Abstract | ||
---|---|---|
Cake cutting is a fundamental model in fair division; it represents the problem of fairly allocating a heterogeneous divisible good among agents with different preferences. The central criteria of fairness are proportionality and envy-freeness, and many of the existing protocols are designed to guarantee proportional or envy-free allocations, when the participating agents follow the protocol. However, typically, all agents following the protocol is not guaranteed to result in a Nash equilibrium. In this paper, we initiate the study of equilibria of classical cake cutting protocols. We consider one of the simplest and most elegant continuous algorithms -- the Dubins-Spanier procedure, which guarantees a proportional allocation of the cake -- and study its equilibria when the agents use simple threshold strategies. We show that given a cake cutting instance with strictly positive value density functions, every envy-free allocation of the cake can be mapped to a pure Nash equilibrium of the corresponding moving knife game. Moreover, every pure Nash equilibrium of the moving knife game induces an envy-free allocation of the cake. In addition, the moving knife game has an epsilon-equilibrium which is epsilon-envy-free, allocates the entire cake, and is independent of the tie-breaking rule. |
Year | DOI | Venue |
---|---|---|
2013 | 10.5555/2484920.2484974 | AAMAS |
Keywords | Field | DocType |
envy-free allocation,existing protocol,classical cake,equilibrium analysis,proportional allocation,knife game,dubins-spanier procedure,pure nash equilibrium,nash equilibrium,entire cake,cake cutting,game theory,fair division | Mathematical optimization,Fair division,Computer science,Proportionality (mathematics),Game theory,Zero-sum game,Nash equilibrium,Distributed computing | Conference |
Citations | PageRank | References |
3 | 0.43 | 7 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Simina Brânzei | 1 | 85 | 14.77 |
Peter Bro Miltersen | 2 | 1146 | 94.49 |