Connected Equitable Cake Division via Sperner's Lemma
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912160220708864 |
|---|---|
| author | Bhaskar, Umang Sricharan, A. R. Vaish, Rohit |
| author_facet | Bhaskar, Umang Sricharan, A. R. Vaish, Rohit |
| contents | We study the problem of fair cake-cutting where each agent receives a connected piece of the cake. A division of the cake is deemed fair if it is equitable, which means that all agents derive the same value from their assigned piece. Prior work has established the existence of a connected equitable division for agents with nonnegative valuations using various techniques. We provide a simple proof of this result using Sperner's lemma. Our proof extends known existence results for connected equitable divisions to significantly more general classes of valuations, including nonnegative valuations with externalities, as well as several interesting subclasses of general (possibly negative) valuations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_13340 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Connected Equitable Cake Division via Sperner's Lemma Bhaskar, Umang Sricharan, A. R. Vaish, Rohit Computer Science and Game Theory We study the problem of fair cake-cutting where each agent receives a connected piece of the cake. A division of the cake is deemed fair if it is equitable, which means that all agents derive the same value from their assigned piece. Prior work has established the existence of a connected equitable division for agents with nonnegative valuations using various techniques. We provide a simple proof of this result using Sperner's lemma. Our proof extends known existence results for connected equitable divisions to significantly more general classes of valuations, including nonnegative valuations with externalities, as well as several interesting subclasses of general (possibly negative) valuations. |
| title | Connected Equitable Cake Division via Sperner's Lemma |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2412.13340 |