Improving Nash Social Welfare Approximations

Jugal Garg, Peter McGlaughlinIJCAI 2019 · DOI

TL;DR

This paper tackles the challenge of fairly dividing indivisible goods among agents, aiming to achieve multiple fairness criteria simultaneously. The authors introduce a novel algorithm that provides a strong approximation for Nash Social Welfare (NSW), Proportionality (Prop-1), Maximin Share (MMS), and Pareto Optimality (PO) – a combination that was previously unattainable.

What Problem Does This Paper Address?

The fair division of indivisible goods is a long-standing problem with various proposed fairness notions. Among these, Nash Social Welfare (NSW) is particularly appealing because a "max NSW" allocation (one that maximizes the geometric mean of agents' valuations) often satisfies multiple other desirable fairness properties, including envy-freeness, proportionality, and Pareto optimality. However, finding an exact max NSW allocation for indivisible goods is computationally hard (APX-hard). Existing approximation algorithms typically focus on optimizing only the NSW objective, falling short of the comprehensive fairness guarantees offered by a true max NSW allocation. This leaves a gap between the ideal and the practical. This paper aims to bridge that gap by developing an algorithm that achieves strong approximations for NSW and several other key fairness criteria simultaneously.

Methods

The core of the paper's approach lies in a market-based interpretation of fractional allocations. They leverage the concept of a "spending restricted (SR) equilibrium," which is a fractional allocation of goods and a corresponding price vector derived from a linear Fisher market. The key idea is to use this fractional equilibrium as a starting point and then devise a clever rounding scheme to transform it into an integral allocation (where goods are assigned whole).

The algorithm, named ALG, proceeds in several steps:

  1. Initialization: Assigns empty bundles to all agents.
  2. Tree Structure: Exploits the property that SR equilibria can be represented as a forest (a collection of trees) based on agent spending.
  3. Leaf Assignment: Assigns goods at the "leaves" of these trees to their parent agents.
  4. Low-Priced Goods: Assigns goods with prices below a certain threshold (1/2) to their parent agents.
  5. High-Priced Goods: For goods with higher prices, it strategically cuts edges to simplify the tree structure, ensuring that agents only receive goods they value highly relative to their price.
  6. Recursive Rounding: A recursive process is used to assign the remaining goods within each tree, carefully selecting agents based on their current bundle values and ensuring they can meet their Prop-1 guarantee.

This rounding scheme is designed to preserve as many of the desirable fairness properties as possible from the initial fractional equilibrium.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm design and analysis, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • The "Unreasonable" Fairness of Max NSW: The paper reinforces the idea that max NSW allocations are remarkably fair, simultaneously satisfying multiple, sometimes conflicting, criteria.
  • Market Equilibrium as a Foundation: Using a fractional market equilibrium (SR equilibrium) provides a powerful starting point for designing algorithms that achieve multiple fairness goals. The prices in this market offer crucial insights into how to balance different agents' needs.
  • Strategic Rounding is Key: The challenge isn't just finding a fractional fair allocation, but effectively rounding it to an integral one while preserving fairness. The paper's novel rounding scheme is central to its success.
  • Trade-offs and Approximations: Since exact solutions are often impossible for indivisible goods, the paper highlights the importance of finding algorithms that offer strong approximations across multiple fairness metrics.

Key Results

The paper presents an algorithm (ALG) that, in strongly polynomial time, yields an integral allocation that is:

  • 2-approximate for Nash Social Welfare (NSW): The NSW of the allocated bundle is at least half of the optimal NSW.
  • Prop-1: Each agent receives a bundle that is proportional after potentially adding one more good.
  • 1/(2n)-approximate for Maximin Share (MMS): Each agent receives a bundle worth at least 1/(2n) times their maximin share.
  • Pareto Optimal (PO): No agent can be made better off without making another agent worse off.

The authors also provide counterexamples to demonstrate that previous algorithms, while achieving some of these properties, fail to achieve this specific combination of guarantees simultaneously.

Limitations and Future Work

  • Approximation Factors: While the algorithm achieves strong guarantees, the approximation factors (e.g., 2 for NSW, 1/(2n) for MMS) could potentially be improved.
  • Envy-Freeness: The paper's algorithm does not guarantee envy-freeness (where agents do not envy others' bundles). A significant future direction is to improve the approximation to meet envy-freeness guarantees.
  • Constant Factor NSW and MMS: The authors suggest exploring algorithms that can achieve a constant factor approximation for both NSW and MMS simultaneously, which would be a further step towards ideal fairness.

Summary updated

BibTeX
@inproceedings{garg2019improving,
  author = {Jugal Garg and Peter McGlaughlin},
  title = {{Improving Nash Social Welfare Approximations}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/42},
}
Figure