On existence of truthful fair cake cutting mechanisms

• Published in: Artificial intelligence 2023-06, Vol.319, p.103904, Article 103904
• Main Authors: Bu, Xiaolin, Song, Jiaxin, Tao, Biaoshuai
• Format: Article
• Language: English
• Subjects: Cake cutting; Fair division; Mechanism design; Truthful
• ISSN: 0004-3702; 1872-7921
• DOI: 10.1016/j.artint.2023.103904

We study the fair division problem on divisible heterogeneous resources (the cake cutting problem) with strategic agents, where each agent can manipulate his/her private valuation to receive a better allocation. A (direct-revelation) mechanism takes agents' reported valuations as input and outputs an allocation that satisfies a given fairness requirement. A natural and fundamental open problem, first raised by Chen, Lai, Parkes, and Procaccia [1] and subsequently raised in reference [2–7], etc., is whether there exists a deterministic, truthful, and envy-free (or even proportional) cake cutting mechanism. In this paper, we resolve this open problem by proving that there does not exist a deterministic, truthful and proportional cake cutting mechanism, even in the special case where all of the following hold:•there are only two agents;•each agent's valuation is a piecewise-constant function;•each agent is hungry: each agent has a strictly positive value on any part of the cake. The impossibility result extends to the case where the mechanism is allowed to leave some part of the cake unallocated. We also present a truthful and envy-free mechanism when each agent's valuation is piecewise-constant and monotone. However, if we require Pareto-optimality, we show that truthful is incompatible with approximate proportionality for any positive approximation ratio even for piecewise-constant and monotone value density functions. To circumvent the main impossibility result, we aim to design mechanisms that possess a certain degree of truthfulness. Motivated by the kind of truthfulness possessed by the classical I-cut-you-choose protocol, we propose a weaker notion of truthfulness, the proportional risk-averse truthfulness. We show that the well-known moving-knife (Dubins-Spanier) procedure and Even-Paz algorithm do not have this truthful property. We propose a mechanism that is proportionally risk-averse truthful and envy-free, and a mechanism that is proportionally risk-averse truthful that always outputs allocations with connected pieces.