Truthful-in-Expectation Mechanisms for MMS Approximation

Researchers Moshe Babaioff, Uriel Feige, and Noam Manaker Morag have published a new paper on arXiv tackling the problem of fairly allocating indivisible goods among strategic agents who value items additively. Since deterministic truthful mechanisms face impossibility results, the team turns to randomized "Truthful-in-Expectation" (TIE) mechanisms, which ensure agents are incentivized to report true valuations in expectation. The key fairness metric is the Maximin Share (MMS), representing the maximum value an agent can guarantee themselves when partitioning items.

Their first result is an ordinal TIE mechanism that guarantees each agent at least 1/(H_n + 2) of their MMS ex-post, where H_n is the n-th harmonic number (roughly ln n). This is nearly best possible for ordinal mechanisms, as even non-truthful ordinal algorithms cannot exceed 1/H_n. By incorporating a small amount of cardinal information (e.g., agent valuations for a few items), the team improves the ex-post guarantee to Ω(1/log log n)-MMS, at the cost of relaxing truthfulness to (1-ε(n))-TIE for negligible ε(n). For the two-agent case, they achieve 2/3-MMS ex-post, which is best possible for the truncated proportional share (TPS), a metric at least as strong as MMS. All mechanisms run in polynomial time and are ex-ante proportional, offering "Best-of-Both-Worlds" guarantees.