💻 computer science

MenuNet: A Strategy-Proof Mechanism for Matching Markets

The paper proposes \texttt{MenuNet}, a strategy-proof mechanism design framework that uses neural networks to generate personalized probabilistic menus, effectively balancing the trade-off between stability axioms (fairness and non-wastefulness) in complex matching markets with distributional constraints where traditional stable matchings often fail to exist.

Original authors: Zhaohong Sun, Makoto Yokoo

Published 2026-05-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zhaohong Sun, Makoto Yokoo

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a massive school lunch program. You have hundreds of students, each with their own favorite meal, and a limited number of seats at each table. The goal is to get everyone a seat they like without anyone feeling cheated or left out.

In the world of economics and computer science, this is called a matching market. The challenge is that you have two golden rules that often fight each other:

Truthfulness: Students shouldn't be able to trick the system by lying about what they like to get a better seat.
Stability: No two people should be able to swap seats and make both of them happier.

Usually, when you add extra rules—like "Table A must have at least 5 kids," or "The total number of kids at all tables can't exceed 100"—these two golden rules break. Sometimes, it's mathematically impossible to make everyone happy and keep the rules.

This paper introduces a new solution called MenuNet. Here is how it works, using simple analogies:

The Problem: The "Impossible" Lunch

Imagine a strict principal trying to assign seats.

If they try to be perfectly fair, some students get stuck at tables they hate.
If they try to be perfectly efficient (no empty seats), some students get pushed out.
If they try to stop students from lying, they often end up with empty seats or unhappy kids.

When the rules get too complicated (like having a "global limit" on how many kids can be over-capacity), the old methods fail. They either leave some kids completely out of luck or force a few kids to take the blame for the whole system's mess.

The Solution: The "Magic Menu"

Instead of the computer trying to decide exactly who sits where immediately, MenuNet acts like a personalized menu generator.

The Menu Generation (The Chef):
The system looks at the whole room (the priorities of the schools and the preferences of everyone except the specific student). It then creates a special "menu" for each student. This menu isn't a list of specific seats; it's a list of probabilities.
- Example: "Student Alice, here is your menu: There is a 70% chance you can sit at the Pizza table, a 20% chance at the Salad table, and a 10% chance you get the 'No Seat' option."
The Choice (The Student):
The student looks at their menu and picks their favorite option that is actually available. Because the menu was created without knowing what Alice specifically said she wanted (it only knew what everyone else wanted), Alice has no incentive to lie. If she lies, she doesn't change her menu; she just changes how she picks from it, which can only hurt her. This makes the system Strategy-Proof (honesty is always the best policy).
The Result:
The system then calculates the final seating based on everyone's choices. Because it uses probabilities, it can smooth out the bumps. Instead of one kid getting a terrible seat while everyone else is happy, the "bad luck" is shared. Maybe everyone gets a slightly less-than-perfect seat, but no one gets a terrible one.

How It Learns (The Training)

MenuNet is a neural network, which is like a super-smart brain that learns by trial and error.

It tries to balance three things:
1. Happiness: Getting students into schools they like.
2. Fairness: Making sure no single student is treated unfairly compared to others.
3. Efficiency: Making sure we don't waste empty seats.
The paper shows that MenuNet is really good at this balancing act. It beats the old "Random Lottery" method (which is fair but wasteful) and the old "Strict Priority" method (which is efficient but leaves some people out).

The "Global Slack" Twist

The paper focuses on a specific real-world problem: Global Capacity Slack.
Imagine a university that wants to take 1,000 students but can technically handle 1,050 if they really have to. Or a school district that wants to balance diversity but has a hard cap on total numbers.

Old systems get stuck when they hit the cap.
MenuNet treats the cap as a "soft" limit. It allows the system to slightly exceed the limit (the "slack") if it means keeping everyone happier and more fairly treated. It calculates exactly how much to "bend" the rules to minimize the pain for everyone.

The Bottom Line

The authors tested MenuNet on simulated markets ranging from small groups to thousands of students. They found that:

It is fast (it can run on a standard computer, not just supercomputers).
It is fairer than random lotteries.
It is less wasteful than strict priority systems.
Most importantly, it spreads the "unavoidable unhappiness" evenly. Instead of one kid getting the short end of the stick, everyone shares a little bit of the burden.

In short, MenuNet is a new way to organize complex matching problems (like school admissions or job placements) that accepts that perfection is impossible, but uses AI to ensure the "imperfection" is shared fairly among everyone.

Technical Summary: MenuNet

Problem Statement
In matching markets such as school choice and labor allocation, two fundamental desiderata are strategy-proofness (ensuring agents have no incentive to misreport preferences) and stability (ensuring no pair of agents can profitably deviate). While mechanisms like Deferred Acceptance (DA) achieve both in classical settings with rigid capacities, real-world applications often involve complex distributional constraints (e.g., diversity quotas, regional balance, lower quotas). Under these constraints, stable matchings are not guaranteed to exist.

Existing literature typically addresses this by relaxing stability into fairness (absence of justified envy) and non-wastefulness. However, current approaches often focus on aggregate objectives, failing to control how unavoidable instability is distributed among agents. This can lead to systemic imbalances where a small subset of agents bears the brunt of violations, causing extreme individual dissatisfaction. The core challenge is to design a strategy-proof mechanism that not only balances fairness and efficiency but also equitably partitions unavoidable instability across all agents.

Methodology: The MenuNet Framework
The authors propose MenuNet, a neural mechanism design framework that generates personalized probabilistic menus rather than direct discrete assignments. The framework operates in two stages:

Menu Generation (Leave-One-Out Construction):
- A shared neural network $F_\theta$ generates a personalized probability distribution (menu) $p_s$ for each student $s$ .
- To guarantee strategy-proofness, the network employs a leave-one-out architecture: the menu for student $s$ is computed using the priority matrix $U$ , capacity vector $q$ , and the preference reports of all other agents ( $V_{-s}$ ), but explicitly excludes $s$ 's own report. This ensures the menu is functionally independent of the student's own strategy.
Structured Sequential Choice:
- Given the probabilistic menu, the final assignment is realized via a sequential choice rule. Students apply to schools in their reported preference order. A school $c_j$ is assigned to student $s$ if it is available in the menu and all higher-ranked schools were unavailable.
- This construction ensures that the mechanism is strategy-proof by construction (Theorem 1), as the menu is invariant to the student's report, and the choice rule is monotonic with respect to true preferences.

Differentiable Objectives and Optimization
To handle the trade-off between fairness and non-wastefulness under global capacity constraints (specifically global capacity slack $k$ ), MenuNet decomposes stability into vector-valued quantities:

Ex-ante Envy ( $E(P)$ ): Measures justified envy intensity based on priority and utility differences.
Ex-ante Waste ( $W(P)$ ): Measures inefficiency based on potential utility gains and available slack (local and global).

The framework optimizes a composite loss function $L(P)$ comprising:

Welfare Loss: Negative average expected utility.
Feasibility Loss (K-Barrier Penalty): A smooth penalty that is linear within the slack budget $k$ and super-linear (quadratic + linear) beyond it, ensuring the global capacity constraint is respected in expectation.
Stability Loss: A weighted sum of three principles applied to the envy and waste vectors:
- Egalitarian: Minimizing the aggregate magnitude (MSE).
- Rawlsian: Minimizing the maximum dissatisfaction (approximated via log-sum-exp).
- Balanced: Minimizing the variance to prevent concentration of instability on specific agents.

Key Contributions

Strategy-Proof Neural Mechanism: Introduces a framework that guarantees strategy-proofness structurally through a leave-one-out menu generation and sequential choice rule, avoiding the need for empirical regularization or regret minimization.
Distributional Control of Instability: Shifts the design goal from eliminating instability (which is impossible under constraints) to equitably distributing it. By modeling envy and waste as vectors and optimizing for variance and Rawlsian fairness, the mechanism prevents disproportionate individual loss.
Scalability and Efficiency: The approach is computationally efficient. Once trained offline, the mechanism requires only a single forward pass for any new market instance, scaling linearly with market size and remaining tractable on standard CPUs.

Experimental Results
The authors evaluate MenuNet against Random Serial Dictatorship (RSD) and Deferred Acceptance (DA) under global capacity slack constraints across market sizes ranging from 100 to 2,000 students.

Performance Trade-off: MenuNet consistently achieves a superior trade-off between fairness and non-wastefulness. It attains lower envy than RSD and lower waste than DA.
Distribution of Instability: Crucially, MenuNet distributes unavoidable dissatisfaction more evenly across the agent population, significantly reducing the variance and maximum envy/waste compared to baselines.
Feasibility: The mechanism respects the global capacity slack budget with high precision, with only negligible deviations in a small subset of instances.
Computational Efficiency: Training is feasible on CPUs (approx. 10 minutes for 1,000 students), and inference is instantaneous, demonstrating practical applicability without specialized hardware.

Significance and Claims
The paper claims that MenuNet provides a flexible and scalable paradigm for mechanism design in highly constrained, real-world environments. By leveraging learning-based menu mechanisms, it offers a principled way to navigate the inherent tension between competing axioms (fairness, efficiency, and feasibility). The authors position this work as a step toward handling complex distributional constraints where traditional stable matching mechanisms fail, offering a solution that balances system-wide objectives while protecting individual agents from disproportionate harm.

Future Directions
The authors modestly suggest future work in comparing MenuNet against specialized strategy-proof mechanisms for structured constraints (e.g., $M^\natural$ -convexity), designing more expressive neural architectures, and extending the framework to richer classes of multi-dimensional distributional constraints.