On Existence of Truthful Fair Cake Cutting Mechanisms (Biaoshuai Tao)

Abstract

We study the fairdivision problem on divisible heterogeneous resources (the cake cuttingproblem) with strategic agents, where each agent can manipulate his/her privatevaluation in order to receive a better allocation. A (direct-revelation)mechanism takes agents' reported valuations as input, and outputs an allocationthat satisfies a given fairness requirement. A natural and fundamental openproblem, first raised by Chen et al. and subsequently raised by Procaccia, Azizand Ye, Branzei and Miltersen, Menon and Larson, Bei et al., etc., is whetherthere exists a deterministic, truthful and envy-free (or even proportional)cake cutting mechanism. In this paper, we resolve this open problem by provingthat there does not exist a deterministic, truthful and proportional cakecutting mechanism, even in the special case where all of the followings hold:

  • there are only twoagents;
  • each agent's valuationis a piecewise-constant function;
  • each agent is hungry:each agent has a strictly positive value on any part of the cake.

The impossibilityresult extends to the case where the mechanism is allowed to leave some part ofthe cake unallocated.

To circumvent thisimpossibility result, we aim to design mechanisms that possess certain degreeof truthfulness. Motivated by the kind of truthfulness possessed by theclassical I-cut-you-choose protocol, we define a weaker notion of truthfulness:the risk-averse truthfulness. We show that the well-known moving-knifeprocedure and Even-Paz algorithm do not have this truthful property. We proposea mechanism that is risk-averse truthful and envy-free, and a mechanism that isrisk-averse truthful and proportional that always outputs allocations withconnected pieces.

Time

2021-06-19  09:30-10:00   

Speaker

Biaoshuai Tao, ShanghaiJiao Tong University

Room

Guangdong Hotel Shanghai