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.2022.55
URN: urn:nbn:de:0030-drops-173402
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17340/
Go to the corresponding LIPIcs Volume Portal

Kobayashi, Yusuke ; Mahara, Ryoga

Proportional Allocation of Indivisible Goods up to the Least Valued Good on Average

pdf-format:
LIPIcs-ISAAC-2022-55.pdf (0.8 MB)

Abstract

We study the problem of fairly allocating a set of indivisible goods to multiple agents and focus on the proportionality, which is one of the classical fairness notions. Since proportional allocations do not always exist when goods are indivisible, approximate notions of proportionality have been considered in the previous work. Among them, proportionality up to the maximin good (PROPm) has been the best approximate notion of proportionality that can be achieved for all instances. In this paper, we introduce the notion of proportionality up to the least valued good on average (PROPavg), which is a stronger notion than PROPm, and show that a PROPavg allocation always exists. Our results establish PROPavg as a notable non-trivial fairness notion that can be achieved for all instances. Our proof is constructive, and based on a new technique that generalizes the cut-and-choose protocol.

BibTeX - Entry

@InProceedings{kobayashi_et_al:LIPIcs.ISAAC.2022.55,
  author =	{Kobayashi, Yusuke and Mahara, Ryoga},
  title =	{{Proportional Allocation of Indivisible Goods up to the Least Valued Good on Average}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{55:1--55:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17340},
  URN =		{urn:nbn:de:0030-drops-173402},
  doi =		{10.4230/LIPIcs.ISAAC.2022.55},
  annote =	{Keywords: Discrete Fair Division, Indivisible Goods, Proportionality}
}

Keywords: Discrete Fair Division, Indivisible Goods, Proportionality
Collection: 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Issue Date: 2022
Date of publication: 14.12.2022

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