EF1 and EFX Orientations
Authors: Argyrios Deligkas, Eduard Eiben, Tiger-Lily Goldsmith, Viktoriia Korchemna
IJCAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main result is to prove that an EF1 orientation always exists when the valuations of the agents are monotone! In fact, we prove our result for a more general model than the one from Christodoulou et al. [2023], where instead of graphs, we consider hypergraphs, i.e., the goods now correspond to hyperedges. In other words, each agent has a subset of goods that are relevant to them. We prove our result algorithmically (Theorem 1). The base of our algorithm is the well-known envy-cycle elimination algorithm [Lipton et al., 2004], although it requires two careful modifications to indeed produce an orientation. |
| Researcher Affiliation | Academia | 1Royal Holloway University of London 2TU Wien EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1 EF1 orientations for monotone valuations Input: Set of items A, set of agents N, valuations Vi, sets of relevant items Ai, i N, agent lists Na, a A Output: EF1 orientation π |
| Open Source Code | No | The paper does not contain any statement about making code publicly available, nor does it provide any links to a code repository. |
| Open Datasets | No | The paper focuses on theoretical problems and algorithmic solutions without using or referencing any specific publicly available datasets for empirical evaluation. It describes problem instances for theoretical proofs, such as "An instance of PARTITION consists of a multiset S of positive integers." |
| Dataset Splits | No | The paper does not conduct experiments on datasets; therefore, no dataset split information is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup that would require hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe any experimental setup that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup or training configurations. |