New Algorithm Guarantees Fair & Stable Random Allocations in Two-Sided Markets
Imamura and Kawase solve a key challenge in ex ante fairness for matching markets with discrete concavity.
In a new paper appearing at EC'26, Kenzo Imamura and Yasushi Kawase address a fundamental problem in two-sided matching markets: how to ensure both stability and fairness when random tie-breaking is used. They prove that when agents have discrete concave (M$^ atural$-concave) valuations — a class capturing many practical preferences — there exists an allocation that is ex ante stable (no blocking coalition wants to deviate based on expected outcomes) and ex ante fair (treats symmetric agents symmetrically).
The authors characterize such allocations as Alkan-Gale stable outcomes under choice functions derived from concave closures with symmetric strictly convex tie-breaking. A key technical contribution is a generalization of the Birkhoff–von Neumann theorem, which decomposes any ex ante stable fractional allocation into a lottery over stable deterministic allocations. They also extend the results to purely ordinal preferences within a matching-with-contracts framework under matroid constraints, which covers existing models like one-to-many random allocation with responsive choice and controlled school choice with lotteries. This provides a rigorous foundation for designing fair lotteries in high-stakes markets.
- Proves existence of ex ante stable and fair allocations for agents with M^\natural-concave valuations, resolving a long-standing open problem in market design.
- Uses a generalized Birkhoff–von Neumann theorem to decompose any ex ante stable fractional allocation into a lottery over deterministic stable allocations.
- Extends results to ordinal preferences under matroid constraints, enabling practical applications like controlled school choice lotteries.
Why It Matters
Provides a rigorous theoretical foundation for fair lotteries in matching markets, directly impacting school choice, kidney exchange, and job matching.