{"id":"b25fd89c-1ba8-420b-bc44-70fdcb43fb21","arxiv_id":"2608.09984","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"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).","lead":"Efficiency-Adjusted Deferred Acceptance (EADA), a school-choice algorithm that repeatedly removes under-demanded schools, gives students expected average ranks at most 4 log log n + O(1), breaking the logarithmic barrier of Deferred Acceptance. The same conclusion, with a weaker bound, holds for every Pareto-efficient improvement of DA, and the results extend to many-to-one markets and correlated preferences.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; Theorem 1 is internally sound under the paper's stated i.i.d. assumptions.","rationale":"The reader's weakest-assumption analysis correctly identifies Lemma 8 as the most distribution-sensitive point of the proof. I agree that this is where the i.i.d. uniform assumption is doing real work: closure is only priced correctly when the surviving schools' positions in each student's list are uniform and independent across students. However, this is not a hidden assumption or an internal inconsistency; it is the model stated in Theorem 1. The paper also proves in Appendix B.5 that without some correlation restriction the conclusion fails, so the restriction is necessary. The remainder of the proof is sound: the deterministic rank accounting is careful and correct, the sequential implementation of EADA is justified by Lemmas 2-3 and Proposition 1, the union bound in Proposition 3 is legitimate because the actual residual market is closed, and the use of Pittel's worst-rank bound is sufficient even if the citation's threshold is read as (log n) rather than (log n)^2. I therefore do not find a load-bearing concern that would justify changing the reader's ACCEPT verdict. The suggested exhaustive check of Lemma 8 would still be a worthwhile independent verification, given that this lemma is the probabilistic heart of the paper.","tokens_in":25479,"tokens_out":38555,"duration_ms":351223,"concrete_test":"Independently re-derive Lemma 8 by exhaustive enumeration on a small market (n=5, all pairs I',S' and all restricted preference/priority profiles): verify P(C(I',S') ∩ {P(I',S') >= p}) <= (m/n)^p for every p, and verify that the sequential EADA implementation matches the batch outcome on the same instances. If both pass, the probabilistic core of Theorem 1 is confirmed; if the first fails, the central bound collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After checking the deterministic rank accounting (Lemmas 2-7), the closure probability bound (Lemma 8), the union-bound and tail-sum argument (Proposition 3), and the Pittel-based worst-rank estimate (Proposition 4), I find no load-bearing flaw. Lemma 8 is valid for i.i.d. uniform preferences: conditional on each student's relative ranking of the surviving schools, the positions of those schools form a uniform m-subset, independent across students, so the closure probability factors as (m/n)^{P(I',S')}; the union bound over survivor pairs is legitimate because the realized residual market is closed by Lemma 7. The only caveat is a possible misstatement of Pittel's threshold: if the original theorem states (2+a) log n rather than (2+a)(log n)^2, equation (16) still follows by monotonicity and E[M_DA]=O((log n)^2) is unchanged. The distributional restriction in Lemma 8 is real but it is exactly the paper's assumption, and the tiered counterexample in Section B.5 shows why some restriction is necessary; this is a scope condition, not an internal gap.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the expected average rank (equivalently, the average position of students' assignments in their reported preferences) achieved by the Efficiency-Adjusted Deferred Acceptance (EADA) mechanism in i.i.d. one-to-one matching markets. It proves Theorem 1, which bounds E[R(\\mu_{EADA})] by 4 log log n + O(1), and Theorem 2, which shows that every Pareto-efficient matching weakly Pareto-dominating the student-proposing DA matching has expected average rank O((log log n)^2). The proof of Theorem 1 proceeds through a sequential implementation of EADA (Proposition 1), a deterministic rank accounting (Proposition 2), a closure probability bound for residual markets (Lemma 8), a union-bound and tail-sum estimate (Proposition 3), and a worst-rank bound for DA from Pittel (Proposition 4). Theorem 2 is proved via an acyclicity property of Pareto-efficient matchings (Lemma 9) and a uniform probabilistic bound on large acyclic sets in random preference graphs (Lemma 10). Appendices extend both results to balanced many-to-one markets with bounded quotas and to bounded Plackett-Luce common popularity, and a tiered example in Section B.5 shows that some correlation restriction is necessary.","tokens_in":25688,"tokens_out":22796,"duration_ms":196433,"significance":"If the results are correct, they resolve a natural open question about the rank efficiency of EADA and provide the first sublogarithmic asymptotic guarantee for any Pareto-efficient improvement of DA. The main argument is self-contained given the cited external lemmas, and the leading-order bound is derived rather than fitted to simulations. The paper is careful to identify the distributional limit of its main probabilistic lemma and to exhibit a counterexample showing that unrestricted correlation destroys the result. The authors also honestly state that no matching lower bound is established and that the simulations cannot distinguish bounded from slowly diverging behavior; these limitations do not undermine the stated theorems. The results are likely to be of broad interest to the random matching markets and school choice communities.","major_comments":[],"minor_comments":[{"comment":"The statement of Pittel's Theorem 6.1(b) should be checked against the original source; if the original threshold is of the form C log n rather than C (log n)^2, equation (16) still follows by monotonicity and E[M_DA]=O((log n)^2) is unchanged, so the issue is not load-bearing, but the citation and displayed formula should be accurate.","section":"Section 2.5, Proposition 4"},{"comment":"The phrase 'we may therefore take c=3, 4' appears garbled; it should presumably read 'c = 3.4' or otherwise be stated consistently with the value c(20) = (sqrt(89)-3)/2.","section":"Section 2.5, after equation (16)"},{"comment":"The notation log^2(1+M) is used for the square of the logarithm; this should be defined explicitly in the notation paragraph of Section 2, which currently defines only o and O notation.","section":"Section 3, Proposition 5"},{"comment":"The last term in the displayed inequality is ambiguous as typeset; it should be written as (1+m/K)/(qm) or equivalently 1/(qm)+1/(qK) to avoid confusion.","section":"Appendix A.4, Proposition 9, display (44)"},{"comment":"The text refers to Figure 1, but the figure itself is not visible in the manuscript text; the simulation values and standard errors are given, but the figure should be included or the reference adjusted.","section":"Section 4, Figure 1"}],"recommendation":"minor_revision","confidential_remarks":"The central results appear correct and well within the journal's scope. The revision request is limited to the local presentation issues listed in the minor comments; there are no concerns about circularity, citation patterns, or the internal consistency of the proofs."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real result, not a rounding error. Theorem 1 (EADA expected average rank at most 4 log log n + O(1)) and Theorem 2 (every Pareto-efficient matching that weakly dominates DA achieves O((log log n)^2)) are the first asymptotic guarantees for those objects in iid uniform markets. The paper deserves a serious referee.\n\nThe new machinery is the combination of a sequential implementation of EADA, deterministic rank accounting via application counts, and a union bound over closed residual markets. I checked the main lemmas—serial implementation, the rank identity in Lemma 5, application nesting in Lemma 6, the closure bound in Lemma 8, the tail bound in Proposition 3, the acyclicity argument in Lemma 9, and the uniform event in Lemma 10—and the stress-test pass agrees: no load-bearing flaw. Lemma 8 is exactly right under iid uniform preferences, and the paper is explicit that some distributional restriction is necessary by giving a tiered-agreement example where average rank is linear. The extensions to bounded quotas and bounded Plackett-Luce popularity are substantial and appear to follow the same architecture.\n\nWhat the paper does especially well is honesty about slack. It states that the constants are not sharp, that no lower bound is known, and that simulations at these n cannot distinguish a bounded average rank from log-log divergence. That is the right way to present a first asymptotic result.\n\nSoft spots, in proportion. The model is stylized: complete lists, balanced market, iid uniform preferences. That is not a flaw given the question, but it limits the practical takeaway. The lack of code is not a concern for a theory paper; the proofs are detailed enough to referee. One minor citation check: the Pittel bound is quoted as (2+a)(log n)^2; if Pittel's theorem states (2+a) log n, the conclusion still follows by monotonicity, but the reference should be made precise. Also, the general theorem's rate O((log log n)^2) has no matching lower bound; the paper says this openly.\n\nVerdict: accept for peer review. I would cite Theorem 1 in future work on average-rank performance of matching mechanisms, and I would bring the paper to reading group. A serious referee will find a few things to polish, but the core contribution is solid and clearly beyond what was known.","headline":"This paper delivers the first asymptotic average-rank bounds for EADA and for every Pareto-efficient mechanism weakly dominating DA; the core proof is sound and the caveats are honestly stated.","tokens_in":26214,"tokens_out":1931,"would_cite":true,"duration_ms":18948,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B68","60C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that EADA's expected average rank is at most $4\\log\\log n+O(1)$ in i.i.d. one-to-one markets, breaking DA's logarithmic rank barrier.","keywords":["efficiency-adjusted deferred acceptance","expected average rank","random matching markets","deferred acceptance","Pareto efficiency","log log n","school choice","one-to-one matching"],"falsifier":"Compute exactly, for $n=6$, the probability in Lemma 8 for a fixed survivor pair with $m=3$ and $p=2$: if $\\Pr(\\text{closed} \\cap \\{P\\ge 2\\}) > (3/6)^2 = 1/4$ under i.i.d. uniform preferences, the key estimate fails; a broader check is exhaustive enumeration of all profiles at small $n$ to see whether EADA's expected average rank exceeds $4\\log\\log n + C$ for every fixed $C$.","tokens_in":25275,"feed_emoji":"🎓","tokens_out":11366,"duration_ms":96187,"temperature":0.7,"pith_summary":"Deferred Acceptance (DA) is known to give students an expected average rank of order $\\log n$, while the rank-minimizing assignment keeps expected average rank bounded. This paper establishes the first asymptotic guarantee for the Efficiency-Adjusted Deferred Acceptance (EADA) mechanism: in i.i.d. one-to-one markets with $n$ students and $n$ schools, the expected average rank under EADA is at most $4\\log\\log n+O(1)$. The paper further proves that every Pareto-efficient matching that weakly Pareto-dominates the DA matching has expected average rank $O((\\log\\log n)^2)$, so the logarithmic barrier falls for an entire class of mechanisms, not just EADA. A sympathetic reader would care because this shows that respecting priorities and Pareto efficiency is compatible with an order-of-magnitude improvement over DA.","feed_headline":"EADA's expected rank is O(log log n), beating DA's log n","feed_subtitle":"In i.i.d. random markets, every Pareto-efficient improvement of Deferred Acceptance provably breaks the logarithmic average-rank barrier.","key_machinery":"The argument rests on a sequential implementation of EADA in which under-demanded schools are settled one at a time, rerunning DA after each settlement; the order of settlement is shown to be irrelevant. This turns a student's final rank into the number of applications she makes when she is settled, so the total rank decomposes into a cut term bounded by DA's worst rank and a residual term bounded by the number of applications in the residual DA run. The residual market reached by EADA is student-closed: every survivor prefers her residual assignment to every school already removed. For fixed survivor sets, closure combined with the uniformity of preferences yields the key estimate that the probability of a residual run with at least $p$ applications is at most $(m/n)^p$, because conditional on relative rankings the surviving schools occupy a uniform subset of each student's full list. A union bound over all possible survivor sets then controls the endogenously selected residual market. The general theorem replaces closure by acyclicity of the top-$k$ envy graph, which Pareto efficiency forces and which random preferences make unlikely at large size.","core_discovery":"The central claim is that EADA breaks DA's logarithmic rank barrier: Theorem 1 states $\\mathbb{E} R(\\mu_{\\mathrm{EADA}})\\le 4\\log\\log n+O(1)$ under i.i.d. uniform preferences, where $R$ is the average rank of assigned schools. Because $\\log\\log n=o(\\log n)$, this improves the asymptotic order of students' assignments. Theorem 2 shows the same qualitative conclusion for every Pareto-efficient matching $\\nu$ that weakly Pareto-dominates the student-proposing DA matching, with the weaker rate $\\mathbb{E} R(\\nu)=O((\\log\\log n)^2)$. The paper also extends both conclusions to balanced many-to-one markets with bounded quotas and to bounded Plackett-Luce common popularity, and it gives a tiered example showing that some restriction on preference correlation is necessary.","pith_inferences":["Because the proof's union bound charges every possible survivor set, the actual distribution of markets reached by EADA is plausibly much more concentrated; a sharper analysis of that joint distribution could yield a matching lower bound or a rate below $\\log\\log n$.","Theorem 2's uniformity over mechanisms chosen after seeing preferences suggests the sublogarithmic property is a consequence of Pareto efficiency plus weak dominance of DA; a testable extension would ask whether weakening 'weakly Pareto-dominates DA' to 'improves a positive fraction of students' already forces the same escape from the logarithmic barrier.","The tiered counterexample indicates the boundary is quantitative rather than structural: between uniform preferences and complete tier agreement, the expected average rank may interpolate from doubly logarithmic to linear, and the bounded-popularity model is one natural way to trace that transition.","Simulations in the paper cannot distinguish bounded from doubly logarithmic growth, so an exact computation of EADA's rank distribution for small $n$, or a matching lower bound, would be the next decisive step."],"forward_implications":["EADA's expected average rank is $o(\\log n)$, so the efficiency adjustment changes the asymptotic order of what students receive, not merely the constant factor.","Any Pareto-efficient mechanism that weakly Pareto-dominates DA, even one selected after the preference profile is observed, has expected average rank $O((\\log\\log n)^2)$, ruling out logarithmic average rank throughout the class.","The bounds carry over to many-to-one markets with fixed quotas: under a common quota $q$, EADA attains at most $2(1+1/q)\\log\\log m+O_q(1)$.","Under bounded Plackett-Luce common popularity with weight ratio $\\kappa$, EADA attains at most $4\\kappa\\log\\log n+O_\\kappa(1)$, and every Pareto-efficient improvement of DA remains sublogarithmic.","The coefficient $4$ is not claimed sharp; tightening the closure argument is the identified route toward possibly lower rates."],"supporting_citations":[{"why":"Introduces EADA as the mechanism whose rank performance is studied: repeated DA with consenting students removing under-demanded schools.","marker":"[Kesten, 2010]"},{"why":"Provides the simplified DA-based EADA implementation and the deletion-monotonicity facts on which the sequential version and closure argument are built.","marker":"[Tang and Yu, 2014]"},{"why":"Supplies the classical result that DA's expected average rank is logarithmic, the baseline barrier EADA breaks.","marker":"[Wilson, 1972]"},{"why":"Refines Wilson's analysis, sharpening the logarithmic expected average rank of DA.","marker":"[Knuth, 1976]"},{"why":"Shows Random Serial Dictatorship also has logarithmic average rank, establishing that Pareto efficiency alone does not guarantee sublogarithmic rank.","marker":"[Knuth, 1996]"},{"why":"Gives the tail bound on DA's worst student rank used to control the first cut term in both theorems.","marker":"[Pittel, 1992]"},{"why":"Provides the rank-minimizing benchmark with bounded expected average rank that contrasts with DA and EADA.","marker":"[Nikzad, 2022]"},{"why":"Supplies the bounded-score Plackett-Luce model used for the correlation-robust extension.","marker":"[Ashlagi et al., 2023]"}],"fun_headline_variants":["EADA achieves O(log log n) expected rank, beating DA's log n","From log n to log log n: EADA's asymptotic gain","Every Pareto-efficient DA improvement breaks the log n barrier","EADA cuts students' expected average rank to O(log log n)"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing assumption is that, after conditioning on the relative order of the surviving schools on a student's list, the positions those schools occupy in her full list form a uniformly random subset, independently across students; this holds under i.i.d. uniform preferences, and the paper's tiered example shows that without some such restriction average rank becomes linear.","fun_headline_variants_meta":{"raw":{"variants":["EADA achieves O(log log n) expected rank, beating DA's log n","From log n to log log n: EADA's asymptotic gain","Every Pareto-efficient DA improvement breaks the log n barrier","EADA cuts students' expected average rank to O(log log n)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000942,"raw_usage":{"total_tokens":3987,"prompt_tokens":866,"completion_tokens":3121,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":482,"completion_tokens_details":{"reasoning_tokens":3046}},"tokens_in":482,"tokens_out":3121,"duration_ms":21196,"temperature":1.0,"reasoning_tokens":3046,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T14:39:10.308298+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute exactly, for $n=6$, the probability in Lemma 8 for a fixed survivor pair with $m=3$ and $p=2$: if $\\Pr(\\text{closed} \\cap \\{P\\ge 2\\}) > (3/6)^2 = 1/4$ under i.i.d. uniform preferences, the key estimate fails; a broader check is exhaustive enumeration of all profiles at small $n$ to see whether EADA's expected average rank exceeds $4\\log\\log n + C$ for every fixed $C$.","supporting_citations":[],"review_version":2}