Fair and Efficient Allocations under Subadditive Valuations

Bhaskar Ray Chaudhury, Jugal Garg, Ruta Mehta

Abstract

The problem of allocating indivisible goods among agents with subadditive valuations presents a significant challenge in balancing fairness and efficiency. While Envy-Freeness up to any good (EFX) is a premier fairness notion, its existence remains an open question for subadditive valuations. This paper introduces a polynomial-time algorithm that achieves an $O(n)$ approximation to the Nash welfare—improving upon existing $O(n \log n)$ and $O(m)$ bounds—while simultaneously ensuring strong fairness guarantees, specifically $1/2$-EFX or EFX with bounded charity.

Introduction

Fair division involves partitioning a set of items among agents such that the resulting allocation is both equitable and efficient. When goods are indivisible, achieving perfect fairness (like Envy-Freeness) is often impossible. Instead, researchers focus on relaxations such as Envy-Freeness up to any good (EFX), where no agent envies another after the removal of any single item from the other's bundle.

Efficiency is typically measured through Nash Welfare—the geometric mean of agents' valuations—which provides a natural balance between total utility and distributive justice. While significant progress has been made for additive valuations, subadditive valuations—where the value of a bundle is at most the sum of its parts—remain a difficult frontier in the field of algorithmic game theory.

The Challenge of Subadditive Valuations

Subadditive valuations are highly expressive, capturing "complement-freeness" (e.g., a pair of shoes is not worth more than the sum of the individual shoes). However, this flexibility makes optimization difficult. Previous algorithms often struggled to provide simultaneous guarantees; they could achieve fairness or efficiency, but rarely both. Specifically, for subadditive preferences, the best-known efficiency approximations were $O(m)$ (where $m$ is the number of goods), which scales poorly as the number of items grows relative to the number of agents.

The Two-Phase Algorithmic Approach

The authors propose a novel two-phase framework that bridges the gap between welfare and fairness by ensuring that fairness-seeking reallocations do not undermine a baseline level of efficiency.

Phase 1: Strategic Pre-allocation

The primary hurdle in previous fairness-focused algorithms was the "singleton barrier"—agents were often left with a single, low-value item, causing the Nash welfare to plummet. To counter this, the algorithm first identifies "high-valued" goods for each agent. It constructs a complete bipartite graph where edges represent the potential utility an agent derives from a specific good, adjusted by a baseline of remaining low-value goods. By finding an optimal matching, the algorithm ensures every agent receives an "anchor" good, establishing a welfare floor.

Phase 2: Fairness Refinement

With the anchor goods secured, the algorithm transitions to a fairness-seeking phase. It employs a modified version of EFX-approximation algorithms to redistribute the remaining goods. The critical technical insight is the proof that these fairness-driven moves do not degrade the welfare established in Phase 1. Even if an agent's bundle changes during this phase, its new value is guaranteed to be at least as high as the value of their initial anchor item.

Key Results and Contributions

The proposed algorithm yields several landmark results for the field of fair division:

  1. Improved Efficiency: The algorithm provides an $O(n)$ approximation to the maximum Nash welfare. This is a substantial improvement over the previous best-known ratios of $O(n \log n)$ for submodular valuations and $O(m)$ for subadditive valuations.
  2. Robust Fairness: The resulting allocation satisfies either $(1/2 - \epsilon)$-EFX or $(1 - \epsilon)$-EFX with bounded charity. In the case of bounded charity, at most $n-1$ items are left unallocated, and no agent prefers the unallocated "charity" pile to their own bundle.
  3. Computational Efficiency: The entire process runs in polynomial time, making it a computationally feasible solution even as the number of goods and agents grows.
  4. Generalized Welfare Measures: Beyond Nash welfare ($p=0$), the technique provides an $O(n)$ approximation for the entire family of $p$-mean welfares for $p \in (-\infty, 1]$. This includes social welfare ($p=1$) and max-min welfare ($p \to -\infty$), matching the best-known asymptotic results for those specific cases while adding fairness guarantees.

Conclusion

This work demonstrates that it is possible to achieve near-optimal efficiency and strong fairness simultaneously, even under the broad class of subadditive valuations. While the $O(n)$ approximation is a major step forward, future research remains focused on achieving a constant-factor approximation and resolving the existential question of exact EFX allocations. Additionally, exploring incentive compatibility—ensuring agents have no reason to misreport their valuations—remains a vital next step for real-world implementation.

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 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 O(n) approximation to the Nash welfare. Our result also improves the current best-known approximation of O(n log n) and O(m) to Nash welfare when agents have submodular and subadditive valuations, respectively. Furthermore, our technique also gives an 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 approximation ratio for special cases like p = -\infty while also retaining the remarkable 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