Stable Matching Looks Inefficient in Large Random Markets

Stable matching mechanisms are usually defended on incentive and fairness grounds: no student-school pair can block the outcome by matching with each other. This paper asks what that stability costs in large random assignment markets. The answer is unusually sharp for a theory paper: under the authors' random preference model, stable allocations are Pareto-inefficient with probability tending to 1, and the inefficiency is not confined to a small tail of unlucky students.

The core object is the envy digraph induced by the student-proposing Deferred Acceptance outcome. A directed edge from student $i$ to student $j$ means that $i$ prefers $j$'s assigned school to her own. If a directed cycle exists, the students on that cycle can trade assignments so that every student in the cycle strictly improves and no one outside the cycle is harmed. The paper's main move is to show that this graph is not a sparse collection of isolated cycles. It contains a giant strongly connected component.

Figure 1 gives the visual version of the argument: in simulations, the largest strongly connected component takes up almost the whole graph as market size grows, while the second-largest component remains negligible.

Core Contribution

The paper turns a familiar local observation about trading cycles into an asymptotic inefficiency result for stable matching mechanisms. Prior work had shown that Deferred Acceptance can be Pareto-dominated in examples, and that efficiency and stability often conflict. The new result is stronger: in large random markets, the conflict is systematic, and any stable allocation inherits the same large inefficiency.

The authors first analyze the student-proposing Deferred Acceptance allocation, then use the lattice structure of stable matchings to extend the conclusion beyond that particular stable mechanism. The mechanism-specific claim is that the envy digraph after Deferred Acceptance has a unique giant strongly connected component. The welfare claim follows because students in a strongly connected component can be arranged into improving trading cycles.

Technical Approach

The model is a random school-choice environment with many students and schools, fixed capacity parameter $q$, and independently drawn preferences. After running Deferred Acceptance, the authors build the envy digraph among students. The graph-theoretic target is a giant strongly connected component: a set of students where each can reach each other through directed envy paths.

The proof strategy separates the matching step from the random-graph step. Deferred Acceptance determines each student's assigned school, which in turn determines which other assignments she envies. The authors then show that, with high probability, this induced envy graph has enough connectivity to contain one dominant strongly connected component. Once that component exists, almost all students in it are potentially improvable through cycles.

A second step considers maximal cycle packings. The result is not merely that some improving cycle exists, or even that many cycles exist. Every maximal collection of disjoint improving cycles covers almost all students asymptotically. That is the paper's main efficiency statement: different Pareto improvements over Deferred Acceptance become asymptotically equivalent in coverage, even if the exact cycles differ.

Results and Analysis

The paper's quantitative evidence is primarily asymptotic theory, supported by simulation plots. The headline theoretical results are limit statements: stable allocations are Pareto-inefficient with probability approaching 1, the share of students outside improving opportunities approaches 0, and the largest strongly connected component covers a fraction approaching 1 of the market.

Figure 2 tracks the fraction of unimprovable students across 2,000 random problems for each market size. The plotted fraction falls toward zero as $n$ increases, matching the theorem's interpretation that inefficiency is large in the population sense, not only in existence.

The simulation design also checks finite-market behavior. The figures include experiments over $n = 10, 20, \ldots, 200$ with $q = 5$, and a two-tiered preference model averaged over 1,000 random envy digraphs for each $n$. The two-tiered variant matters because uniform random preferences are a strong abstraction; showing the same giant-component pattern under a tiered model makes the phenomenon less dependent on complete symmetry.

The practical interpretation is narrower than the title might suggest. The paper does not say that stability is normatively bad, nor does it evaluate strategic behavior, information constraints, or legal constraints in deployed school-choice systems. It shows that, in the model studied, stability leaves a very large Pareto-improvement opportunity on the table. For designers who treat stability as non-negotiable, this is a warning about the efficiency price. For designers willing to post-process stable matchings through trading cycles, the result suggests that many students can be helped after Deferred Acceptance without hurting others.

Limitations

The evidence is strongest as an asymptotic theorem for random markets. Real assignment systems often have correlated preferences, priorities, geographic constraints, sibling rules, and heterogeneous capacities. The paper partially addresses preference structure with a two-tiered simulation, but it does not establish the full result for the institutional detail of a specific deployed market. Its welfare metric is also ordinal Pareto improvement, not cardinal utility or distributional fairness.