RESEARCH DOSSIER
Matching and Allocation under Capacity Constraints
Abstract. Matching under capacity constraints studies the allocation of indivisible opportunities when participation, compatibility, priority, and institutional quotas jointly determine attainable outcomes. This Research Dossier reconstructs the combinatorial feasibility conditions and the economic logic of stable many-to-one matching, deferred acceptance, immediate acceptance, priority-based allocation, housing exchange, matching with contracts, and coordinated kidney exchange. It distinguishes applicant welfare, two-sided stability, maximum feasible fill, incentive compatibility, and realized take-up. Explicit finite counterexamples establish the limits of otherwise powerful theoretical guarantees. Published research from school choice in the United States, Chile, and Ghana and dated United States medical-residency statistics provide institution-specific evidence on incentives, application information, and the interpretation of outcomes. The analytical synthesis identifies how accessible capacity, priority rights, the message domain, and implementation jointly condition observed allocation, without establishing a new named theory or reporting original causal estimates.
Keywords: matching theory; capacity constraints; indivisible allocation; deferred acceptance; stability; priorities; strategy-proofness; school choice; matching with contracts; market design; kidney exchange; welfare economics; causal identification
Scope and economic object
Matching is the allocation of indivisible opportunities among participants whose feasible associations depend on acceptance, compatibility, ranking, and capacity. A place at a school, a residency appointment, the right to occupy a particular dwelling, and a coordinated transplant exchange share the feature that the outcome consists of discrete associations rather than independently divisible quantities. The incidence of a match changes what can be offered to another participant. The economic object is therefore an allocation together with the rule and institutional conditions that make it attainable.
This dossier focuses on finite markets with hard individual and institutional capacities. It addresses the relationship between feasibility, stability, priorities, incentives, welfare, and actual take-up. It treats transferable utility as a comparison case and networked exchange as a boundary extension. It does not infer a universal social welfare ranking from ordinal data, develop a new named economic theory, or estimate new causal effects from administrative microdata. The primary disciplinary home is Microeconomics; Mathematical Economics supplies the formal allocation and combinatorial methods.
A priority is an ordering used to decide which applicants may claim scarce positions. It can represent an institution's actual preference, a test score ordering, legal entitlement, an administrative tie-break, or a composite of these. Its mathematical representation alone does not establish its ethical standing. A preference describes the applicant's choice among alternatives, including remaining unmatched. A quota gives the maximum admissible number of assigned participants at an institution; eligibility limits which associations may be considered. A mechanism maps submitted information into outcomes, while an algorithm is a computational realization of that mapping. The distinction matters when two computer systems use the same mathematical rule but different application interfaces or data validation procedures.
The research questions are conditional. Which constraints determine whether a complete allocation is possible? When do individually rational outcomes resist blocking? How do changes in priority, capacity, information, and coordination alter distribution? How can observational match records distinguish an allocation rule's effects from endogenous applications and institutional differences? These questions connect mathematical existence to economic implementation and welfare without collapsing them into one criterion.
Historical development of matching economics
Combinatorial existence precedes the modern market-design literature. Hall's (1935) representatives theorem gives the mathematical ancestry of distinct assignments. A collection of admissible sets has distinct representatives precisely when the union of any subcollection is at least as numerous as that subcollection. The capacity interpretation developed below follows by replacing each institution with its available unit slots. This is a feasibility statement and contains no preference ranking.
Gale and Shapley (1962), in College Admissions and the Stability of Marriage, transformed a feasibility problem into a strategic ordering problem. Their many-to-one version allowed institutions to hold applicants provisionally up to stated quotas, revising those holdings as stronger applicants appeared. Their optimality result orders stable allocations from the applicants' perspective. It concerns a restricted domain of two-sided preferences; it cannot be read as a universal theorem about efficient allocation of public resources.
Shapley and Scarf (1974), in On Cores and Indivisibility, established a core result for exchange involving indivisible endowments. A house already owned by a participant belongs to that participant's initial bundle, so the right to withdraw and retain it helps define feasible coalition deviations. This property differs from a school seat held in public trust. Both are allocation problems, but their institutional endowments differ.
In labor markets and public services, the design problem became increasingly explicit as economists studied actual clearinghouses. Roth and Peranson (1999) examined the physician match redesign, where complementary choices complicate a simple two-sided model. Abdulkadiroğlu and Sönmez (2003) subsequently formulated school choice as mechanism design, evaluating shortcomings in several US district plans. Hatfield and Milgrom (2005) incorporated contract terms into the allocation object rather than restricting each association to a single undifferentiated seat. Roth, Sönmez, and Ünver (2004) extended indivisible exchange to compatible living-donor kidney transfers with distinct ethical and operational constraints.
The historical progression thus reflects a widening of the feasible object: a slot, a pair of preferences, an endowed object, a contract, and a coordinated network of exchanges. The relevant theory becomes more demanding as additional contractual or technological interdependencies enter. Institutional evidence also acquired an independent role: actual applications, redesigned systems, and assignment-generated randomness became means of evaluating mechanisms instead of treating their predicted properties as realized social outcomes.
Feasibility and scarce capacity
Let I be a finite set of applicants and J a finite set of institutions. Let q(j) be a nonnegative integer quota for institution j, and let E be a subset of I × J representing mutually admissible associations. Define x(i,j) as a binary assignment variable. An ordinary unit-demand allocation satisfies
- For each applicant i, sum over j of x(i,j) is at most one.
- For each institution j, sum over i of x(i,j) is at most q(j).
- If (i,j) is outside E, x(i,j) equals zero.
A zero row represents the outside option. All acceptable but unassigned opportunities remain available subject to the rest of the institution's constraints. These conditions specify the feasible set. A match respecting them might still violate priority or leave a desirable compatible vacancy.
For any subset A of applicants, write N(A) for the institutions adjacent to at least one member. Complete placement requires |A| ≤ sum of q(j) over j in N(A). Necessity follows by counting the slots usable by A. Sufficiency follows by making q(j) distinct copies of every institution, giving each eligible applicant edges to each copy, and using the distinct-representatives theorem. This argument uses the counting theorem associated with Hall (1935); the institutional extension is a direct derivation. The condition is exact for independent unit slots, without group minima, linked regional limits, or couples.
The same object can be expressed as a maximum-flow problem: connect a source to applicants with capacity one, eligible applicants to institutions with capacity one, and institutions to a sink with capacity q(j). Integral flows correspond to assignments. The cardinality maximum equals the maximum flow. The necessity of examining subsets rather than the aggregate quota can be seen with three applicants a, b, c and two institutions X and Y. Let X have one seat and Y two. If a and b can access only X, while c can access only Y, the total capacity is three but only two people can be placed. The violating subset is {a,b}, whose access amounts to one position.
A change in eligibility can relieve this shortage without adding a seat. If b also becomes eligible for Y and considers it acceptable, a can take X while b and c take Y. Conversely, increasing Y's quota without extending any admissible association leaves the shortage for a and b unchanged. Increasing the numerical stock of resources and improving the connectivity of the allocation network are different interventions.
Individual capacity may be fixed by legal or physical requirements. Other capacities are economic choices: staffing, training budgets, working hours, scheduling windows, or complementary facilities. An institution may nominally offer ten positions but only have resources to fill eight combinations of positions. When feasibility depends on the identity or combination of assigned participants, a simple scalar quota is incomplete. The correct modeling step is to state the joint constraints explicitly rather than interpreting a failure of the basic model as a failure of integer arithmetic.
The linear relaxation of the ordinary bipartite incidence formulation has integral extreme points after the usual flow construction. This means that maximum-cardinality and linear-weight allocations can be solved without fractional assignments in that domain. Joint constraints and non-bipartite exchange cycles may destroy this convenient representation. Computational solvability, however, is only one aspect of economic design: a maximum flow does not respect rankings unless those rankings are introduced through additional requirements or an objective.
Stability, deferred acceptance, and proposer optimality
Give each applicant a strict ranking of acceptable institutions and the outside option, and each institution a strict priority among acceptable applicants. Assume institutional choices are responsive: the institution chooses its highest-priority acceptable applicants up to its quota, independently of interactions among them. A matching is individually rational if every assigned association is acceptable. A blocking pair is an applicant and institution such that the applicant prefers that institution to the current assignment, and the institution has an acceptable vacancy or would replace a lower-priority incumbent. Stability means individual rationality and absence of blocking pairs.
The applicant-proposing deferred acceptance algorithm operates as follows. Each unheld applicant proposes to the most preferred eligible institution not yet attempted. Each institution maintains a provisional set consisting of its highest-priority applicants among existing holdings and new proposals, rejecting the remainder. Rejected applicants proceed to their next acceptable institution. When no new proposal is possible, provisional holdings become assignments. A finite instance terminates after at most |E| proposals because each edge can be attempted once.
The stability proof reconstructs the reasoning in Gale and Shapley's college admissions procedure (1962). Suppose an applicant prefers institution j to the final allocation. The applicant must have applied there and been rejected. At the rejection, the institution held a full quota of applicants above that applicant in priority. Later replacements can only improve the priority of its lowest retained applicant. At termination, j neither has a vacancy nor holds someone lower in priority. The claimed pair cannot block. Rejected applications to unacceptable institutions are excluded from the pair definition.
The optimality statement is stronger than existence. Consider the earliest rejection of an applicant from any institution at which the applicant could be assigned in some stable matching. The rejecting institution holds a full quota of more preferred applicants. Each one has already tried all personally preferred institutions; by earliest rejection, none of those earlier institutions can be assigned to that applicant in a stable outcome. A hypothesized stable assignment retaining the rejected applicant must omit at least one of the higher-priority applicants from this institution. That applicant is assigned to a less-preferred feasible alternative or remains outside and can block. Thus no such rejection can occur. Every applicant attains the best attainable institution across stable matchings in the DA result. The proof does not compare this outcome to allocations that allow priority violations.
Consider three applicants and two one-seat schools. Applicant a ranks Y above X; b ranks X above Y; c ranks X only. X ranks a above c above b, and Y ranks b above a above c. Initially a applies to Y while b and c apply to X. X retains c. Then b applies to Y, displacing a. Then a applies to X, displacing c, who has no other acceptable choice. The final assignments are a at X, b at Y, and c outside. The rejected applicants and attempts can be audited individually.
All institutions are full. Applicant a prefers Y, but Y retains b with higher priority; b prefers X, but X retains a with higher priority; c wants X, but X retains a. The outcome is stable. Giving a Y and b X would improve both and leave c outside; c would then have a justified claim to X over b. The alternative improves the welfare of the two assigned applicants without harming the third in ordinal terms, yet violates the stated priority system. Stability and Pareto efficiency over all feasible student allocations need not coincide, even under strict priorities.
The truthful-reporting property for proposing applicants in the standard responsive domain removes the gain from changing their reported ranking while keeping the domain and other reports fixed. It does not guarantee truthful participation by institutions, truthful information about residence or eligibility, or strategic immunity when applicants must truncate their lists. A mechanism with a list-length constraint effectively changes the admissible messages. Participants may then need to decide which alternatives to investigate and include. An ordinal outcome cannot reveal what an applicant would have ranked had relevant information been costless.
The term stable is also conditional on participation rights. A program that remains outside the clearinghouse, a contract signed before the clearing date, or an enforceable local entitlement changes the alternatives against which blocking must be assessed. Stability measured only within the submitted network can coexist with outside-market dissatisfaction.
Alternative rules and welfare comparisons
Immediate acceptance processes rank rounds by the order in which applicants list institutions. Within a round, competing applicants are ranked by the institution's priority; successful placements become final. The attraction of this mechanism is its ability to grant early choices when the corresponding schools are available. Its strategic cost is that a rejected applicant cannot displace a lower-priority participant accepted in a previous round.
Take applicants a, b, and c with one seat at each of X and Y. Applicant a prefers Y to X; b regards only Y as acceptable; c regards only X as acceptable. The priority at Y places b above a; X places a above c. Under immediate acceptance with truthful reports, b obtains Y and c obtains X in round one; a remains unmatched. If a instead lists X first, a wins X and is strictly better off. Applicant-proposing DA gives b Y and a X without the need for a false first choice. These are constructed examples, not historical observations. They isolate a strategic penalty created by committing allocations before considering later proposals.
The empirical discussion in Abdulkadiroğlu et al.'s (2006) Changing the Boston School Choice Mechanism documents a related policy concern: families differed in their recognition of the old mechanism's strategic features. This adds a distributive dimension to incentive compatibility. A rule can favor families with better strategic knowledge even when its advertised priority categories are uniform.
Under a common strict priority, serial dictatorship assigns each applicant the most preferred remaining acceptable opportunity in descending priority order. It is strategy-proof for applicants and Pareto efficient in the unconstrained one-unit domain with a fixed order. It is stable relative to that common priority. With institution-specific priorities, a single common ordering cannot necessarily preserve each local priority. The choice between a shared and differentiated priority is itself a policy choice.
Top trading cycles begin with each active participant pointing to the most preferred available object and each object pointing to its current owner or to an institutionally specified claimant. Every finite directed graph with one outgoing edge per vertex contains a directed cycle. Clear its trades and repeat. In the standard housing market, participants begin with endowed houses; the allocation respects the endowment-based exchange structure. In a school-choice adaptation, priorities replace ownership in the pointing rule, so the ordinary housing-core argument cannot simply be imported. A cycle may improve applicant welfare while overruling an institution's priority claims. The exact version of the mechanism determines which rights survive.
With tied priorities, a lottery may refine each institution's ordering before a deterministic algorithm is executed. A fixed lottery produces an ex post allocation; variation over possible draws produces a distribution over allocations. The comparison should report both properties of realized assignments and distributional properties of the lottery. An outcome stable under its refined order may be inefficient at the level of the original, weak priority relations. Abdulkadiroğlu, Pathak, and Roth (2009) examine the NYC high school match as an instance of the interaction between efficiency, stability, and strategy-proofness under indifferences. The existence of a tie-break does not resolve the choice of social objective.
Cardinality is another distinct criterion. Let a prefer X to Y, b accept only X, X prioritize a over b, and Y accept a. With one seat at each institution, DA assigns a to X and leaves b outside. There is a two-person feasible allocation a to Y and b to X. It violates stability because a and X would block. Maximum fill is not guaranteed by ordinary stability. The counterexample also shows why a shortage of realized matches cannot immediately be attributed to an insufficient number of physical slots.
When transfers are available and utility is quasilinear, a different optimization problem is informative. Consider two people and two indivisible objects. Values are a: X=10, Y=9; b: X=8, Y=0. The value-maximizing assignment gives a Y and b X, obtaining 17 rather than 10. With object prices p(X)=2 and p(Y)=0, a prefers Y (9 versus 8) while b prefers X (6 versus 0). Each can afford the assumed prices; no budget constraint beyond quasilinearity is imposed. This illustrates how money can support an efficient assignment by pricing scarce opportunities. Where prices or transfers are prohibited, or liquidity and entitlement matter, the same outcome cannot be justified by the same argument.
The design decision must state whose welfare counts. Applicant Pareto efficiency evaluates only applicants' orderings. Two-sided Pareto efficiency includes institutional preferences. Stability encodes the ability of individuals and institutions to form better bilateral associations. A weighted social objective requires interpersonal weights or valuations supplied from outside ordinal rankings. Constrained efficiency compares only allocations satisfying the chosen restrictions. An assertion of efficiency without identifying both the welfare domain and the feasible comparison class is underspecified.
Contracts, complementary demand, and complex quotas
In a contract formulation, a match specifies more than a partner. A contract can identify a worker, institution, salary, work location, hours, training track, or other terms. An applicant may accept at most one of the relevant contracts, and institutions choose subsets from offers. Let C(j,S) be institution j's chosen contracts from finite offer set S. A choice rule is substitutable when a contract chosen from a larger set remains chosen if other offers are removed while the contract stays available. Equivalently, under the corresponding definition, rejected available contracts remain rejected when the offer set expands. Irrelevance of rejected alternatives is a related consistency requirement: removing rejected offers does not change the chosen set. The law of aggregate demand requires chosen cardinality to be weakly increasing as the offer set expands.
Hatfield and Milgrom's (2005) Matching with Contracts analyzes a finite contract domain, with conditions on institutions' choices and unit-demand doctors. Its existence, stable-allocation structure and incentive results explain why the responsive quota model extends to certain richer settings. In the specific worker-proposing algorithm, substitutes together with aggregate-demand conditions support truthful worker reports. The cardinality invariance result is conditional upon the stated premises. It must be distinguished from arbitrary generalized constraints. A priority system implemented by greedily taking the best q distinct acceptable applicants has these properties in the ordinary no-contract-variation setting.
Complementarity arises if an institution wants two applicants together but rejects them separately, or a household evaluates two jobs as one bundle. Suppose a department requires both a laboratory specialist and a safety supervisor; neither appointment independently opens the facility. A choice rule accepting both but rejecting either alone fails substitutability. A mechanical deferred acceptance procedure designed for separable places can lose the very monotonic rejection property that its stability proof requires. A rejected offer can become desirable after another offer arrives.
Here is a small instance with no stable outcome under natural couple blocking. Hospitals X and Y each have one slot. A couple a and b values only the bundle (a at X, b at Y), with outside as the alternative. A singleton s prefers X to Y to remaining unmatched. X ranks a over s; Y ranks s over b. If the couple is assigned, s and Y block. If the couple is outside and s is at X, the couple can jointly displace s at X and fill Y. If s is at Y or outside, X and s block. The cases exhaust individually rational allocations. There is no stable allocation under these blocking conventions. This constructed example does not predict the frequency of instability in real residency markets.
Quota structure creates further complexity. An institution might reserve places for a particular category, limit the number of placements needing a scarce clinical supervisor, or impose regional aggregate caps shared among multiple institutions. Upper limits restrict admissible sets. Lower quotas can require a certain number to be assigned or the program to close; with a minimum of two, a singleton offer set may be rejected while the pair is accepted. Hard reserves, transferable reserves, and soft targets produce different feasible sets and incentive properties. Some structured choice rules preserve substitutes; arbitrary overlapping restrictions and minimum enrollment do not provide a general guarantee.
A transparent policy specification therefore states the total quotas, categories, overlap rules, eligibility, priorities within each category, reserve transfer rules, and the treatment of unfilled positions. A change in seats alone is not equivalent to a change in these rules. Mechanism comparison should first determine whether the institution's distinct contractual options satisfy its operational choice assumptions; if they do not, the analysis should report which theorem no longer applies and use an appropriate restricted optimization, search, or explicit treatment of unresolved blocking.
Networked exchange and operational constraints
The simplest kidney exchange model represents each incompatible patient-donor pair as a vertex in a directed compatibility graph. An arc v to w indicates that the donor in v may donate to the patient in w according to specified medical compatibility tests and institutional eligibility. A directed cycle describes a simultaneous reciprocal exchange; vertex-disjoint cycles ensure that no donor or recipient is used twice. A non-directed two-cycle representation permits graph matching when only pairwise exchange is allowed. The problem differs from choosing a single institution for each applicant because exchanges require coordinated sets of linked acts.
Roth, Sönmez, and Ünver (2004) analyze Kidney Exchange within the legal and ethical conditions of their setting, including simulations of gains from expanding the potential exchange set. Their (2005) pairwise exchange study analyzes the restrictions and incentives associated with two-way exchanges under simplified binary-preference assumptions. These are theoretical and simulated findings, not measurements of actual transplantation gains in all current programs. Compatibility edges in a mathematical graph are provisional descriptions, not clinical decisions.
For an illustrative three-vertex network, take only arcs a→b, b→c, and c→a. No two-way exchange is feasible. Allowing a three-cycle creates three theoretical transplants. Conversely, if compatible routes are deleted after further testing, the cycle becomes infeasible. The comparison isolates the effect of a cycle-length restriction independently of preferences and raw donor count.
More generally, let K be a precomputed set of feasible cycles and chains that respects specified length limits and timing. Select binary z(k) for each k, with the sum of z(k) over exchanges containing a given patient or donor unit at most one. A cardinal objective maximizes the number of recipients served; other objectives can incorporate compatibility quality, clinical priority, or expected completion. A chain initiated by an available nondirected donor has different start and termination conditions from a cycle. It must be represented with its own resource constraints and no unwarranted assumption that every vertex is an incompatible pair.
If each edge in a three-cycle has a hypothetical independent probability of successful execution p=0.9, and the cycle only executes when every edge succeeds, the expected transplant count is 3 × 0.9³ = 2.187. This is an illustrative sensitivity computation, not a measured medical probability; independence and all-or-nothing completion are substantive assumptions. A different scheduling protocol, correlated crossmatch failures, or the ability to salvage part of a chain changes the calculation. The basic expected count is not a sufficient welfare metric when patient-specific urgency, waiting time, and risk matter.
Capacity in network exchange can include operating room time, laboratory review, hospital participation, transportation, and synchronization requirements. Expanding the compatibility graph can increase the maximum feasible number of exchanges, yet physical and contractual constraints may reduce the achievable set. Measuring actual completed procedures as well as proposed combinations separates mathematical allocation from realized benefit. Policy analysis must preserve consent, privacy, and clinical eligibility as governing constraints rather than treating them as penalties to trade away in an unconstrained numerical objective.
Data, definitions, and research identification
The research method combines formal reconstruction, independently constructed examples, bibliographic verification, and bounded comparison of published empirical and institutional results. No confidential participant record was accessed; no cross-country pooled estimate or raw clinical replication is reported. The sources differ in evidentiary strength. Historical and theoretical results are grounded in original article text where available or attributed to accessible scholarly abstracts. Administrative totals are directly reported by the responsible institution. Published behavioral studies provide evidence within their own populations and research designs.
A reproducible analysis requires a data dictionary. The applicant table should identify a pseudonymous applicant, cycle, eligibility category, entry status, declared outside option, and application deadlines. The institution table should include the opportunity identity, cycle, initial capacity, revised capacity, reserve types, priority groups, and rules for vacant places. The application table records acceptable options submitted, rank order, timestamp, completeness, and any legal list cap. The priority table contains the rule version and complete ranking inputs or a protected reproducible equivalent. Lottery records require randomization unit, tie-break distribution, draw correlation across institutions, and an auditable seed or secure custody record. Results tables distinguish tentative hold, final offer, acceptance, enrollment, withdrawal, substitution, and later placement.
The denominator belongs to the metric. An offer rate is offers divided by the relevant eligible applicant population. A match rate may use registered applicants, active applicants, applicants qualifying for a specified track, or only those who received an offer. A fill rate uses filled positions over the number offered under the same definition and stage. A first-choice assignment rate should state whether it uses submitted first choice among matched applicants or among all active applicants, and whether unavailable alternatives and unranked outside options are excluded. A blocking-pair count requires independently specified priorities and the appropriate acceptable set; it cannot be reliably computed from placement records alone.
The observed ranking is an action, not a complete measurement of preferences. Under a strategic mechanism, the ranking may reflect anticipation of earlier acceptance rules. Even with a strategy-proof mechanism, limited search and a list cap may generate a truncated and selected set of preferences. Consequently, comparisons of average assigned rank across different application regimes may reverse the interpretation of what actually improved. A mechanism change that encourages applicants to add ambitious schools can lower their reported first-choice assignment rate without lowering their underlying welfare.
Simulation with fixed inputs asks what alternative rules would produce for identical submitted lists, priorities, and quotas. The result is a mechanical counterfactual. It does not anticipate changes in information acquisition, application effort, institution participation, or capacity. A model that allows reported lists to respond to the mechanism requires additional assumptions and sensitivity checks. Using the observed lists as if they were unchanging preferences can misattribute behavioral responses to the algorithm.
Causal studies use a different source of variation. Abdulkadiroğlu, Angrist, Narita, and Pathak (2017), in Research Design Meets Market Design, derive empirical tools using randomization incorporated into centralized assignment and apply their framework to Denver school attendance. A general design distinguishes realized assignment Z from actual attendance D and outcome Y. Conditional on a well-defined assignment propensity and the relevant randomization structure, comparisons of outcomes by offer identify an intention-to-treat effect in the eligible overlap group. Under independence, relevance, exclusion, monotonicity, and appropriate no-interference assumptions, an instrumental-variables ratio of outcome and take-up differences can identify an effect for compliers. The estimand can change with the lottery, population, and school alternatives.
Centralized random assignment is rarely equivalent to an unrestricted lottery across the whole applicant population. Priorities, choice lists, admission cutoffs, and correlated tie-breakers affect the set of comparisons. Applicants with an assignment probability of zero or one contribute no within-stratum random assignment variation. Peer composition may create spillovers, while competitors' choices alter equilibrium probabilities. Even valid local causal effects of attending a particular school do not directly quantify the welfare effect of a national mechanism redesign.
Administrative law and confidentiality require limiting access to sensitive input variables while preserving verifiable procedures. A public report can publish aggregate outcomes, the algorithm version, eligibility definitions, and reproducible synthetic cases without disclosing rank lists or clinical records. Individual appeals should have an auditable record of the particular rule and data used. These practices improve the interpretation of allocation metrics by revealing which administrative choices generated the values.
International evidence and institutional interpretation
School choice in the United States illustrates how changing the sequencing of accepts and rejections alters incentives. The Boston reform decision in July 2005, documented by Abdulkadiroğlu et al. (2006), followed examination of applications and the strategic incentives of the existing rule. The evidence concerns a particular district and its administrative history. The principle established by the immediate-acceptance example is general within the finite domain; the magnitude of strategic disadvantage in another district is an empirical question.
The New York City study by Abdulkadiroğlu, Pathak, and Roth (2009) addresses a different design margin: how indifferences are broken and what is sacrificed by insisting on particular combinations of incentive and efficiency properties. A single common lottery and independent school lotteries produce different correlation structures. One should distinguish an efficiency comparison conditional on a tie-break from a comparison over the distributions generated by alternative lotteries. The relevant institutional choice includes how priorities are defined, not just how their ties are resolved.
Physician matching illustrates contractual complexity and common timing. Roth and Peranson (1999) report computational design evidence from the US residency system, where complementarities make direct application of elementary matching results inadequate. The official NRMP matching algorithm explanation describes applicant-proposing provisional assignments, displacement, and final binding outcomes. This description is a useful account of the basic algorithm, not a complete specification of how every special-case joint ranking is processed.
The dated 2025 Main Residency Match results (NRMP 2025) report 43,237 offered positions and 40,764 filled at the algorithm stage. In March 2026, the 2026 Main Residency Match results report 44,344 offered and 41,482 filled at the same named stage. These totals permit a simple internally consistent comparison:
| Year | Positions offered | Algorithm fills | Algorithm vacancies | Fill share |
|---|---|---|---|---|
| 2025 | 43,237 | 40,764 | 2,473 | 94.28% |
| 2026 | 44,344 | 41,482 | 2,862 | 93.55% |
The fill shares are calculated as the ratio of algorithm fills to positions offered, rounded independently to two decimals. The source reports round them to one decimal (94.3% and 93.5%). The fall of about 0.73 percentage points is consistent with an increase in both positions and filled positions: the position stock grew more quickly than the algorithm fills. The result does not identify why particular positions were unfilled. The outside option, geography, specialization, interview access, eligibility, and joint rankings all may constrain the feasible network.
A separate denominator is the active applicant count. The reports identify 47,208 in 2025 and 48,050 in 2026, of whom 37,667 and 38,354, respectively, obtained PGY-1 positions. The PGY-1 proportions are approximately 79.79% and 79.82%. These denominators are not interchangeable with the count of PGY-1 plus PGY-2 positions filled. Post-algorithm processes also change the final position fill count; the 2025 report describes SOAP and its inclusion of positions not in the algorithm phase. Therefore algorithm-stage vacancies cannot be equated to final unused training capacity.
Information and application choice supply a different margin in Chile and the United States. Arteaga, Kapor, Neilson, and Zimmerman (2022), in Smart Matching Platforms and Heterogeneous Beliefs in Centralized School Choice, examine search behavior and feedback interventions in Chile and New Haven through randomized and regression-discontinuity designs. They find that perceived admission chances influence search even when ranking known schools truthfully is optimal, and that warning applicants with high nonplacement risk improves some application and enrollment outcomes. The measured outcomes derive from their platform and population; they do not prove that every warning scheme improves all markets.
Ghana provides a contrasting institutional setting. Ajayi, Friedman, and Lucas (2026), in When Information is Not Enough, report a randomized study encompassing 900 junior high schools in their Ashanti-region sample. Admission uses a constrained four-choice list among school-program options, with exam performance informing priority. Information provision altered application and admission characteristics, yet the study did not detect improved matriculation. Some households pursue alternative schools after assignment. This distinction shows why a change in the allocation message differs from a change in realized attendance. The journal issue is January 2026; online publication occurred in June 2025.
Chile/New Haven and Ghana therefore offer evidence on different information interventions, technology, admission stages, and outside opportunities. One cannot subtract the estimated outcomes across them to obtain a universal treatment effect of centralized matching. They demonstrate that the useful unit of comparison includes search environment, list constraints, assignment, and enrollment. A broader global assessment would need harmonized definitions and evidence from additional national systems. The present cases provide international analytical variation without claiming representative global coverage.
Comparative robustness and policy diagnostics
A counterfactual should first specify which part of the institution is allowed to change. Keeping eligibility and capacities fixed while comparing deferred and immediate acceptance isolates sequencing. Keeping the algorithm fixed while expanding the number of acceptable choices isolates an input-network change, provided the new choices are genuinely acceptable. Varying capacities while preserving priorities measures feasible resource expansion; changing priorities while holding resource levels fixed changes the entitlement structure. Jointly changing all four prevents clean attribution without a factorial design or structural assumptions.
For a finite baseline, define maximum feasible cardinality M, the assignment cardinality observed under a specified mechanism m, and the realized take-up count T. A comparison of M and m describes the binding limits of the stated rule and input profile; a comparison of m and T describes the gap between offers and take-up under the particular follow-up window. These are diagnostic counts, not separate causal estimators. If M is calculated from lists that are themselves truncated, it understates the set of matches potentially attainable under expanded search. If post-match assignments enter T but not m, the two counts must first be made stage-consistent.
A ranking-based audit should compare the allocation to the priority rule actually in force. On a strict priority profile, a claimant assigned to a lower-ranked acceptable institution has a blocking claim only when the preferred institution has a compatible vacancy or a lower-priority assigned applicant. When reserves are involved, potential replacement must satisfy all operative constraints. A purely pairwise audit cannot detect all coalition deviations in a market with complementary contracts. An institution can satisfy every pairwise condition and still be vulnerable to a coordinated offer.
The authorial examples give a useful battery of tests. A two-applicant demand bottleneck persists after expanding an institution that neither applicant can use. A stable assignment can forego both maximum fill and applicant Pareto improvements when such improvements conflict with priority. An immediate-acceptance mechanism can impose a cost on truthful reporting. A joint couple preference can make stability impossible. A three-cycle can increase feasible exchange count when pairwise limits are relaxed. All examples are small enough to inspect by hand and exhaustively enumerate. They test the boundaries of claims, not their typical prevalence.
Sensitivity to a priority reversal is easiest to see in the two-applicant fill example. If X instead ranks b over a, then a is displaced to Y and both are placed. The same preference profile and quotas support a different stable result. A change in scarcity alone is not needed. In the three-applicant welfare example, relaxing a particular justified-envy condition allows a two-person improvement; retaining the priority system precludes it. These comparisons clarify which constraint is causally responsible inside the constructed profile.
A probabilistic analysis should test common versus independent tie-breaks, group-level assignment probabilities, and the joint distribution of outcomes. Simulation estimates should record seed, number of draws, input version, numerical method, and uncertainty from finite sampling. If a deterministic rule has multiple optima, the implementation must document its tie-resolution order to reproduce the output. If capacities depend on fiscal conditions, the sensitivity exercise should vary the resource constraint rather than just the total quota. Averages should be accompanied by subgroup, location, and eligibility variation where the data allow.
Finally, implementation quality is measurable separately from economic desirability. Software can be checked against exhaustive small instances, deterministic regression cases, feasibility invariants, and priority rules. A formally valid program can still apply the wrong institutional priorities, stale eligibility, or incorrectly recorded applicant choices. An administrative review therefore needs input provenance, policy version, change logs, protected access, and a way to reproduce contested decisions. The cost of such safeguards should be evaluated alongside application complexity and the operational value of accurate allocations.
Original analytical synthesis
The evidence and formal reconstruction support an integrated interpretation of capacity-constrained matching: effective allocation depends on the structure of access to scarce opportunities, the rights governing competition for them, and the ability of participants to convert an assignment into actual participation. These dependencies explain why the same numerical quota can produce distinct outcomes across markets and why a formally excellent assignment method may fail to address a binding institutional obstacle.
First, capacity is relational in its economic effect. In a finite network, a new seat benefits applicants only when it is accessible to a person who can reach it directly or through a feasible reassignment. Hall's condition gives the exact form of the bottleneck in the unit-slot domain. An aggregate shortage indicator misses shortages concentrated among participants with narrow access. A capacity policy should therefore analyze the distribution of accessible places and the opportunity cost of alternative eligibility or mobility measures. This is a comparative interpretation of existing combinatorial theory.
Second, the welfare consequences of priority are inseparable from its normative basis. In the three-applicant instance, enforcing priority transfers welfare relative to a feasible applicant improvement; the loss is the cost of honoring the stated claim of an excluded applicant. If priority represents an ethically justified entitlement, respecting that claim may be central to the institution. If priority is merely a historical proxy unrelated to the policy objective, the same formal stability property might preserve an undesirable distribution. The mathematical computation identifies the conflict; the legitimacy of the claim is a separate institutional question.
Third, incentives operate at more than one decision stage. Strategy-proofness simplifies ranking a known acceptable set under stated assumptions. Information search, interviews, qualification, application limits, and outside options determine that set before the allocation rule operates. Empirical work on school information and platform feedback demonstrates that intermediate application changes and final participation can diverge. The practical benefit of a truthful ranking rule therefore depends on how accessible and comprehensible the prior choice process is. This conclusion does not diminish the theorem; it locates its domain.
Fourth, additional constraints can alter the mathematical type of the problem. Simple individual capacity yields a bipartite flow formulation. Complementarity in contracts introduces joint deviations and potential nonexistence of stable outcomes. Coordinated exchange requires graph cycles or chains and concurrent execution. A policy document that describes all three as generic assignment cannot establish which algorithm or welfare guarantee applies. The correct order of analysis is to specify the admissible collective acts and then identify the appropriate mechanism.
Fifth, measured outcomes require stage-consistent units. The distinct applicant and position ratios in the residency data show that a stable applicant-level rate can coexist with a changing fill rate. This follows from their different populations and resource denominators; no behavioral explanation is identified by the aggregate arithmetic. Likewise, a school application warning can reduce estimated nonplacement risk without having the same effect in a different country with costly post-assignment transfers. A credible evaluation connects the chosen measure to the actual decision stage.
The author's contribution is this structured comparison of formal constraints, counterexamples, and heterogeneous institutional evidence. It does not claim a new theorem, named theory, mechanism, or empirical discovery. The independent examples furnish reproducible explanations for the separation between feasibility, priorities, welfare, incentives, and realized participation. The conclusions are conditional on explicitly stated models and on the evidentiary scope of the selected studies.
Open research questions and limitations
Several extensions require dedicated evidence beyond the present dossier. Endogenous quotas introduce strategic supply, entry, and closure decisions. A program expanding one category of posts can change the total feasible network, competitors' participation, and salary conditions. The equilibrium effect of such a change requires modeling institution behavior as well as applicant choices. Dynamic matching adds the timing of arrivals, expiration of offers, learning, and wait-list movement; one-period stability does not resolve these tradeoffs.
Diversity and geographic policy raise questions about the choice rules that can implement specified group targets while respecting capacity and acceptable priorities. Upper bounds, minimum commitments, reserve systems, and cross-institution budgets generate different mathematical properties. The policy objectives should be independently justified; subgroup or socioeconomic data should be handled with explicit lawful measurement and protection rules.
Market power, fees, and institutional application screening may produce strategic behavior before the clearinghouse stage. This dossier's unit-demand preference domain does not by itself model application pricing, interview costs, or strategic capacity reports. In many markets, uncertainty about acceptance and preferences creates a sequential search problem even when the eventual ranking mechanism has a strong incentive property.
Empirical inference also has unresolved boundaries. Administrative data often omit rejected options, the outside alternatives that participants would have accepted, or the information they possessed at the time of choice. An empirically valid estimation strategy should identify the lottery or cutoff variation, account for changing capacity, and define the population for which outcomes are observed. Cross-market transportability requires explicit assumptions about participation, opportunity sets, policy definitions, and equilibrium responses.
The source review uses primary texts where available and scoped publisher or institutional abstracts elsewhere. A subset of direct source and screenshot retrieval attempts encountered access restrictions. The dossier confines attributed claims to material actually retrieved, and it does not claim a systematic review of all published work, external peer review, unrestricted full-text access, or replication of confidential data. Its quantitative results are either arithmetic derived from official totals or small constructed examples. Additional international studies and primary restricted-paper verification would deepen the empirical and historical record without changing the conditional status of the elementary derivations.
Conclusion
Capacity-constrained matching is an economic problem of constituting and allocating discrete opportunities within an institutionally defined feasible set. In basic unit-demand environments, combinatorial counting characterizes whether all participants can be served; responsive priorities and deferred acceptance yield stable and applicant-optimal outcomes within the stable set. Those properties have distinct scopes from maximum fill and unconstrained applicant welfare. Transfers, contractual terms, complementary demands, quotas, and linked exchange alter the relevant domain and may require different mechanisms.
The formal examples establish specific boundary conditions. The restriction to accessible institutions can create a local shortage despite aggregate slack. Immediate acceptance creates a potential incentive to alter reported rank. Stability may preclude either a higher-cardinality allocation or an applicant Pareto improvement. Complementarity can remove the existence guarantee altogether, and cycle restrictions can reduce attainable exchange. These are logical implications of the stated instances, not empirical frequency claims.
International evidence supports treating information acquisition, application, assignment, and take-up as separately observed decisions. The practical evaluation of a matching mechanism requires institution-specific priorities, comparable denominators, and a counterfactual appropriate to the outcome of interest. The selected studies and administrative counts illuminate distinct margins without yielding a universal welfare ranking. The resulting analysis locates the economic value of matching mechanisms in the relationship between formal guarantees and the institutions that give them operational meaning.
References
Abdulkadiroğlu, Atila, and Tayfun Sönmez. 2003. School Choice: A Mechanism Design Approach. American Economic Review 93 (3): 729–747. DOI: 10.1257/000282803322157061.
Abdulkadiroğlu, Atila, Joshua D. Angrist, Yusuke Narita, and Parag A. Pathak. 2017. Research Design Meets Market Design: Using Centralized Assignment for Impact Evaluation. Econometrica 85 (5): 1373–1432. DOI: 10.3982/ECTA13925.
Abdulkadiroğlu, Atila, Parag A. Pathak, Alvin E. Roth, and Tayfun Sönmez. 2006. Changing the Boston School Choice Mechanism. Working paper, May 18 revision; NBER Working Paper 11965 (January version). DOI of January version: 10.3386/w11965.
Abdulkadiroğlu, Atila, Parag A. Pathak, and Alvin E. Roth. 2009. Strategy-Proofness versus Efficiency in Matching with Indifferences: Redesigning the NYC High School Match. American Economic Review 99 (5): 1954–1978. DOI: 10.1257/aer.99.5.1954.
Ajayi, Kehinde F., Willa H. Friedman, and Adrienne M. Lucas. 2026. When Information is Not Enough: Evidence from a Centralised School Choice System. Economic Journal 136 (673): 26–60. Online June 13, 2025. DOI: 10.1093/ej/ueaf046.
Arteaga, Felipe, Adam J. Kapor, Christopher A. Neilson, and Seth D. Zimmerman. 2022. Smart Matching Platforms and Heterogeneous Beliefs in Centralized School Choice. Quarterly Journal of Economics 137 (3): 1791–1848. DOI: 10.1093/qje/qjac013.
Gale, David, and Lloyd S. Shapley. 1962. College Admissions and the Stability of Marriage. The American Mathematical Monthly 69 (1): 9–15. DOI: 10.1080/00029890.1962.11989827.
Hall, Philip. 1935. On Representatives of Subsets. Journal of the London Mathematical Society s1-10 (1): 26–30. DOI: 10.1112/jlms/s1-10.37.26.
Hatfield, John William, and Paul R. Milgrom. 2005. Matching with Contracts. American Economic Review 95 (4): 913–935. DOI: 10.1257/0002828054825466.
National Resident Matching Program. 2025. National Resident Matching Program Releases the 2025 Main Residency Match Results, Celebrates the Next Generation of Physicians. March 21.
National Resident Matching Program. 2026. NRMP Releases Results of the 2026 Main Residency Match for More Than 38,000 Future Residents. March 20.
National Resident Matching Program. n.d. The Matching Algorithm. Official explanatory webpage. Accessed November 17, 2026.
Roth, Alvin E., and Elliott Peranson. 1999. The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design. American Economic Review 89 (4): 748–780. DOI: 10.1257/aer.89.4.748.
Roth, Alvin E., Tayfun Sönmez, and M. Utku Ünver. 2004. Kidney Exchange. Quarterly Journal of Economics 119 (2): 457–488. DOI: 10.1162/0033553041382157.
Roth, Alvin E., Tayfun Sönmez, and M. Utku Ünver. 2005. Pairwise Kidney Exchange. Journal of Economic Theory 125 (2): 151–188. DOI: 10.1016/j.jet.2005.04.004.
Shapley, Lloyd, and Herbert Scarf. 1974. On Cores and Indivisibility. Journal of Mathematical Economics 1 (1): 23–37. DOI: 10.1016/0304-4068(74)90033-0.