A Simple Method for School Choice Lotteries

Yasunori Okumura

arxiv: 2605.06721 · v2 · pith:OFDIGVOInew · submitted 2026-05-07 · 💻 cs.GT · econ.TH

A Simple Method for School Choice Lotteries

Yasunori Okumura This is my paper

Pith reviewed 2026-06-30 23:30 UTC · model grok-4.3

classification 💻 cs.GT econ.TH

keywords school choicelotteriesex ante stabilityequal treatment of equalsconstrained efficient stable matchingordinal dominationrandom assignment

0 comments

The pith

The ETE reassignment of any constrained efficient stable matching produces an ex ante stable lottery that satisfies equal treatment of equals and is not ordinally dominated by any other ex ante stable lottery.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper offers a direct polynomial-time procedure to generate school choice lotteries that remain stable before random outcomes are drawn and assign identical students identical probabilities. The procedure starts from any constrained efficient stable matching and applies a reassignment step that equalizes treatment while preserving the ex ante stability property. The resulting lottery cannot be improved in the ordinal sense by any alternative ex ante stable lottery, and for some starting matchings it also escapes domination by every ex post stable lottery. A reader would care because real school assignment systems routinely use randomization to respect capacities, yet most existing methods either sacrifice stability in expectation or require heavy computation.

Core claim

The ETE reassignment of any constrained efficient stable matching is ex ante stable, satisfies ETE, and is not ordinally dominated by any other ex ante stable lottery. There exists a constrained efficient stable matching whose ETE reassignment is not ordinally dominated by any ex post stable lottery.

What carries the argument

The ETE reassignment operation, which converts a deterministic constrained efficient stable matching into a lottery by equalizing probabilities across equal students while maintaining ex ante stability.

If this is right

The constructed lottery meets the equal treatment of equals criterion for any group of identical students.
No student can gain by deviating to a different school with positive probability in a way that breaks ex ante stability.
The lottery is at least as good as any other ex ante stable lottery according to every student's reported ranking.
For at least one choice of starting matching, the lottery also evades ordinal domination by every ex post stable lottery.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Districts could adopt the method as a lightweight post-processing step on top of existing stable-matching algorithms.
The polynomial-time guarantee makes the approach feasible even for large assignment problems with thousands of students.
The result suggests that ex ante stability plus ETE can be achieved without sacrificing the efficiency properties already present in constrained efficient matchings.

Load-bearing premise

The standard school choice model with strict preferences and capacities admits constrained efficient stable matchings, and the ETE reassignment step preserves stability without introducing new violations.

What would settle it

A school choice instance in which the ETE reassignment of some constrained efficient stable matching produces a lottery that is ordinally dominated by another ex ante stable lottery.

read the original abstract

This note proposes a simple polynomial-time method for constructing an ex ante stable school-choice lottery satisfying equal treatment of equals (ETE). We show that the ETE reassignment of any constrained efficient stable matching is ex ante stable, satisfies ETE, and is not ordinally dominated by any other ex ante stable lottery. We further show that there exists a constrained efficient stable matching whose ETE reassignment is not ordinally dominated by any ex post stable lottery.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The note gives a polynomial-time ETE reassignment construction that yields ex ante stable ETE lotteries with non-domination guarantees over other ex ante stable ones and sometimes over ex post stable ones.

read the letter

The core contribution is a simple polynomial-time method that takes any constrained efficient stable matching and produces an ex ante stable lottery satisfying equal treatment of equals via ETE reassignment. The two non-domination results are the main new claims: the output is not ordinally dominated by any other ex ante stable lottery, and there exists a choice of input matching where it is also not dominated by any ex post stable lottery.

The construction is useful because it stays within the standard school-choice model with strict preferences and capacities, builds directly on existing constrained efficient matchings, and avoids heavy computation. The non-domination properties give concrete fairness guarantees that matter for applications. Nothing in the stated claims suggests the reassignment breaks stability or capacity constraints.

The main limitation is that the abstract states the theorems without proof sketches, so the details of how ETE reassignment preserves ex ante stability and avoids new instabilities remain to be checked in the full text. The assumptions are the usual ones, and the stress-test found no internal contradictions.

This is for people working on probabilistic mechanisms and school-choice design. Readers who need an efficient way to generate fair ex ante stable lotteries will get direct value from the method. It deserves a serious referee because the results are specific, the runtime claim is clear, and the non-domination statements are falsifiable in principle.

I would send it to peer review.

Referee Report

1 major / 0 minor

Summary. The paper proposes a simple polynomial-time method for constructing an ex ante stable school-choice lottery satisfying equal treatment of equals (ETE). It shows that the ETE reassignment of any constrained efficient stable matching is ex ante stable, satisfies ETE, and is not ordinally dominated by any other ex ante stable lottery. It further shows that there exists a constrained efficient stable matching whose ETE reassignment is not ordinally dominated by any ex post stable lottery.

Significance. If the results hold, this provides a computationally efficient and conceptually simple way to produce ex ante stable and ETE-satisfying lotteries in school choice, extending standard stable matching theory with a reassignment operation that preserves key properties. The second claim, if verified, would be particularly useful as it shows some such lotteries can be undominated even relative to the stronger ex post stability benchmark.

major comments (1)

[Abstract] Abstract (and presumably the main text): the central theorems are stated clearly but the manuscript provides no proof sketches, counter-example checks, or derivation outlines for the claims that the ETE reassignment preserves ex ante stability and yields an undominated lottery. This is load-bearing for both main results and prevents verification of the reassignment operator's properties under the standard model assumptions.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their constructive feedback. We address the major comment below and will revise the manuscript accordingly.

read point-by-point responses

Referee: [Abstract] Abstract (and presumably the main text): the central theorems are stated clearly but the manuscript provides no proof sketches, counter-example checks, or derivation outlines for the claims that the ETE reassignment preserves ex ante stability and yields an undominated lottery. This is load-bearing for both main results and prevents verification of the reassignment operator's properties under the standard model assumptions.

Authors: We agree that the current version of the manuscript would benefit from explicit proof sketches for the central claims. In the revised manuscript, we will add concise proof sketches outlining the key steps for (i) why the ETE reassignment of a constrained efficient stable matching is ex ante stable and satisfies ETE, and (ii) why it is not ordinally dominated by any other ex ante stable lottery (as well as the existence result relative to ex post stable lotteries). These additions will not change the results but will improve verifiability under the standard school-choice model. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper proposes a polynomial-time construction via ETE reassignment of constrained efficient stable matchings and proves that the resulting lottery is ex ante stable, satisfies ETE, and is undominated among ex ante stable lotteries (with a further existence claim relative to ex post stable lotteries). These results rest directly on the standard school-choice primitives (strict preferences, capacities, stability definitions) and the explicit definition of the reassignment operator; no step reduces by construction to a fitted parameter, self-citation chain, or renamed input. The derivation is therefore self-contained and externally falsifiable against the model assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Paper relies on standard axioms of the school choice model (student preferences, school capacities, stability definitions) with no free parameters or invented entities introduced.

axioms (2)

domain assumption Existence of constrained efficient stable matchings in the school choice instance
Invoked to define the input to the ETE reassignment procedure
standard math Standard definitions of ex ante stability and equal treatment of equals
Background from matching theory literature

pith-pipeline@v0.9.1-grok · 5584 in / 1238 out tokens · 20079 ms · 2026-06-30T23:30:52.624045+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

3 extracted references · 3 canonical work pages · 1 internal anchor

[1]

arXiv:2602.10679

Smart Lotteries in School Choice: Ex-ante Pareto-Improvement with Ex-post Stability. arXiv:2602.10679. Cookson, B., Shah, N

work page arXiv
[2]

Proceedings of the 26th ACM Conference on Economics and Computation, p.1130

Fairly Stable Two-Sided Matching with In- differences. Proceedings of the 26th ACM Conference on Economics and Computation, p.1130. https://doi.org/10.1145/3736252.3742675 Erdil, A., Ergin, H

work page doi:10.1145/3736252.3742675
[3]

Equal Treatment of Equals and Efficiency in Probabilistic Assignments

Equal Treatment of Equals and Efficiency in Probabilis- tic Assignments. Unpublished manuscript available at https://arxiv.org/pdf/2508.14522 14

work page internal anchor Pith review Pith/arXiv arXiv

[1] [1]

arXiv:2602.10679

Smart Lotteries in School Choice: Ex-ante Pareto-Improvement with Ex-post Stability. arXiv:2602.10679. Cookson, B., Shah, N

work page arXiv

[2] [2]

Proceedings of the 26th ACM Conference on Economics and Computation, p.1130

Fairly Stable Two-Sided Matching with In- differences. Proceedings of the 26th ACM Conference on Economics and Computation, p.1130. https://doi.org/10.1145/3736252.3742675 Erdil, A., Ergin, H

work page doi:10.1145/3736252.3742675

[3] [3]

Equal Treatment of Equals and Efficiency in Probabilistic Assignments

Equal Treatment of Equals and Efficiency in Probabilis- tic Assignments. Unpublished manuscript available at https://arxiv.org/pdf/2508.14522 14

work page internal anchor Pith review Pith/arXiv arXiv