Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee

M Ma, B Tao, F Wang - arXiv preprint arXiv:2609.35670, 2026 - arxiv.org
arXiv preprint arXiv:2609.35670, 2026•arxiv.org
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)=\Theta (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 …
We study the truthful and fair allocation of indivisible goods to 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 of her maximin share (MMS) in every realized allocation, where is the 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 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 goods and reduces her probability of receiving a good for each other agent who also ranks it among her top 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.
arxiv.org