Fairly Allocating Goods and (Terrible) Chores
Authors: Hadi Hosseini, Aghaheybat Mammadov, Tomasz Wąs
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | By identifying a class of instances with terrible chores, we show that determining the existence of an EFX allocation is NP-complete. This result immediately implies the intractability of EFX under additive preferences. Nonetheless, we propose a natural subclass of lexicographic preferences for which an EFX and Pareto optimal (PO) allocation is guaranteed to exist and can be computed efficiently. |
| Researcher Affiliation | Academia | Hadi Hosseini , Aghaheybat Mammadov and Tomasz W as Pennsylvania State University {hadi, mammadovagha, twas}@psu.edu |
| Pseudocode | Yes | Algorithm 1 Finding an EFX and PO allocation for separable lexicographic preferences |
| Open Source Code | No | The paper does not provide an unambiguous statement or a direct link for open-source code for the described methodology. |
| Open Datasets | No | This is a theoretical paper and does not use datasets for training or evaluation. |
| Dataset Splits | No | This is a theoretical paper and does not involve data splitting for validation. |
| Hardware Specification | No | This is a theoretical paper and does not describe computational experiments that would require hardware specifications. |
| Software Dependencies | No | This is a theoretical paper and does not mention specific software dependencies with version numbers for experimental replication. |
| Experiment Setup | No | This is a theoretical paper and does not describe experimental setups with hyperparameters or training configurations. |