Almost Envy-Free Allocations with Connected Bundles

Vittorio Bilò, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco (), Dominik Peters (), Cosimo Vinci () and William Zwicker
Additional contact information
Vittorio Bilò: Università del Salento = University of Salento [Lecce]
Ioannis Caragiannis: CTI - Computer Technology Institute - Computer Technology Institute
Michele Flammini: GSSI - Gran Sasso Science Institute
Ayumi Igarashi: NII - National Institute of Informatics
Gianpiero Monaco: DI - Dipartimento di Informatica [Italy] - UNIVAQ - Università degli Studi dell'Aquila = University of L'Aquila = Université de L'Aquila
Dominik Peters: LAMSADE - Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision - Université Paris Dauphine-PSL - PSL - Université Paris Sciences et Lettres - CNRS - Centre National de la Recherche Scientifique
Cosimo Vinci: UNISA - Università degli Studi di Salerno = University of Salerno
William Zwicker: Union College

Post-Print from HAL

Abstract: We study the existence of allocations of indivisible goods that are envy-free up to one good (EF1), under the additional constraint that each bundle needs to be connected in an underlying item graph. If the graph is a path and the utility functions are monotonic over bundles, we show the existence of EF1 allocations for at most four agents, and the existence of EF2 allocations for any number of agents; our proofs involve discrete analogues of the Stromquist's moving-knife protocol and the Su-Simmons argument based on Sperner's lemma. For identical utilities, we provide a polynomial-time algorithm that computes an EF1 allocation for any number of agents. For the case of two agents, we characterize the class of graphs that guarantee the existence of EF1 allocations as those whose biconnected components are arranged in a path; this property can be checked in linear time.

Keywords: Envy-free Division; Cake-cutting; Resource Allocation (search for similar items in EconPapers)
Date: 2021-11-26
New Economics Papers: this item is included in nep-des and nep-upt
Note: View the original document on HAL open archive server: https://hal.science/hal-03834506v1
References: View references in EconPapers View complete reference list from CitEc
Citations:

Published in Games and Economic Behavior, 2021, 131, pp.197-221. ⟨10.1016/j.geb.2021.11.006⟩

Downloads: (external link)
https://hal.science/hal-03834506v1/document (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-03834506

DOI: 10.1016/j.geb.2021.11.006

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().