EconCS Seminar

 

Lecturer: 

Noam Manaker Morag (HUJI)

Title: 

Truthful-in-Expectation Mechanisms for MMS Approximation

Abstract: 

How can we fairly divide a set of m indivisible goods among n self-interested agents 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 a prior work with Moshe Babaioff (EC2025), 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 low bound 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 focus on the approach of using randomized mechanisms, which rely on random "coin-tosses" when deciding on the allocation. We seek to design mechanisms that are truthful-in-expectation (TIE) and, additionally, obtain strong fairness guarantees in every realized outcome. Previously, the best-known TIE mechanism guaranteed only a 1/n fraction of the MMS. In our research, we introduce new randomized mechanisms that exponentially improve this ex-post fairness guarantee:

First, a purely ordinal TIE mechanism that achieves 1/log(n)-MMS ex-post, which is nearly optimal for any ordinal mechanism. Second, an approximately TIE mechanism that improves this guarantee to 1/loglog(n)-MMS. Finally, for the two-agent case, a TIE mechanism that achieves 2/3-MMS ex-post. Crucially, all of these mechanisms run in polynomial time and guarantee proportionality ex-ante. Thus we provides strategic "Best-of-Both-Worlds" results: agents are guaranteed fairness in expectation before the coin is flipped, and a strong approximation of their MMS share after the goods are distributed.

Joint work with Uriel Feige and Moshe Babaioff.

Link to arxiv: https://arxiv.org/abs/2604.27211

Location: 

Room 130, Feldman Building, Edmond J. Safra Campus.

Click here to add the EconCS Seminar to your Google Calendar