Maximum Nash Welfare and Other Stories About EFX
Authors: Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, Alexandros A. Voudouris
IJCAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | 1University of Essex 2University of Amsterdam 3Sapienza University of Rome 4University of Oxford 5University of Liverpool |
| Pseudocode | Yes | Algorithm 1 MATCH&FREEZE(N, M, (vi)i N) |
| Open Source Code | No | The paper does not provide any concrete access to source code for the methodology described. |
| Open Datasets | No | The paper does not use or refer to any publicly available or open datasets for training or evaluation. The examples used (e.g., 'g1 g2 g3 agent 1 1 ε 1 1 + ε') are illustrative and not real-world datasets. |
| Dataset Splits | No | The paper does not describe any training, validation, or test dataset splits, as it focuses on theoretical proofs and algorithm design rather than empirical evaluation on specific datasets. |
| Hardware Specification | No | The paper is theoretical and does not report on any experiments that would require specific hardware for computation. Therefore, no hardware specifications are provided. |
| Software Dependencies | No | The paper describes algorithms and proves theoretical results. It does not mention any specific software dependencies with version numbers needed to replicate experimental results, as no empirical experiments are reported. |
| Experiment Setup | No | The paper is theoretical, presenting algorithms and proofs. It does not include an experimental setup section with specific hyperparameters, training configurations, or system-level settings, as no empirical experiments are detailed. |