almost envy free allocations with connected bundles

• DOI: 10.4230/lipics.itcs.2019.14
• Publication Date: 2022-01-01
• Authors: Vittorio Bilò; Ioannis Caragiannis; Michele Flammini; Ayumi Igarashi; Gianpiero Monaco; Dominik Peters; Cosimo Vinci; William S. Zwicker
• Keywords: [INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI]; FOS: Computer and information sciences; [INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO]; Algorithmic game theory, Cake-cutting, Envy-free division, Resource allocation; 02 engineering and technology; Cake-cutting; Resource Allocation; FOS: Economics and business; Computer Science - Computer Science and Game Theory; Economics - Theoretical Economics; 0202 electrical engineering, electronic engineering, information engineering; Resource allocation; [SHS.ECO] Humanities and Social Sciences/Economics and Finance; Envy-free Division, Cake-cutting, Resource Allocation, Algorithmic Game Theory; Envy-free Division; Cake-cutting; Resource Allocation; Algorithmic Game Theory; Algorithmic Game Theory; Envy-free Division; Envy-free division; 004; Algorithmic game theory; [INFO.INFO-GT] Computer Science [cs]/Computer Science and Game Theory [cs.GT]; Theoretical Economics (econ.TH); [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC]; [INFO.INFO-MA] Computer Science [cs]/Multiagent Systems [cs.MA]; ddc:004; Algorithmic game theory; Cake-cutting; Envy-free division; Resource allocation; Computer Science and Game Theory (cs.GT)

Accepted journal version<br/>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.<br/>