Finding Fair Allocations under Budget Constraints
Authors: Siddharth Barman, Arindam Khan, Sudarshan Shyam, K. V. N. Sreenivas
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We make notable progress towards this by proposing a simple, greedy, polynomial-time algorithm that computes EF2 allocations under budget constraints. Our algorithmic result implies the universal existence of EF2 allocations in this fair division context. The analysis of the algorithm exploits intricate structural properties of envy-freeness. Interestingly, the same algorithm also provides EF1 guarantees for important special cases. Specifically, we settle the existence of EF1 allocations for instances in which: (i) the value of each good is proportional to its size, (ii) all goods have the same size, or (iii) all the goods have the same value. Our EF2 result extends to the setting wherein the goods sizes are agent specific. |
| Researcher Affiliation | Academia | 1Department of Computer Science and Automation, Indian Institute of Science, Bangalore 2Department of Computer Science, Aarhus University |
| Pseudocode | Yes | Algorithm 1: Densest Greedy |
| Open Source Code | No | The paper references a full version on arXiv (Barman et al. 2022) but does not contain an explicit statement about releasing source code for the methodology or provide a direct link to a code repository. |
| Open Datasets | No | This is a theoretical paper, focusing on algorithm design and mathematical proofs. It does not involve empirical training on datasets, and therefore no dataset availability is mentioned. |
| Dataset Splits | No | This is a theoretical paper and does not involve empirical experimentation with data. Therefore, it does not describe dataset splits for training, validation, or testing. |
| Hardware Specification | No | This is a theoretical paper. No hardware specifications are mentioned as there are no empirical experiments performed. |
| Software Dependencies | No | This is a theoretical paper focused on algorithm design and proofs. There is no mention of specific software dependencies with version numbers required to replicate any experiments. |
| Experiment Setup | No | This is a theoretical paper. It describes an algorithm and its analysis but does not detail an experimental setup with hyperparameters or system-level training settings. |