Fair allocation in graphs

Christodoulou, George ORCID: 0000-0002-9623-7461, Fiat, Amos ORCID: 0000-0002-5748-9519, Koutsoupias, Elias ORCID: 0000-0002-2226-6737 and Sgouritsa, Alkmini ORCID: 0000-0003-3997-5131 (2023) Fair allocation in graphs. In: EC '23: 24th ACM Conference on Economics and Computation.

PDF
Graph_EFX.pdf - Author Accepted Manuscript
Download (392kB) | Preview

Official URL: http://dx.doi.org/10.1145/3580507.3597764

Abstract

We study envy freeness up to any good (EFX) in settings where valuations can be represented via a graph of arbitrary size where vertices correspond to agents and edges to items. An item (edge) has zero marginal value to all agents (vertices) not incident to the edge. Each vertex may have an arbitrary monotone valuation on the set of incident edges. We first consider allocations that correspond to orientations of the edges, where we show that EFX does not always exist, and furthermore that it is NP-complete to decide whether an EFX orientation exists. Our main result is that (EFX) allocations exist for this setting. This is one of the few cases where EFX allocations are known to exist for more than 3 agents.

Item Type:	Conference or Workshop Item (Unspecified)
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	24 Jul 2023 14:25
Last Modified:	05 Sep 2023 22:48
DOI:	10.1145/3580507.3597764
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3171870