Envy-Free and Pareto-Optimal Allocations for Agents with Asymmetric Random Valuations
Authors: Yushi Bai, Paul Gölz
IJCAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In Section 5, we empirically evaluate how many items are needed to guarantee envy-free and Pareto-optimal allocations for a fixed collection of agents. We find that the approximate multiplier algorithm needs relatively large numbers of items to ensure envy-freeness; that the round robin algorithm violates Pareto-optimality in almost all instances; and that the Maximum Nash Welfare (MNW) algorithm achieves both axioms already for few items but that its running time limits its applicability. |
| Researcher Affiliation | Academia | 1Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China 2Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA |
| Pseudocode | Yes | Algorithm 1: Equalizing Multipliers |
| Open Source Code | No | No statement or link providing access to the source code for the methodology described in this paper was found. |
| Open Datasets | No | The paper describes using a 'set of ten agents with utility distributions from a simple parametric family of (0.1, 1.9)-PDF-bounded distributions' in its empirical evaluation, implying simulated data rather than a publicly available dataset with a specific link or citation. |
| Dataset Splits | No | The paper does not provide specific training/validation/test dataset splits. The empirical section uses randomly generated utility distributions and instances for evaluation, not a fixed dataset that would require such splits. |
| Hardware Specification | No | The paper vaguely mentions 'on consumer hardware' for runtime, but does not provide specific hardware details such as GPU or CPU models, or memory specifications. |
| Software Dependencies | No | The paper mentions using the 'optimization library BARON' but does not specify its version number or any other software dependencies with version numbers. |
| Experiment Setup | Yes | For a requested accuracy of δ = 10 5, our algorithm runs in 30 seconds on consumer hardware, and we verify analytically that the resulting multipliers indeed lie within this tolerance, undisturbed by numerical inaccuracies in the computation. |