Stable matching assumes agents know their preferences completely. In the marriage problem, each person has a total ordering over all potential partners. In practice, preferences are uncertain until you've actually met someone. You need interviews — costly information-gathering steps — before preferences become concrete.
Beyhaghi, Cai, and Sivan (arXiv:2602.20358) ask: how many interviews are needed to produce a stable matching? The answer: approximately 2 per agent, on average. Not 2 per pair — 2 per person. With n agents on each side, only about 2n total interviews (out of a possible n²) suffice to compute a matching that is stable given the information revealed.
The key insight is that stability doesn't require complete information. An interim-stable matching is one where, after the interviews are done, no pair that has interviewed each other would prefer to deviate, and no uninterviewed pair would benefit in expectation from matching instead. Most potential pairs don't need to be evaluated because most potential deviations are unlikely to be beneficial.
The sequential algorithm adaptively chooses who interviews whom, directing the costly information acquisition to where it matters — the pairs most likely to be blocking. A hybrid approach achieves similar interview efficiency with polylogarithmic communication rounds, making it suitable for decentralized settings.
The result is near-optimal: the authors prove that ~2 interviews per agent is a lower bound for any algorithm achieving interim stability. You cannot do meaningfully better. The problem has an intrinsic information requirement of about 2 interviews per agent — enough to identify the partner and the most threatening alternative, but no more.
The general observation: when a global property (stability) can be certified by local conditions (no blocking pair), the information requirement is determined by the local condition, not the global structure. You don't need to know all preferences — you need to know enough about the relevant neighborhood of the solution. The rest is irrelevant.