ELC Seminar (C01)
Date: August 28(FRI), 2015
Time: 16:30 - 17:30
Place: CELC Seminar room (Rm.404)

Speaker: Prof. Peter Bro Miltersen (Aarhus University, Denmark)
Title: A dictatorship theorem for cake cutting
Abstract:
We consider discrete protocols for the classical Steinhaus cake cutting problem. 
Under mild technical conditions, we show that any deterministic strategy-proof protocol 
for two agents in the standard Robertson-Webb query model is dictatorial, 
that is, there is a fixed agent to which the protocol allocates the entire cake. 
For n > 2 agents, a similar impossibility holds, namely there always exists an agent 
that gets the empty piece (i.e. no cake). 
In contrast, we exhibit randomized protocols that are truthful in expectation 
and compute approximately fair allocations.

Joint work with Simina Branzei, appearing at IJCAI'15