Truthful cake sharing
The classic cake cutting problem concerns the fair allocation of a heterogeneous resource among interested agents. In this paper, we study a public goods variant of the problem, where instead of competing with one another for the cake, the agents all share the same subset of the cake which must be c...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/179994 |
| _version_ | 1811681195186978816 |
|---|---|
| author | Bei, Xiaohui Lu, Xinhang Suksompong, Warut |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Bei, Xiaohui Lu, Xinhang Suksompong, Warut |
| author_sort | Bei, Xiaohui |
| collection | NTU |
| description | The classic cake cutting problem concerns the fair allocation of a heterogeneous resource among interested agents. In this paper, we study a public goods variant of the problem, where instead of competing with one another for the cake, the agents all share the same subset of the cake which must be chosen subject to a length constraint. We focus on the design of truthful and fair mechanisms in the presence of strategic agents who have piecewise uniform (i.e., approval) utilities over the cake. On the one hand, we show that the leximin solution is excludably truthful (meaning it is truthful when it can block each agent from accessing parts of the cake that the agent does not claim to desire) and moreover maximizes the guaranteed normalized egalitarian welfare among all excludably truthful and position oblivious mechanisms. On the other hand, we demonstrate that the maximum Nash welfare solution is excludably truthful for two agents (as it coincides with leximin in that case) but not in general. We also provide an impossibility result on truthfulness when blocking is not allowed, and adapt notions of representation to our setting. |
| first_indexed | 2024-10-01T03:37:05Z |
| format | Journal Article |
| id | ntu-10356/179994 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T03:37:05Z |
| publishDate | 2024 |
| record_format | dspace |
| spelling | ntu-10356/1799942024-09-09T15:34:52Z Truthful cake sharing Bei, Xiaohui Lu, Xinhang Suksompong, Warut School of Physical and Mathematical Sciences Mathematical Sciences Polynomial Approximation Resource Allocation The classic cake cutting problem concerns the fair allocation of a heterogeneous resource among interested agents. In this paper, we study a public goods variant of the problem, where instead of competing with one another for the cake, the agents all share the same subset of the cake which must be chosen subject to a length constraint. We focus on the design of truthful and fair mechanisms in the presence of strategic agents who have piecewise uniform (i.e., approval) utilities over the cake. On the one hand, we show that the leximin solution is excludably truthful (meaning it is truthful when it can block each agent from accessing parts of the cake that the agent does not claim to desire) and moreover maximizes the guaranteed normalized egalitarian welfare among all excludably truthful and position oblivious mechanisms. On the other hand, we demonstrate that the maximum Nash welfare solution is excludably truthful for two agents (as it coincides with leximin in that case) but not in general. We also provide an impossibility result on truthfulness when blocking is not allowed, and adapt notions of representation to our setting. Ministry of Education (MOE) Published version This work was partially supported by the Ministry of Education, Singapore, under its Academic Research Fund Tier 1 (RG23/20), by ARC Laureate Project FL200100204 on “Trustworthy AI”, by the Singapore Ministry of Education under grant number MOE-T2EP20221-0001, and by an NUS Start-up Grant. 2024-09-09T04:49:19Z 2024-09-09T04:49:19Z 2024 Journal Article Bei, X., Lu, X. & Suksompong, W. (2024). Truthful cake sharing. Social Choice and Welfare. https://dx.doi.org/10.1007/s00355-023-01503-0 0176-1714 https://hdl.handle.net/10356/179994 10.1007/s00355-023-01503-0 2-s2.0-85182494699 en RG23/20 MOE-T2EP20221-0001 FL200100204 Social Choice and Welfare © 2024 The Author(s). Open Access. This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/ licenses/by/4.0/. application/pdf |
| spellingShingle | Mathematical Sciences Polynomial Approximation Resource Allocation Bei, Xiaohui Lu, Xinhang Suksompong, Warut Truthful cake sharing |
| title | Truthful cake sharing |
| title_full | Truthful cake sharing |
| title_fullStr | Truthful cake sharing |
| title_full_unstemmed | Truthful cake sharing |
| title_short | Truthful cake sharing |
| title_sort | truthful cake sharing |
| topic | Mathematical Sciences Polynomial Approximation Resource Allocation |
| url | https://hdl.handle.net/10356/179994 |
| work_keys_str_mv | AT beixiaohui truthfulcakesharing AT luxinhang truthfulcakesharing AT suksompongwarut truthfulcakesharing |