Truthful fair division without free disposal
- PDF / 2,285,532 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 71 Downloads / 146 Views
Truthful fair division without free disposal Xiaohui Bei1 · Guangda Huzhang1 · Warut Suksompong2 Received: 16 August 2019 / Accepted: 15 April 2020 © The Author(s) 2020
Abstract We study the problem of fairly dividing a heterogeneous resource, commonly known as cake cutting and chore division, in the presence of strategic agents. While a number of results in this setting have been established in previous works, they rely crucially on the free disposal assumption, meaning that the mechanism is allowed to throw away part of the resource at no cost. In the present work, we remove this assumption and focus on mechanisms that always allocate the entire resource. We exhibit a truthful and envy-free mechanism for cake cutting and chore division for two agents with piecewise uniform valuations, and we complement our result by showing that such a mechanism does not exist when certain additional constraints are imposed on the mechanisms. Moreover, we provide bounds on the efficiency of mechanisms satisfying various properties, and give truthful mechanisms for multiple agents with restricted classes of valuations.
1 Introduction Given a heterogeneous divisible resource and a set of interested agents with potentially differing valuations on different parts of the resource, how can we allocate the resource to the agents in such a way that all agents perceive the resulting allocation as fair? The resource is often modeled as a cake in the literature, and the problem, which therefore commonly goes by the name of cake cutting, has occupied the minds of mathematicians, computer scientists, economists, and political scientists alike for the past seventy years (Brams and Taylor 1996; Moulin 2004; Procaccia 2016; Robertson and Webb 1998; Steinhaus 1948). Cake in the cake cutting problem is used to represent a desirable resource; all agents wish to maximize the amount of resource that they receive. In contrast, the dual problem to cake cutting, known as chore division, aims to allocate an undesirable resource to the agents, with every agent wanting to receive as little of the resource as possible. Though several * Warut Suksompong [email protected] 1
Nanyang Technological University, Singapore, Singapore
2
University of Oxford, Oxford, UK
13
Vol.:(0123456789)
X. Bei et al.
algorithms for cake cutting also apply to chore division, the theoretical properties of the two problems differ in many cases, and much less work has been done on chore division than on cake cutting (Dehghani et al. 2018; Farhadi and Hajiaghayi 2018; Heydrich and van Stee 2015; Peterson and Su 1998, 2002). Perhaps the simplest and most well-known fair division protocol is the cut-andchoose protocol, which works for both cake cutting and chore division with two agents. The protocol operates by letting the first agent divide the resource into two parts that she values equally, and letting the second agent choose the part that she prefers. The resulting allocation is always envy-free—each agent likes her part at least as much as the other agent
Data Loading...
