2018-09-11
An improved envy-free cake cutting protocol for four agents
Publication
Publication
We consider the classic cake-cutting problem of producing envy-free allocations, restricted to the case of four agents. The problem asks for a partition of the cake to four agents, so that every agent finds her piece at least as valuable as every other agent’s piece. The problem has had an interesting history so far. Although the case of three agents is solvable with less than 15 queries, for four agents no bounded procedure was known until the recent breakthroughs of Aziz and Mackenzie [2, 3]. The main drawback of these new algorithms, however, is that they are quite complicated and with a very high query complexity. With four agents, the number of queries required is close to 600. In this work we provide an improved algorithm for four agents, which reduces the current complexity by a factor of 3.4. Our algorithm builds on the approach of [3] by incorporating new insights and simplifying several steps. Overall, this yields an easier to grasp procedure with lower complexity.
| Additional Metadata | |
|---|---|
| doi.org/10.1007/978-3-319-99660-8_9 | |
| Lecture Notes in Computer Science | |
| International Symposium on Algorithmic Game Theory | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Amanatidis, G., Christodoulou, G., Fearnley, J., Markakis, V., Psomas, C.-A., & Vakaliou, E. (2018). An improved envy-free cake cutting protocol for four agents. In Proceedings of International Symposium on Algorithmic Game Theory (pp. 87–99). doi:10.1007/978-3-319-99660-8_9 |
|
