Recent developments in fair division for strategic agents

22/03/2016 - 14:00
Speaker: 
Seminar: 
מיקום: 
Abstract: 

I will talk about fair division for strategic agents and will start with the cake cutting problem, which models the division of a heterogeneous divisible good among players with different preferences. Here I will talk about an impossibility result (dictatorship theorem), as well as an
algorithmic framework for strategic agents, where fair outcomes can be implemented in the equilibria of protocols.

If enough time I will also mention the problem of allocating multiple divisible goods for the fairness solution concept of Nash social welfare. When the preferences are known, this solution is achieved in the Fisher market equilibrium outcomes. However, with strategic agents the strong fairness guarantees of market equilibria can be destroyed. We find that for
additive valuations, the Fisher market approximates the NSW within a factor of 2, but for Leontief utilities the approximation degrades linearly with the number of players. Surprisingly, a mechanism known as Trading Post not only retains the constant 2-approximation of Fisher for additive utilities, but approximately implements the NSW objective for Leontief valuations: its price of anarchy is 1 + epsilon for every epsilon > 0.

This is joint work with Peter Bro Miltersen, Ioannis Caragiannis, David Kurokawa, Ariel Procaccia, Vasilis Gkatzelis, and Ruta Mehta.