Reachability of Fair Allocations via Sequential Exchanges
Authors: Ayumi Igarashi, Naoyuki Kamiyama, Warut Suksompong, Sheung Man Yuen
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that two EF1 allocations may not be reachable from each other even in the case of two agents, and deciding their reachability is PSPACE-complete in general. On the other hand, we prove that reachability is guaranteed for two agents with identical or binary utilities as well as for any number of agents with identical binary utilities. |
| Researcher Affiliation | Academia | Ayumi Igarashi1, Naoyuki Kamiyama2, Warut Suksompong3, Sheung Man Yuen3 1University of Tokyo 2Kyushu University 3National University of Singapore |
| Pseudocode | No | The paper describes algorithms in prose and through proofs but does not include any clearly labeled pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | The paper conducts theoretical research and does not use datasets for training, validation, or testing. |
| Dataset Splits | No | The paper conducts theoretical research and does not use datasets, therefore no training/test/validation splits are provided. |
| Hardware Specification | No | The paper describes theoretical work and does not mention any hardware used for experiments. |
| Software Dependencies | No | The paper describes theoretical work and does not mention specific software dependencies with version numbers. |
| Experiment Setup | No | The paper focuses on theoretical proofs and complexity analysis; thus, it does not describe an experimental setup with hyperparameters or training configurations. |