Computing Pareto-Optimal and Almost Envy-Free Allocations of Indivisible Goods
Authors: Jugal Garg, Aniket Murhekar
JAIR 2024 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present a pseudo-polynomial time algorithm to compute an EF1+f PO allocation, thereby improving the earlier results. Our techniques also enable us to show that an EQ1+f PO allocation always exists when the values are positive and that it can be computed in pseudo-polynomial time. We also consider the class of k-ary instances where k is a constant, i.e., each agent has at most k different values for the goods. For such instances, we show that an EF1+f PO allocation can be computed in strongly polynomial time. Finally, on the complexity side, we show that the problem of computing an EF1+f PO allocation lies in the complexity class PLS. |
| Researcher Affiliation | Academia | Jugal Garg EMAIL University of Illinois, Urbana-Champaign Aniket Murhekar EMAIL University of Illinois, Urbana-Champaign |
| Pseudocode | Yes | Algorithm 1 Computing an EF1+f PO allocation of goods Algorithm 2 Computing an EQ1+f PO allocation of goods |
| Open Source Code | No | The paper does not provide any explicit statement about the release of source code, nor does it include any links to code repositories. |
| Open Datasets | No | The paper discusses theoretical fair division instances with agents, goods, and valuation functions (N, M, V) but does not refer to any specific, publicly available datasets used for empirical evaluation or provide access information for such datasets. |
| Dataset Splits | No | The paper is theoretical and focuses on algorithmic design and complexity analysis; it does not involve empirical experiments with specific datasets, and therefore, no dataset splits are described. |
| Hardware Specification | No | The paper is theoretical, presenting algorithms and complexity results. It does not describe any experimental setup that would involve specific hardware, such as GPUs, CPUs, or cloud resources. |
| Software Dependencies | No | The paper is theoretical, focusing on algorithmic design and complexity analysis. It does not provide details on specific software components or their version numbers used for implementation or experimentation. |
| Experiment Setup | No | The paper focuses on theoretical algorithm design and complexity analysis. It does not describe any empirical experiments, and consequently, there are no details provided regarding hyperparameter values, training configurations, or system-level settings. |