Cake Cutting - Envy and Truth
Time: 14:00 - 15:00, April 24, Tuesday
Place: Room 850, 8th floor, ICT, CAS
Speaker: Xiaohui Bei, Nanyang Technological University
Abstract:
Cake cutting is a classic resource allocation problem in which a central decision maker divides and allocates a divisible and heterogeneous good, known as a cake, to a set of agents with individual valuation functions, with the goal of balancing efficiency and fairness. Despite its seemingly simple setting, the problem compasses rich structures and has been a central topic in resource allocation for many decades.
In this talk, I will give an overview of some recent research on this topic. In particular, I will take a game-theoretic viewpoint and discuss the challenge of designing envy-free cake cutting algorithms that are immune to manipulation. Among other things, I will present a truthful envy-free mechanism for cake cutting with two agents that does not rely on the commonly assumed free-disposal assumption, and I will complement this result by showing that such a mechanism does not exist when certain additional assumptions are made.
Bio:
Xiaohui Bei is currently an Assistant Professor at Nanyang Technological University (NTU) in Singapore. He got his Ph.D. from Tsinghua University at Beijing in 2012. Then he spent two years as a research fellow at NTU, and one year as a researcher at Max Planck Institute for Informatics. His research interests include topics in computational economics, resource allocation and general algorithm design.