Fair and Efficient Allocations under Subadditive Valuations

Bhaskar Ray Chaudhury, Jugal Garg, Ruta Mehta

Abstract

We study the problem of allocating a set of indivisible goods among agents with subadditive valuations in a fair and efficient manner. Envy-Freeness up to any good (EFX) is considered the most compelling fairness notion for indivisible goods, yet its existence for more than two agents remains an open question. This paper introduces a polynomial-time algorithm that achieves an $O(n)$ approximation to the Nash welfare—a significant improvement over previous $O(n \log n)$ and $O(m)$ bounds—while simultaneously ensuring approximate EFX fairness. Our results extend to a broad family of $p$-mean welfare measures, bridging the gap between fairness and efficiency in complex valuation settings.

Introduction

The fair division of indivisible resources is a fundamental problem in multi-agent systems. Two primary objectives often guide these allocations: fairness, typically captured by Envy-Freeness up to any good (EFX), and efficiency, often measured by the Nash Welfare (the geometric mean of utilities).

While these concepts are well-understood for additive valuations, real-world preferences are often subadditive. In subadditive settings, the value of a set of items is less than or equal to the sum of the values of its individual components (e.g., the marginal utility of a second car is lower than the first). Prior to this work, algorithms usually optimized for either fairness or efficiency, but rarely both, especially for subadditive preferences. This paper provides a breakthrough by offering the first polynomial-time algorithm to provide strong simultaneous guarantees for both.

The Algorithmic Framework

The authors propose a clever two-phase algorithmic framework to balance the competing needs of welfare and fairness.

Phase 1: Identifying Anchor Goods

The algorithm first focuses on "high-valued" goods. It constructs a complete bipartite graph between agents and goods where edge weights are carefully defined based on the desired welfare measure. For instance, when optimizing for Nash welfare, the weights involve logarithmic transformations of the valuations. By finding an optimal matching in this graph, the algorithm assigns each agent a single "anchor" good. This initial step is crucial; it ensures that every agent receives a baseline level of utility that is sufficient to meet the $O(n)$ efficiency bound, regardless of how the remaining items are distributed.

Phase 2: Fair Distribution of Remaining Goods

With the anchor goods assigned, the algorithm employs existing EFX-finding procedures (such as those developed by Plaut & Roughgarden or Chaudhury et al.) to distribute the remaining items. The "secret sauce" of this framework lies in how the Phase 1 weights are calibrated to interact with the fairness properties of Phase 2. The authors realized that the main barrier to efficiency in fair division is often "singleton" bundles—agents who receive only one very valuable item. By getting the allocation of these high-value items right first via matching, they can afford to be less precise with the remaining items while still hitting the $O(n)$ target.

Key Insights

  • The Power of the Anchor: The strategy of prioritizing high-value items through matching allows the algorithm to bypass the complexities of subadditive valuations for the bulk of the welfare calculation. By securing one high-value item per agent, the algorithm establishes a welfare floor.
  • Fairness as a Tool for Efficiency: Interestingly, the authors use the properties of EFX—specifically, the bounds on how much utility an agent must have relative to others' bundles—to prove the lower bounds on the total welfare achieved by their algorithm. This demonstrates a synergistic relationship between fairness and efficiency.
  • Unifying Welfare Measures: The paper doesn't just solve for Nash Welfare ($p=0$). It addresses a whole family of $p$-mean welfare measures, including max-min welfare ($p=-\infty$) and social welfare ($p=1$).

Key Results

  • Efficiency Gains: The algorithm achieves an $O(n)$ approximation to the maximum Nash welfare. This is a significant improvement over the previous best-known bounds of $O(n \log n)$ for submodular valuations and $O(m)$ for subadditive valuations.
  • Fairness Guarantees: The algorithm outputs an allocation that is either $(\frac{1}{2} - \epsilon)$-EFX or $(1 - \epsilon)$-EFX with bounded charity.
  • Polynomial Time: The entire process runs in polynomial time relative to the number of agents ($n$) and goods ($m$), making it computationally feasible for practical applications.
  • Asymptotic Match: For the specific case of max-min welfare ($p = -\infty$), the $O(n)$ ratio matches the best-known approximation while adding the EFX fairness property.

Conclusion and Future Directions

This work establishes a new state-of-the-art for fair and efficient allocation under subadditive valuations. However, several open questions remain. While $O(n)$ is a significant improvement, it remains a linear approximation; determining if a constant-factor approximation (independent of the number of agents) is possible is a major open problem. Additionally, the existence of an exact EFX allocation for more than two agents with subadditive valuations remains one of the most prominent unsolved challenges in the field of discrete fair division.

Summary updated

Abstract

We study the problem of allocating a set of indivisible goods among agents with subadditive valuations in a fair and efficient manner. Envy-Freeness up to any good (EFX) is the most compelling notion of fairness in the context of indivisible goods. Although the existence of EFX is not known beyond the simple case of two agents with subadditive valuations, some good approximations of EFX are known to exist, namely $\tfrac{1}{2}$-EFX allocation and EFX allocations with bounded charity. Nash welfare (the geometric mean of agents' valuations) is one of the most commonly used measures of efficiency. In case of additive valuations, an allocation that maximizes Nash welfare also satisfies fairness properties like Envy-Free up to one good (EF1). Although there is substantial work on approximating Nash welfare when agents have additive valuations, very little is known when agents have subadditive valuations. In this paper, we design a polynomial-time algorithm that outputs an allocation that satisfies either of the two approximations of EFX as well as achieves an $\mathcal{O}(n)$ approximation to the Nash welfare. Our result also improves the current best-known approximation of $\mathcal{O}(n \log n)$ and $\mathcal{O}(m)$ to Nash welfare when agents have submodular and subadditive valuations, respectively. Furthermore, our technique also gives an $\mathcal{O}(n)$ approximation to a family of welfare measures, $p$-mean of valuations for $p\in (-\infty, 1]$, thereby also matching asymptotically the current best known approximation ratio for special cases like $p =-\infty$ while also retaining the fairness properties.
BibTeX
@inproceedings{chaudhury2021fair,
  author = {Bhaskar Ray Chaudhury and Jugal Garg and Ruta Mehta},
  title = {{Fair and Efficient Allocations under Subadditive Valuations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=5m05iVC8Ls},
}
Figure