REVIEW 8 minor 1 cited by
Asymptotic Equivalence of Immediate and Deferred Acceptance
T0 review · 0 major / 8 minor · reviewed 2026-07-31 · grok-4.5
Pith's one-line read In large random school-choice markets, Immediate Acceptance and Deferred Acceptance both assign the average student a school of rank about log n.
desk verdict Closes the Pritchard–Wilson conjecture cleanly: under i.i.d. truth-telling, IA’s expected average rank is also ~log n, so Pareto efficiency buys no first-order gain over DA. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
A sequential round-respecting implementation of IA that restores a coupon-collector comparison: an amnesiac upper process that allows repeated draws bounds applications from above by n H_n, while a case-split lower bound (few rounds vs many active students per round) shows that deleting repetitions cannot remove the leading n log n term.
What would settle it
In a sequence of balanced random markets with i.i.d. uniform preferences, compute the realized average IA rank divided by log n; if the ratio stays bounded away from 1 (for example converging to a constant other than 1, or growing like log log n), the main theorem is false.
Extended reading notes
Core claim
In i.i.d. one-to-one random markets of size n, for every sequence of school priorities, the expected average student rank under Immediate Acceptance satisfies E[rk_IA]/log n → 1 as n → ∞, matching the classical asymptotic for Deferred Acceptance. Thus the ratio of the two expected average ranks tends to 1. The same leading asymptotic holds for IA with skips and, with log(m/q) scaling, for many-to-one markets with bounded quotas.
Load-bearing premise
Student preferences are drawn independently and uniformly at random over all strict rankings of schools; structured or correlated tastes would break the coupon-collector bounds as written.
Editorial extensions
If this is right
- Truthful IA and DA are first-order equivalent in expected average rank in the canonical random market, so IA’s Pareto edge is only lower-order in that metric.
- The same log n (or log m/q) asymptotic holds for adaptive/skipping IA and for many-to-one markets with bounded quotas.
- There exists a Nash equilibrium of the IA reporting game that reproduces the DA matching, so strategic play need not destroy the first-order equivalence.
- Policymakers cannot cite first-order average-rank gains under truth-telling as a reason to prefer IA over DA in large i.i.d. markets.
Reading between the lines
- If real districts have strong common quality tiers rather than i.i.d. tastes, the paper’s coupon-collector logic may fail and IA could still pull ahead or fall behind on average rank—worth checking on administrative preference data.
- The result sharpens the welfare debate: any large practical gain from IA over DA must come from incomplete information, cardinal intensities, or equilibrium selection, not from ordinal average rank under truth-telling.
- Extending the amnesiac argument to growing quotas or to correlated priorities could map where the log-order equivalence breaks.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the Immediate Acceptance (Boston) mechanism in balanced one-to-one random matching markets with n students, n schools, i.i.d. uniform student preferences, and arbitrary fixed school priorities. Theorem 1 establishes that the expected average rank of the assigned school under IA, conditional on truthful reporting, is asymptotically log n — matching the classical Wilson (1972)/Knuth (1976) result for Deferred Acceptance, so that (Corollary 1) the ratio of expected average ranks under IA and DA tends to 1. The proof introduces a sequential implementation of IA that respects rounds, then derives an upper bound via a coupon-collector coupling (Lemma 1: conditional uniformity of unexposed preference suffixes gives discovery probability ≥ u/n when u schools are unseen, yielding E[T] ≤ nH_n + n), and a matching lower bound via Knuth's amnesiac clock: a two-case split on the event A_n (few vs. many rounds to reach a_n = ⌈(log n)²⌉ unseen schools) shows wasted ticks are negligible in the fast case (Eqs. 10–12) while slow progress forces ≥ (2+o(1))n log n genuine applications in the slow case (Eq. 13). Extensions cover IA-with-skips (Theorem 2, via a balls-into-bins contraction argument) and many-to-one markets with bounded quotas (Theorem 3/Proposition 1), plus an observation that a Nash equilibrium of IA replicating DA always exists (§4.3). The result resolves the log n conjecture implicit in Pritchard and Wilson (2023).
Significance. If correct — and I believe it is — this is a clean and useful contribution. It settles the conjecture of Pritchard and Wilson (2023) on the order of IA's expected average rank, and does so with a sharp constant (limit exactly 1, not just Θ(log n)), uniformly over all school-priority profiles, with no free or fitted parameters anywhere in the argument. The proof technique is itself a contribution: it shows that the Wilson–Knuth coupon-collector/amnesia machinery extends to IA once rounds are respected, with the round structure doing double duty in the lower bound. The extensions (IA with skips, many-to-one markets with bounded quotas) and the equilibrium observation in §4.3 broaden the result without diluting it. The policy message — that IA's Pareto efficiency buys no first-order improvement in average rank over DA even before accounting for manipulation — is directly relevant to the school-choice design debate.
minor comments (8)
- [§2, Corollary 1] Corollary 1: the DA benchmark is imported from Knuth (1976), but the corollary asserts the limit uniformly over all priority sequences (▷_n). The coupon-collector analysis of DA is indeed priority-free (each proposal target is conditionally uniform regardless of which student proposes, by the same suffix-uniformity argument as Lemma 1), so the claim is correct — but the paper should state explicitly that the cited Wilson/Knuth/Pittel results hold in this priority-uniform form, or note that the argument of §3 applies verbatim to DA.
- [§3.2, Lemma 1] Lemma 1: the conditioning event F includes other students' exposed preference prefixes and schools' accept/reject decisions. The conclusion is right because F is measurable with respect to exposed prefixes, and students' lists are independent, so the current student's unexposed suffix remains a uniform permutation of the untried schools. One sentence making this explicit would close the only place where a skeptical reader might worry about information leakage through the history.
- [§3.3, Eq. (11)] Eq. (11) is asserted from the mean and variance computations in (7)–(8); please include the one-line Chebyshev step (P(|C_{n,a_n} − E C| > εn log n) ≤ Var/(εn log n)² = O(1/(a_n log² n)) → 0, plus the mean gap 2 log log n / log n → 0). As written the reader must supply it. Also worth one line noting that the L1 convergence in (11) is what licenses E[C 1_{A_n}] = (p_n + o(1)) n log n in (12) without needing p_n → 1 — the manuscript uses this implicitly.
- [§1] §1, first paragraph after the model description: 'Nonetheless, the expected average rank remained unknown' — the antecedent is ambiguous (DA's expected rank is known since Wilson/Knuth; it is IA's that was open). Please reword, e.g., 'For IA, the expected average rank remained unknown.'
- [§4.1] §4.1 intuition paragraph: 'A surviving student scans roughly n/m new positions before finding one of the m vacant schools' is heuristic and ignores the K already-inspected positions; the actual negative-hypergeometric mean is (n − K_{i,r} + 1)/(m + 1), and the proof in Appendix A handles K_r carefully via K_r ≤ T^τ_{r−1}. Consider flagging the heuristic as such so readers do not think the n/m rate is exact per round.
- [§4.3] §4.3: the Ergin–Sönmez (2006) characterization invoked for (15) is for the complete-information preference-reporting game; state this information assumption explicitly when defining the equilibrium selection σ_DA. The existence-vs-selection caveat that follows is appropriately stated.
- [§4.1] Attribution detail: the 'adaptive Boston mechanism' label is attached to Miralles (2009), but that paper is primarily a defense of the standard Boston mechanism; the skips/adaptive variant is more directly associated with Harless (2019) and Mennle–Seuken (2021), both of which are cited. Please double-check the attribution wording.
- [Throughout] Cosmetic: missing space in 'asymptotically $\log n$' in the abstract; equation number (14) appears inside the statement of Theorem 2 rather than on a displayed equation; check consistent italicization of a_n and s_n in the displayed definitions (9) and (21).
Circularity Check
No significant circularity: pure coupon-collector bounds on IA applications under stated i.i.d. preferences
full rationale
The paper derives the asymptotic E[rk_IA_n] ~ log n from first-principles probabilistic arguments (sequential IA accounting, conditional uniformity of unexposed preference suffixes in Lemma 1, geometric domination for the upper bound, and an amnesiac coupon-collector case-split for the matching lower bound). The target quantity is identified with total genuine applications via the rank-sum identity and is bounded by external objects (harmonic numbers, partial coupon-collection times C_n,a) that are not fitted to the result. Self-citations supply related context (DA inefficiency, strategic vulnerability) but are not load-bearing inputs that force the log-n claim. The i.i.d. uniform-preference model is an explicit scope assumption, not a circular reduction. Extensions (IA-with-skips, bounded-quota many-to-one) reuse the same independent coupon logic. No self-definitional step, fitted-as-prediction step, or uniqueness-import chain appears.
Assumptions & free parameters
assumptions (6)
- domain assumption Student preferences are i.i.d. uniform over the n! strict rankings of schools; priorities are arbitrary fixed profiles.
- domain assumption Market is balanced: |I|=|S|=n (one-to-one) or total seats equal number of students (many-to-one).
- domain assumption Agents report true preferences (truth-telling), even though IA is manipulable.
- standard math Classical coupon-collector expectation and variance: E[C_{n,a}]=n(H_n−H_a), Var=O(n²/a); harmonic H_n∼log n.
- domain assumption Sequential within-round processing of IA yields the same matching as simultaneous IA.
- domain assumption For many-to-one extension, all school quotas are bounded by a fixed Q independent of market size.
Cite this review
Pith. "Pith review of Asymptotic Equivalence of Immediate and Deferred Acceptance." pith.science (2026). https://pith.science/paper/OKSV445O
@misc{pith2026260724970,
author = {Pith},
title = {Pith review of: Asymptotic Equivalence of Immediate and Deferred Acceptance},
year = {2026},
howpublished = {\url{https://pith.science/paper/OKSV445O}},
note = {Machine review of arXiv:2607.24970}
}
abstract
Immediate Acceptance (IA, also known as the Boston mechanism) is commonly used to assign students to schools because it produces a Pareto-efficient matching if parents report their preferences over schools truthfully, unlike student-proposing Deferred Acceptance (DA). In this paper, we ask: does IA produce meaningfully better average ranks than DA, conditional on truth-telling? We show that, in i.i.d. one-to-one random markets, IA's expected average rank is asymptotically $\log n$, just like DA's. Therefore, IA's Pareto efficiency does not translate into a first-order improvement in expected average rank. This conclusion extends to variations of IA as well as to many-to-one markets.
Forward citations
Cited by 1 Pith paper
-
Efficiency Adjustments Break the Logarithmic Rank Barrier
EADA's expected average rank is at most 4 log log n + O(1), and every Pareto-efficient mechanism that weakly Pareto-dominates Deferred Acceptance achieves O((log log n)^2).
Reviewed July 31, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.