MenuNet: A Strategy-Proof Mechanism for Matching Markets
New AI mechanism balances fairness and efficiency in constrained markets like school choice.
Matching markets — like school choice, labor markets, and residency assignments — rely on stability and truthfulness. But real-world constraints (diversity quotas, regional caps, capacity slacks) often make stable matchings impossible. Researchers Zhaohong Sun and Makoto Yokoo propose MenuNet, a neural mechanism that sidesteps this by generating individualized probabilistic menus. Agents choose sequentially from these menus, guaranteeing strategy-proofness by design. Instead of forcing a single unstable outcome, MenuNet distributes instability across agents in a principled way, optimizing trade-offs between fairness (no envy) and non-wastefulness.
MenuNet models fairness and waste as differentiable objectives, enabling gradient-based optimization. Empirically, it outperforms Random Serial Dictatorship (RSD) on envy and Deferred Acceptance (DA) on waste, while maintaining computational efficiency. This learning-based approach scales to large, highly constrained environments where classical mechanisms struggle. MenuNet represents a new paradigm: using neural representations to design flexible, axiom-driven market clearing processes for critical real-world applications.
- MenuNet uses neural network-generated personalized probabilistic menus to guarantee strategy-proofness by construction
- Handles complex distributional constraints (diversity quotas, regional balance) where stable matchings don't exist
- Outperforms RSD in envy reduction and DA in waste reduction, with scalable computation
Why It Matters
Makes matching markets fairer and more efficient for school choice, labor markets, and constrained allocation problems.