On the Pursuit of EFX for Chores: Non-existence and Approximations
Authors: Vasilis Christoforidis, Christodoulos Santorinaios
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We resolve this question by providing a negative answer for the latter, presenting a simple construction that admits no EFX solutions for allocating six items to three agents equipped with superadditive cost functions, thus proving a separation result between goods and bads. In fact, we uncover a deeper insight, showing that the instance has unbounded approximation ratio. Moreover, we show that deciding whether an EFX allocation exists is NP-complete. On the positive side, we establish the existence of EFX allocations under general monotone cost functions when the number of items is at most n+2. We then shift our attention to additive cost functions. We employ a general framework in order to improve the approximation guarantees in the well-studied case of three additive agents, and provide several conditional approximation bounds that leverage ordinal information. |
| Researcher Affiliation | Academia | Vasilis Christoforidis1,2 and Christodoulos Santorinaios1,3 1Archimedes / Athena RC 2Aristotle University of Thessaloniki 3Athens University of Economics and Business |
| Pseudocode | Yes | Algorithm 1 Top trading envy cycle elimination algorithm, Algorithm 2 Chore approximation framework, Algorithm 3 Top n 1 disagreement |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described in this paper. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments on datasets, thus no information on publicly available datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments with data splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require specific hardware, thus no hardware specifications are provided. |
| Software Dependencies | No | The paper does not provide specific ancillary software details with version numbers that would be needed to replicate experiments. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training configurations. |