{"id":"05174776-a2c0-4738-8a12-5da45e2b26eb","arxiv_id":"2607.24970","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Under i.i.d. preferences, Immediate Acceptance’s expected average rank is asymptotically log n, matching Deferred Acceptance, so IA’s Pareto efficiency yields no first-order rank improvement.","lead":"In large random school-choice markets, the Boston (Immediate Acceptance) mechanism assigns students to schools of average rank about log n—the same order as Deferred Acceptance. Pareto efficiency under truth-telling therefore does not buy a first-order gain in average rank.","discovery_kind":"unification","skeptic_critique":{"model":"moonshotai/kimi-k3","headline":"No significant internal objection identified; the main restriction is the explicitly scoped i.i.d. uniform-preference model.","rationale":"The reader correctly identifies i.i.d. uniform preferences as the weakest assumption. It is essential to Lemma 1, the geometric domination in Eq. (4), and the amnesiac lower-bound estimates. Correlated preferences could change the asymptotics, so the result should not be read as a general statement about realistic school-preference distributions.\n\nThat limitation is nonetheless explicit and conventional for this question, and it does not undermine correctness within the paper's stated model. The proof is parameter-free, handles arbitrary fixed priority profiles, and accounts for the main structural difference between DA and IA—the round restriction—rather than assuming it away. The one-to-one argument extends naturally to the stated skip and bounded-quota variants.\n\nAccordingly, the appropriate response is scope discipline rather than a verdict change. The reader's ACCEPT with high confidence remains justified.","tokens_in":11354,"tokens_out":5582,"duration_ms":221338,"concrete_test":"Independently rewrite the lower-bound argument with an explicit filtration and verify the identity C_{n,a_n}=Σ_{j≤T_{n,a_n}}W_j on A_n (up to a harmless final application) and the conditional mean E[W_j|H_n]=n/(n−K_j). If either fails beyond an O(1) or o(n log n) correction, the lower bound requires repair.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central proof appears structurally sound. Lemma 1 supplies the conditional uniformity needed for the coupon-collector upper bound, while the amnesiac construction and the fast/slow case split in Eqs. (10)–(13) address the fact that IA deletes repeated draws. In particular, the fast case controls wasted ticks using K_j ≤ s_n−1, and the slow case converts many rounds with at least a_n vacant schools into at least a_ns_n genuine applications. Together these give the matching logarithmic lower bound.\n\nThe genuinely load-bearing premise is that each unexposed preference suffix is conditionally uniform. That premise follows directly from i.i.d. uniform preferences, but would fail under common quality tiers or other correlated preference structures. This is a substantive limitation on applicability, not a defect in the stated theorem: the model is declared in Section 2, and Theorem 1 is explicitly a claim about that random-market environment. The uniformity-over-priorities feature is also correctly handled because the coupon bounds hold conditionally on every realized history.\n\nI therefore do not find an internal inconsistency or hidden assumption sufficient to unsettle the central claim.","agreement_with_reader":"agree"},"referee_report":{"model":"moonshotai/kimi-k3","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).","tokens_in":11528,"tokens_out":7530,"duration_ms":247164,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"§2, Corollary 1"},{"comment":"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.","section":"§3.2, Lemma 1"},{"comment":"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.","section":"§3.3, Eq. (11)"},{"comment":"§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.'","section":"§1"},{"comment":"§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.","section":"§4.1"},{"comment":"§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.","section":"§4.3"},{"comment":"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.","section":"§4.1"},{"comment":"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).","section":"Throughout"}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The one thing to know is that Ortega settles a clean open asymptotic: in balanced one-to-one i.i.d. markets, IA’s expected average rank is asymptotically log n for any priority profile, matching the classical Wilson–Knuth bound for DA. Corollary 1 and the skip / bounded-quota extensions follow immediately. That removes one quantitative defense of Boston under truth-telling.\n\nWhat is actually new is the proof technique, not just the statement. Pritchard–Wilson gave rank-by-rank limits and conjectured order log n but left the expectation open. Ortega restores a sequential, round-respecting implementation of IA, couples it to an amnesiac coupon collector, and splits on a fast/slow event A_n. Upper bound is elementary (coupon collector plus at most n leftover applications). Lower bound uses concentration of partial collection time plus the round structure itself when progress is slow. The algebra closes to 1. Same logic carries the skip variant (counting inspected positions) and many-to-one with bounded quotas (double Dixie-cup style). Math is fully written out, no free parameters, no circular fitting. Citations are appropriate; the self-cites supply context, not load-bearing claims.\n\nSoft spots are the usual ones for this literature and are scoped honestly. Everything leans on i.i.d. uniform preferences and conditional uniformity of unexposed suffixes (Lemma 1). Correlated tiers would break it; that is a limitation on applicability, not a hole in the theorem. Truth-telling is assumed for the main result; the short equilibrium section notes that a DA-selecting equilibrium exists but adverse selection can be much worse—fair, not oversold. Finite-n behavior and welfare under real preference structure are left open, which is fine for a pure asymptotic note.\n\nThis is for people who already care about random-market asymptotics in school choice. If you work on mechanism comparison or teach the Wilson–Knuth argument, read it; the adaptation to rounds is neat and short. It deserves a serious referee. I would bring it to reading group and cite the equivalence when the log-n benchmark comes up.","headline":"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.","tokens_in":12444,"tokens_out":547,"would_cite":true,"duration_ms":15503,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B68","91B32"],"pacs":[],"model":"grok-4.5","headline":"In large random school-choice markets, Immediate Acceptance and Deferred Acceptance both assign the average student a school of rank about log n.","keywords":["school choice","Immediate Acceptance","Boston mechanism","Deferred Acceptance","average rank","random markets","coupon collector","asymptotic equivalence"],"falsifier":"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.","tokens_in":12394,"feed_emoji":"🏫","tokens_out":922,"duration_ms":20499,"temperature":0.7,"pith_summary":"School-choice designers often prefer Immediate Acceptance (the Boston mechanism) because, if families report truthfully, it yields a Pareto-efficient assignment, while student-proposing Deferred Acceptance does not. This paper asks whether that efficiency edge shows up in average rank when preferences are random and truthful. It proves that in balanced one-to-one markets with i.i.d. uniform student preferences, IA’s expected average rank is still asymptotically log n—the same leading term long known for DA. So Pareto efficiency does not buy a first-order improvement in how far down the list the typical student is placed. The same log-order conclusion holds for IA that skips full schools and for many-to-one markets with bounded quotas, and it survives at least one natural equilibrium selection under strategic play.","feed_headline":"Boston and DA both place students at rank ~log n","feed_subtitle":"Pareto efficiency under truth-telling does not improve average rank to first order in large random markets.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["IA and DA both yield average rank ~log n in large markets","Boston mechanism matches DA's log n rank asymptotically","IA's efficiency brings no first-order rank gain over DA","Expected IA rank ~log n, same as DA under truth-telling","IA and DA average ranks are asymptotically equivalent"],"cache_read_input_tokens":128,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["IA and DA both yield average rank ~log n in large markets","Boston mechanism matches DA's log n rank asymptotically","IA's efficiency brings no first-order rank gain over DA","Expected IA rank ~log n, same as DA under truth-telling","IA and DA average ranks are asymptotically equivalent"]},"model":"grok-4.5","effort":"low","cost_usd":0.002973,"raw_usage":{"total_tokens":1028,"prompt_tokens":690,"num_sources_used":0,"completion_tokens":65,"cost_in_usd_ticks":29728000,"prompt_tokens_details":{"text_tokens":690,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":273,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":690,"tokens_out":65,"duration_ms":4984,"temperature":1.0,"reasoning_tokens":273,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-31T04:36:41.966377+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"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.","supporting_citations":[],"review_version":1}