Truthful mechanism guarantees fair share of indivisible goods for agents
Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
Computer Science and Game Theory
Summary
The paper studies how to fairly divide indivisible items among people who value them differently and may act strategically. Previous work showed it’s possible to guarantee each person a fair share based only on their rankings, but that share decreases as the group grows. The authors confirm a prediction that knowing exact values lets you do better: their method ensures everyone gets at least one-seventh of their fair share, and no one envies others before the division. This method runs efficiently and uses randomness cleverly to be truthful and fair.
What this means in practice
- •For market designers: Allocate indivisible resources fairly and truthfully among strategic participants using a polynomial-time mechanism with guaranteed minimum shares.
- •For online platform engineers: Implement randomized allocation systems that ensure each user receives a guaranteed fair portion of resources based on reported preferences without incentive to lie.
Authors
Mengfan Ma, Biaoshuai Tao, Fangxiao Wang
Abstract
We study the truthful and fair allocation of indivisible goods to $n$ strategic agents with additive valuations. Babaioff, Feige, and Manaker Morag [FOCS 2026] gave a randomized mechanism that uses only the agents' rankings of the goods, is truthful in expectation (TIE), and guarantees every agent $1/(H_{n-1}+2)=Θ(1/\log n)$ of her maximin share (MMS) in every realized allocation, where $H_{n-1}$ is the $(n-1)$th harmonic number; this is nearly the best possible with rankings alone. They conjectured that cardinal information allows TIE mechanisms to achieve a constant ex-post MMS guarantee. We confirm this conjecture: our TIE mechanism guarantees every agent at least $1/7$ of her MMS in every realized allocation; moreover, the mechanism is ex-ante envy-free and can be implemented in polynomial time. Our mechanism has two key technical ingredients, both of which may be of independent interest. The first is a truthful fractional allocation rule specifying each agent's probability of receiving each good: it favors each agent on her top $n-1$ goods and reduces her probability of receiving a good for each other agent who also ranks it among her top $n-1$ goods. The second is the balanced edge coloring: we decompose these probabilities into equally likely matchings from agents to high-value goods, those that alone meet an agent's guarantee, and balance these matchings in a fine-grained way without changing any marginal probability, so that every agent who receives no high-value good can obtain sufficient value from the remaining goods without over-allocating any good.