Aarhus University Seal

Almost envy-free allocations with connected bundles

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Vittorio Bilo, University of Salento, Italy
  • Ioannis Caragiannis
  • Michele Flammini, Gran Sasso Science Institute, Italy
  • Ayumi Igarashi, National Institute of Informatics, Tokyo, Japan
  • Gianpiero Monaco, University of L'Aquila, Italy
  • Dominik Peters, University of Toronto, Canada
  • Cosimo Vinci, Gran Sasso Science Institute, Italy
  • William Zwicker, Union College, United States

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.

Original languageEnglish
JournalGames and Economic Behavior
Volume131
Pages (from-to)197-221
Number of pages25
ISSN0899-8256
DOIs
Publication statusPublished - Jan 2022

    Research areas

  • Algorithmic game theory, Cake-cutting, Envy-free division, Resource allocation

See relations at Aarhus University Citationformats

ID: 229894149