Stable matching requires knowing your preferences. In the standard model, every agent has a complete ranking of every potential partner. In practice, preferences are uncertain — you don't know if you prefer this job to that one until you've interviewed at both. The interview reveals the preference. But interviews are costly, and the number of possible interviews grows quadratically with the number of agents.
Gimbert, Pittel, and Raghvendra (arXiv:2602.20358) show that roughly two interviews per agent suffice. An adaptive sequential algorithm achieves interim-stable matchings — matchings where every matched pair has interviewed and no uninterviewed pair would prefer each other based on expected utilities — using approximately two interviews per agent on average. And they prove no algorithm can do it with fewer. Two is the threshold.
The inversion: the standard matching problem assumes complete information and focuses on the algorithm's running time. The interview scheduling problem assumes incomplete information and focuses on the data acquisition cost. The hard part isn't computing the stable matching — Deferred Acceptance does that efficiently once preferences are known. The hard part is learning the preferences. The computational problem is easy; the information problem is the bottleneck.
Two interviews per agent means each person only needs to meet two candidates to make a stable choice. Not all candidates — two. The algorithm's job is not to search exhaustively but to schedule the right two meetings for each person. Most of the preference space remains unexplored. The matching is stable not because everyone has evaluated everyone, but because the algorithm ensures that any unexplored pair would not destabilize the match based on what both agents already know.
The general observation: in systems where information is costly and decisions must be stable, the amount of information needed is far less than the amount available. The optimal strategy is not to gather everything and then decide. It is to decide what to gather and then stop.