Almost Full EFX Exists for Four Agents
Authors: Ben Berger, Avi Cohen, Michal Feldman, Amos Fiat4826-4833
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We develop new techniques that allow us to push the boundaries of the enigmatic EFX problem beyond these known results, and (arguably) to simplify proofs of earlier results. Our main result is that every setting with 4 additive agents admits an EFX allocation that leaves at most a single item unallocated. To prove Theorem 1, we show that for any EFX allocation with at least two unallocated items, it is possible to reshuffle bundles and reallocate them in such a way that advances the lexicographic potential function and preserves EFX. The proof requires solving a complex puzzle, and exemplifies the extensive use of our new techniques. |
| Researcher Affiliation | Academia | Tel Aviv University benberger1@tauex.tau.ac.il, avicohen2@mail.tau.ac.il, michal.feldman@cs.tau.ac.il, fiat@tau.ac.il |
| Pseudocode | No | The paper describes conceptual steps and definitions related to graph theory and allocations, but it does not include any formal pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide an explicit statement or a link to open-source code for the methodology described. It refers to a full version on arXiv, which typically contains the paper itself, not source code. |
| Open Datasets | No | This is a theoretical paper focused on mathematical proofs and algorithms. It does not involve datasets, training, or data availability. |
| Dataset Splits | No | This is a theoretical paper focused on mathematical proofs and algorithms. It does not involve validation datasets or data splits. |
| Hardware Specification | No | This is a theoretical paper focused on mathematical proofs and algorithms. It does not describe any computational experiments that would require specific hardware, thus no hardware specifications are mentioned. |
| Software Dependencies | No | This is a theoretical paper focused on mathematical proofs and algorithms. It does not describe any computational experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper focused on mathematical proofs and algorithms. It does not describe an experimental setup with hyperparameters or training configurations in the empirical sense. |