Research Repository

Maximum Nash welfare and other stories about EFX

Amanatidis, Georgios and Birmpas, Georgios and Filos-Ratsikas, Aris and Hollender, Alexandros and Voudouris, Alexandros A (2021) 'Maximum Nash welfare and other stories about EFX.' Theoretical Computer Science, 863. 69 - 85. ISSN 0304-3975

[img] Text
2001.09838.pdf - Accepted Version
Restricted to Repository staff only until 9 February 2022.
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (288kB)

Abstract

We consider the classic problem of fairly allocating indivisible goods among agents with additive valuation functions and explore the connection between two prominent fairness notions: maximum Nash welfare (MNW) and envy-freeness up to any good (EFX). We establish that an MNW allocation is always EFX as long as there are at most two possible values for the goods, whereas this implication is no longer true for three or more distinct values. As a notable consequence, this proves the existence of EFX allocations for these restricted valuation functions. While the efficient computation of an MNW allocation for two possible values remains an open problem, we present a novel algorithm for directly constructing EFX allocations in this setting. Finally, we study the question of whether an MNW allocation implies any EFX guarantee for general additive valuation functions under a natural new interpretation of approximate EFX allocations.

Item Type: Article
Uncontrolled Keywords: Fair division, Nash welfare, EFX, Approximation
Divisions: Faculty of Science and Health > Computer Science and Electronic Engineering, School of
Faculty of Science and Health > Mathematical Sciences, Department of
Depositing User: Elements
Date Deposited: 30 Mar 2021 10:09
Last Modified: 30 Mar 2021 10:09
URI: http://repository.essex.ac.uk/id/eprint/29751

Actions (login required)

View Item View Item