PROPm Allocations of Indivisible Goods to Multiple Agents
Authors: Artem Baklanov, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin
IJCAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the classic problem of fairly allocating a set of indivisible goods among a group of agents, and focus on the notion of approximate proportionality known as PROPm. Prior work showed that there exists an allocation that satisfies this notion of fairness for instances involving up to five agents, but fell short of proving that this is true in general. We extend this result to show that a PROPm allocation is guaranteed to exist for all instances, independent of the number of agents or goods. Our proof is constructive, providing an algorithm that computes such an allocation and, unlike prior work, the running time of this algorithm is polynomial in both the number of agents and the number of goods. |
| Researcher Affiliation | Academia | 1HSE University, Russian Federation 2Columbia University 3Drexel University |
| Pseudocode | Yes | As the pseudocode of Algorithm 1 shows, the decomposition process works in a sequence of (up to) n iterations, indexed by t {1, 2, . . . , n}. |
| Open Source Code | No | The paper does not provide any statement or link indicating the availability of open-source code. |
| Open Datasets | No | The paper is theoretical and does not describe experiments using datasets, thus no information on dataset availability or access is provided. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments using datasets, thus no information on training/validation/test splits is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with specific hyperparameters or system-level training settings. |