## 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.

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.

Originalsprog | Engelsk |
---|---|

Titel | Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems , AAMAS '13 |

Redaktører | Maria Gini, Onn Shehory |

Antal sider | 8 |

Forlag | Association for Computing Machinery |

Publikationsdato | 1 apr. 2013 |

Sider | 327-334 |

ISBN (Trykt) | 978-1-4503-1993-5 |

Status | Udgivet - 1 apr. 2013 |

Begivenhed | International Conference on Autonomous Agents and Multiagent Systems - St Paul, USA Varighed: 6 maj 2013 → 10 maj 2013 |

### Konference

Konference | International Conference on Autonomous Agents and Multiagent Systems |
---|---|

Land/Område | USA |

By | St Paul |

Periode | 06/05/2013 → 10/05/2013 |