Pushing the Frontier on Approximate EFX Allocations

29^th October 2024, 13:00 Ashton Lecture Theatre
Aris Filos-Ratsikas
University of Edinburgh

Abstract

We study the problem of allocating a set of indivisible goods to a set of agents with additive valuation functions, aiming to achieve approximate envy-freeness up to any good (α-EFX). The state-of-the-art results on the problem include that (exact) EFX allocations exist when (a) there are at most three agents, or (b) the agents' valuation functions can take at most two values, or (c) the agents' valuation functions can be represented via a graph. For α-EFX, it is known that a 0.618-EFX allocation exists for any number of agents with additive valuation functions. In this work we show that 2/3-EFX allocations exist when (a) there are at most seven agents, (b) the agents' valuation functions can take at most three values, or (c) the agents' valuation functions can be represented via a multigraph. Our results can be interpreted in two ways. First, by relaxing the notion of EFX to 2/3-EFX, we obtain existence results for strict generalizations of the settings for which exact EFX allocations are known to exist. Secondly, by imposing restrictions on the setting, we manage to beat the barrier of 0.618 and achieve an approximation guarantee of 2/3. Therefore, our results push the frontier of existence and computation of approximate EFX allocations, and provide insights into the challenges of settling the existence of exact EFX allocations.

Biography

Aris is a Lecturer at the University of Edinburgh. His research lies in the intersection of theoretical computer science and artificial intelligence, with an emphasis on algorithms and computational complexity. In particular, he is interested in problems related to social choice theory, fair division, competitive markets, game theory and mechanism design. He obtained his PhD degree from the Computer Science Department of Aarhus University, Denmark in 2015, under the supervision of Peter Bro Miltersen. In the past, he was a Lecturer at the University of Liverpool, a postdoctoral researcher at École polytechnique fédérale de Lausanne, and a postdoctoral research assistant at the University of Oxford.

Additional Materials

• https://arxiv.org/abs/2406.12413