License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2021.68
URN: urn:nbn:de:0030-drops-155011
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15501/
Go to the corresponding LIPIcs Volume Portal

Asano, Takao

Simple Envy-Free and Truthful Mechanisms for Cake Cutting with a Small Number of Cuts

pdf-format:
LIPIcs-ISAAC-2021-68.pdf (0.7 MB)

Abstract

For the cake-cutting problem, Alijani, et al. [Reza Alijani et al., 2017; Masoud Seddighin et al., 2019] and Asano and Umeda [Takao Asano and Hiroyuki Umeda, 2020; Takao Asano and Hiroyuki Umeda, 2020] gave envy-free and truthful mechanisms with a small number of cuts, where the desired part of each player’s valuation function is a single interval on a given cake. In this paper, we give envy-free and truthful mechanisms with a small number of cuts, which are much simpler than those proposed by Alijani, et al. [Reza Alijani et al., 2017; Masoud Seddighin et al., 2019] and Asano and Umeda [Takao Asano and Hiroyuki Umeda, 2020; Takao Asano and Hiroyuki Umeda, 2020]. Furthermore, we show that this approach can be applied to the envy-free and truthful mechanism proposed by Chen, et al. [Yiling Chen et al., 2013], where the valuation function of each player is more general and piecewise uniform. Thus, we can obtain an envy-free and truthful mechanism with a small number of cuts even if the valuation function of each player is piecewise uniform, which solves the future problem posed by Alijani, et al. [Reza Alijani et al., 2017; Masoud Seddighin et al., 2019].

BibTeX - Entry

@InProceedings{asano:LIPIcs.ISAAC.2021.68,
  author =	{Asano, Takao},
  title =	{{Simple Envy-Free and Truthful Mechanisms for Cake Cutting with a Small Number of Cuts}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{68:1--68:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15501},
  URN =		{urn:nbn:de:0030-drops-155011},
  doi =		{10.4230/LIPIcs.ISAAC.2021.68},
  annote =	{Keywords: cake-cutting problem, envy-freeness, fairness, truthfulness, mechanism design}
}

Keywords: cake-cutting problem, envy-freeness, fairness, truthfulness, mechanism design
Collection: 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Issue Date: 2021
Date of publication: 30.11.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI