How can we fairly divide a set of m indivisible goods among n self-interested agents with additive valuations who might lie about their preferences? This fundamental problem sits at the intersection of mechanism design and fair division. While compelling fairness benchmarks like the Maximin Share (MMS) are approximately achievable algorithmically, severe impossibility results arise in the strategic setting. In particular, in prior work with Noam Manaker Morag (EC 2025), we showed that the best MMS approximation achievable by deterministic mechanisms that are truthful, non-bossy, and neutral is a mere O(1/m). This poor guarantee is matched by a trivial mechanism: letting every agent but the last pick exactly one good, and giving all remaining goods to the last agent.
In this talk, we seek to design randomized mechanisms that are truthful-in-expectation (TIE) while also obtaining strong fairness guarantees in every realized outcome. Previously, the best-known TIE mechanism guaranteed only a 1/n-fraction of each agent's MMS ex-post. We present new randomized mechanisms that dramatically improve the MMS approximation: first, an ordinal TIE mechanism guaranteeing about 1/log n-MMS ex-post, which is nearly optimal for ordinal mechanisms; second, a mechanism that slightly relaxes truthfulness-in-expectation and improves the guarantee to Ω(1/log log n)-MMS; and finally, for two agents, a TIE mechanism guaranteeing 2/3-MMS ex-post. All these mechanisms run in polynomial time and are ex-ante proportional. Thus, they provide strategic "Best-of-Both-Worlds" results: proportionality in expectation, together with strong MMS guarantees in every realized allocation.
Bio: Prof. Moshe Babaioff is an Associate Professor in the School of Computer Science and Engineering at the Hebrew University of Jerusalem and a member of the Federmann Center for the Study of Rationality. His research lies at the intersection of theoretical computer science, game theory, and economics, with interests including algorithmic game theory, mechanism design, auction theory, and fairness. Prior to joining the Hebrew University, he was a Senior Principal Researcher at Microsoft Research. He received his Ph.D. from the Hebrew University of Jerusalem under the supervision of Prof. Noam Nisan.
