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.

Maximum Nash Welfare and Other Stories About EFX / Amanatidis, Georgios; Birmpas, Georgios; Filos-Ratsikas, Aris; Hollender, Alexandros; Voudouris, Alexandros A.. - In: IJCAI. - ISSN 1045-0823. - (2020), pp. 24-30. (Intervento presentato al convegno International Joint Conference on Artificial Intelligence (IJCAI-20) tenutosi a Yokohama; Japan (Virtual)) [10.24963/ijcai.2020/4].

Maximum Nash Welfare and Other Stories About EFX

Amanatidis, Georgios
;
Birmpas, Georgios
;
2020

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.
2020
International Joint Conference on Artificial Intelligence (IJCAI-20)
Agent-based Systems; Multi-agent Systems; Computational Social Choice; Economic Paradigms; Auctions and Market-Based Systems
04 Pubblicazione in atti di convegno::04c Atto di convegno in rivista
Maximum Nash Welfare and Other Stories About EFX / Amanatidis, Georgios; Birmpas, Georgios; Filos-Ratsikas, Aris; Hollender, Alexandros; Voudouris, Alexandros A.. - In: IJCAI. - ISSN 1045-0823. - (2020), pp. 24-30. (Intervento presentato al convegno International Joint Conference on Artificial Intelligence (IJCAI-20) tenutosi a Yokohama; Japan (Virtual)) [10.24963/ijcai.2020/4].
File allegati a questo prodotto
File Dimensione Formato  
Amanatidis_Maximum_2020.pdf

accesso aperto

Note: https://doi.org/10.24963/ijcai.2020/4
Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 159.26 kB
Formato Adobe PDF
159.26 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1504572
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 16
social impact