Envy-Free and Pareto-Optimal Allocations for Asymmetric Agents

Yushi Bai, Paul GölzarXiv 2021 · arXiv · OpenReview

Abstract

We study the problem of allocating $m$ indivisible items to $n$ agents with additive utilities. It is desirable for the allocation to be both fair and efficient, which we formalize through the notions of envy-freeness and Pareto-optimality. While envy-free and Pareto-optimal allocations may not exist for arbitrary utility profiles, previous work has shown that such allocations exist with high probability assuming that all agents' values for all items are independently drawn from a common distribution. In this paper, we consider a generalization of this model where each agent's utilities are drawn independently from a distribution specific to the agent. We show that envy-free and Pareto-optimal allocations are likely to exist in this asymmetric model when $m=\Omega\left(n\log n\right)$, which is tight up to a log log gap that also remains open in the symmetric subsetting. Furthermore, these guarantees can be achieved by a polynomial-time algorithm.

Introduction

In fair division, the simultaneous achievement of Envy-Freeness (EF)—where no agent prefers another's bundle—and Pareto-Optimality (PO)—where no agent can be made better off without harming another—is a primary objective. While these properties are not guaranteed to exist for indivisible items in the worst case, they often emerge in average-case scenarios where utilities are drawn from random distributions.

Existing literature has largely focused on the symmetric model, where all agents share the same utility distribution. This paper extends these guarantees to the more realistic asymmetric model, where agents possess unique utility distributions, reflecting diverse tastes and value scales.

The Multiplier Allocation Method

The core approach introduced is the Multiplier Allocation. In a standard welfare-maximizing allocation, items are given to the agent with the highest raw utility ($u_i$). While Pareto-optimal, this often leads to envy if one agent has naturally higher value scales. To counter this, the authors assign a multiplier ($\beta_i$) to each agent, allocating items based on the highest weighted value ($\beta_i \cdot u_i$).

Using topological tools like Sperner’s Lemma, the authors prove that a set of multipliers always exists such that every agent has an equal $1/n$ probability of winning any item. They provide a polynomial-time algorithm that iteratively adjusts these multipliers to achieve this statistical balance, ensuring that as the number of items $m$ grows, actual utilities concentrate around their expected values, satisfying envy-freeness.

Theoretical Results

The paper establishes that EF+PO allocations are likely to exist in the asymmetric model when $m = \Omega(n \log n)$. This result is significant because it matches the best-known bounds for the simpler symmetric case, effectively closing the gap between the two models for large item counts.

Comparison of existence results for EF and PO allocations in symmetric vs. asymmetric models.

As shown in the theoretical landscape above, the asymmetric model results (Sections 3 and 4) successfully extend the existence guarantees of EF and PO from the symmetric model across the same complexity thresholds for $m$.

Empirical Evaluation

To validate these findings, the authors tested the multiplier algorithm against standard benchmarks like Round Robin and Maximum Nash Welfare (MNW) using heterogeneous Beta and Peak distributions.

Experimental results demonstrate a clear trade-off. While the Round Robin algorithm achieves envy-freeness with fewer items, its probability of maintaining Pareto-optimality drops to zero as the number of items increases. In contrast, the multiplier-based allocation is inherently Pareto-optimal and becomes reliably envy-free as $m$ approaches approximately 2,000 for a 10-agent system.

Conclusion and Limitations

This work proves that fairness and efficiency are compatible even under heterogeneous preferences. However, the "high probability" guarantee requires a relatively large number of items ($m$) to take effect. Additionally, the current proof assumes utility distributions have interval support and that item values are independent. Future research may explore discrete utility values or correlated preferences where an agent's value for an item depends on their current bundle.

Summary updated

Abstract

We study the problem of allocating $m$ indivisible items to $n$ agents with additive utilities. It is desirable for the allocation to be both fair and efficient, which we formalize through the notions of envy-freeness and Pareto-optimality. While envy-free and Pareto-optimal allocations may not exist for arbitrary utility profiles, previous work has shown that such allocations exist with high probability assuming that all agents' values for all items are independently drawn from a common distribution. In this paper, we consider a generalization of this model where each agent's utilities are drawn independently from a distribution specific to the agent. We show that envy-free and Pareto-optimal allocations are likely to exist in this asymmetric model when $m=\Omega\left(n\log n\right)$, which is tight up to a log log gap that also remains open in the symmetric subsetting. Furthermore, these guarantees can be achieved by a polynomial-time algorithm.
BibTeX
@misc{bai2021envy,
  author = {Yushi Bai and Paul Gölz},
  title = {{Envy-Free and Pareto-Optimal Allocations for Asymmetric Agents}},
  year = {2021},
  eprint = {2109.08971},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2109.08971},
}
Figure