Approximating Nash Social Welfare Under Binary XOS and Binary Subadditive Valuations

Siddharth Barman, Paritosh Verma

Introduction

Fair division is a fundamental problem in computational social choice, concerning the allocation of indivisible goods among agents with diverse preferences. A central challenge is identifying an allocation that is both efficient and fair. The Nash Social Welfare (NSW)—defined as the geometric mean of the agents' valuations—serves as a "Goldilocks" metric for this purpose. It effectively balances the extremes of Social Welfare (maximizing total value) and Egalitarian Welfare (maximizing the value of the least-off agent).

While NSW is well-understood for simple additive valuations, it becomes computationally difficult as agent preferences grow more complex. This paper investigates two broad classes of complement-free valuations: XOS and Subadditive. Specifically, the authors focus on "binary" versions of these valuations, where the marginal value of any item is either 0 or 1. The research aims to determine if these binary properties make the otherwise intractable general cases computationally accessible.

The Computational Challenge

In general XOS settings, the best possible approximation for NSW is linear in the number of agents, which is often considered a poor result for large systems. This research explores whether the restriction to binary marginals allows for a constant-factor approximation.

Furthermore, the paper addresses the distinction between XOS and subadditive valuations. While all XOS functions are subadditive, the converse is not true. The authors seek to understand if this structural difference impacts the feasibility of fair division under binary constraints.

Algorithmic Framework for Binary XOS

The authors propose a polynomial-time algorithm, Algorithm 1 (ALG), which utilizes a value oracle—a mechanism that returns an agent's valuation for any given bundle. The algorithm iteratively updates allocations to maintain specific invariants:

  1. Envy Bounding: It ensures that for every agent $i$, their value for their own bundle is at least half of their value for a specific set of goods $G_i$. This set includes unallocated goods and goods held by agents with significantly larger bundles, effectively bounding "multiplicative envy."
  2. Non-wastefulness: The algorithm maintains an invariant where an agent's valuation of their bundle is equal to the number of items in it, ensuring no "junk" items are assigned.
  3. Greedy-like Increments: If an agent is found to be suboptimal, the algorithm identifies a more valuable bundle within $G_i$, doubling their value and reallocating items from other agents as necessary.

Key Results and the Structural Divide

The paper establishes several landmark results in the field of fair division:

  • NSW Approximation: The authors provide the first polynomial-time 288-approximation for binary XOS valuations.
  • Simultaneous Guarantees: Beyond NSW, the algorithm provides a 5.83-approximation for Social Welfare and a 1/6-approximation for the Groupwise Maximin Share (GMMS) guarantee, suggesting that a single allocation can satisfy multiple definitions of fairness and efficiency.
  • Hardness of XOS: The authors prove that maximizing NSW under binary XOS is APX-hard, meaning it is NP-hard to achieve an approximation better than 1.0042.
  • The Subadditive Barrier: A major contribution is the discovery of a sharp structural divide. While binary XOS allows for a constant-factor approximation, binary subadditive valuations require an exponential number of queries to achieve any approximation better than $n^{1-\epsilon}$. This highlights that XOS functions possess a much more useful structure for fair division than general subadditive functions, even when both are restricted to binary marginals.

Conclusion and Future Work

This work clarifies the boundaries of tractability for Nash Social Welfare. By demonstrating that binary XOS valuations allow for constant-factor approximations while binary subadditive valuations do not, the authors provide a new understanding of the relationship between valuation classes and fair division.

Future research directions include extending these results to asymmetric NSW, where agents have different weights or entitlements, and exploring $p$-mean welfare generalizations. Additionally, the authors suggest investigating whether the use of demand oracles—which are more powerful than value oracles—could bypass the lower bounds established for subadditive valuations.

Summary updated

Abstract

We study the problem of allocating indivisible goods among agents in a fair and economically efficient manner. In this context, the Nash social welfare—defined as the geometric mean of agents’ valuations for their assigned bundles—stands as a fundamental measure that quantifies the extent of fairness of an allocation. Focusing on instances in which the agents’ valuations have binary marginals, we develop essentially tight results for (approximately) maximizing Nash social welfare under two of the most general classes of complement-free valuations, i.e., under binary XOS and binary subadditive valuations. For binary XOS valuations, we develop a polynomial-time algorithm that finds a constant-factor (specifically 288) approximation for the optimal Nash social welfare, in the standard value-oracle model. The allocations computed by our algorithm also achieve constant-factor approximation for social welfare and the groupwise maximin share guarantee. These results imply that—in the case of binary XOS valuations—there necessarily exists an allocation that simultaneously satisfies multiple (approximate) fairness and efficiency criteria. We complement the algorithmic result by proving that Nash social welfare maximization is APX-hard under binary XOS valuations. Furthermore, this work establishes an interesting separation between the binary XOS and binary subadditive settings. In particular, we prove that an exponential number of value queries are necessarily required to obtain even a sub-linear approximation for Nash social welfare under binary subadditive valuations.
BibTeX
@misc{barman2021approximating,
  author = {Siddharth Barman and Paritosh Verma},
  title = {{Approximating Nash Social Welfare Under Binary XOS and Binary Subadditive Valuations}},
  year = {2021},
  eprint = {2106.02656},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2106.02656},
}
Figure