New Fairness Concepts for Allocating Indivisible Items
Authors: Ioannis Caragiannis, Jugal Garg, Nidhi Rathi, Eklavya Sharma, Giovanna Varricchio
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main result is a polynomial-time algorithm that computes an EEFX (and, hence, MXS) allocation in any fair division instance. Our analysis exploits several key ideas from the fair division literature, such as the concept of ordered instances, which are typically used in the design of approximation algorithms for MMS since the work of Bouveret and Lemaître [2016], the envy cycle elimination algorithm of Lipton et al. [2004], and the fact that applying this algorithm on ordered instances results in EFX allocations, observed independently by Plaut and Roughgarden [2020] and Barman and Krishnamurthy [2020]. |
| Researcher Affiliation | Academia | 1Aarhus University, Aarhus, Denmark 2University of Illinois, Urbana-Champaign, USA 3Goethe University Frankfurt, Frankfurt am Main, Germany |
| Pseudocode | Yes | Algorithm 1 Computing EEFX allocations |
| Open Source Code | No | The paper describes theoretical results and algorithms and does not provide any statement or link indicating that source code for the described methodology is publicly available. |
| Open Datasets | No | The paper is theoretical and does not involve empirical studies with datasets; therefore, it does not provide concrete access information for a publicly available or open dataset for training. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical studies with datasets; therefore, it does not provide specific dataset split information for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithms and proofs; it does not describe any specific hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies with version numbers needed to replicate any experimental results. |
| Experiment Setup | No | The paper describes theoretical results and algorithms and does not include details about an experimental setup, hyperparameters, or system-level training settings as it does not conduct experiments. |