Fair Division of Indivisible Goods for a Class of Concave Valuations

Bhaskar Ray Chaudhury, Yun Kuen Cheung, Jugal Garg, Naveen Garg, Martin Hoefer, Kurt Mehlhorn

TL;DR

This paper tackles the challenge of fairly and efficiently dividing indivisible goods among agents with complex valuation functions. They introduce a polynomial-time algorithm that achieves a near-optimal approximation for Nash Social Welfare (NSW), a key efficiency metric, while also providing strong fairness guarantees. This work extends existing methods for simpler valuation functions to a more general and realistic setting.

What Problem Does This Paper Address?

The core problem is how to divide a collection of items (goods) among multiple people (agents) in a way that is both "fair" and "efficient." Imagine dividing up a set of inherited furniture or assigning tasks among roommates.

  • Fairness: No one should feel significantly worse off than others. A common fairness notion is "envy-freeness," meaning no one prefers another person's share. However, for indivisible goods, perfect envy-freeness is often impossible. This paper uses a relaxation called "envy-freeness up to one good" (EF1).
  • Efficiency: The total happiness or utility generated by the allocation should be maximized. A standard measure for this is "Nash Social Welfare" (NSW), which is the geometric mean of each agent's utility. Maximizing NSW is known to be computationally hard (APX-hard).

The challenge is that agents' preferences (valuations) can be complex. This paper focuses on "Capped Additively Separable Concave" (CASC) valuations. These are more general than simple additive valuations because they capture diminishing marginal returns (each additional unit of a good is worth less than the previous one) and also have a "cap" – a maximum value an agent will derive from any bundle, regardless of how many goods it contains. This CASC model is more realistic for many scenarios but makes fair division algorithms more difficult.

Methods

The authors build upon existing algorithms for fair division, particularly the work of Barman et al. (2018) for additive valuations. Their approach involves an iterative process that adjusts prices and allocations. Key techniques include:

  • Rounding Utilities: To handle the complexity of CASC valuations, they first round agent utilities and caps to powers of a parameter r = 1 + ε. This simplifies the problem while allowing for a bounded approximation loss.
  • Ascending Price Algorithm: The algorithm iteratively increases prices for goods and adjusts allocations. This is guided by "maximum bang per buck" (MBB) ratios, which measure an agent's utility per unit of price.
  • Tight Graph and Improving Paths: They use a "tight graph" to identify potential improvements. An "improving path" in this graph represents a sequence of swaps that can increase the overall NSW or reduce envy.
  • Swap and Price Increase Operations: The algorithm repeatedly performs two types of operations:
  • Swap: Reassigning goods along an improving path to improve the allocation.
  • Price Increase: Raising prices for some goods to reduce MBB ratios and potentially resolve envy issues.
  • Invariant Maintenance: Throughout the process, they maintain key invariants related to allocation, prices, and MBB ratios to ensure the algorithm progresses correctly.

A significant contribution is adapting these techniques to handle the "capped" aspect of CASC valuations, which requires distinguishing between capped and uncapped agents and carefully managing their valuations.

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

  • Generalizing Fairness and Efficiency: The paper demonstrates that algorithms designed for simpler valuation functions can be adapted to more complex CASC valuations, achieving comparable approximation guarantees for efficiency (NSW) and strong fairness properties (EF1).
  • The Power of Rounding: Rounding utilities to powers of r is a crucial step that simplifies the problem without sacrificing too much accuracy, enabling the use of existing algorithmic tools.
  • Capped Valuations are Tricky: Introducing caps adds significant complexity. The algorithm needs to explicitly track whether an agent has reached their cap, as this affects how their valuation behaves and how they interact with the market.
  • Near-Optimal NSW is Achievable: The algorithm achieves an approximation factor of e^(1/e) ≈ 1.445 for NSW, which is the state-of-the-art for additive valuations and a significant achievement for the more general CASC setting.
  • Fairness Guarantees Hold: The computed allocation is not only efficient but also approximately envy-free up to one good (EF1), and approximately Pareto-optimal in certain cases.

Key Results

  • A polynomial-time algorithm that computes an allocation with an approximation factor of e^(1/e) ≈ 1.445 for Nash Social Welfare (NSW) for agents with CASC valuations.
  • The computed allocation is 1/(2 + γ)-EF1 (envy-free up to one good) and (1 + γ/4)-approximately Pareto-optimal (for uncapped valuations).
  • An improved approximation guarantee for NSW is shown under a "large-market" condition.
  • The paper proves that two previously established upper bounds on optimal NSW (CG-bound and BKV-bound) are equivalent.

Limitations and Future Work

  • Approximation Factor Gap: While the algorithm achieves a 1.445 approximation for NSW, there's a known lower bound of 1.069 for additive valuations. Closing this gap for additive valuations and extending it to CASC valuations is an open question.
  • Submodular Valuations: The paper mentions that for even more general "submodular" valuations, the current approximation factor is very large (380). Reducing this factor is an exciting direction for future research.
  • Best Possible Fairness: The paper shows that a factor of 2 + ε for EF1 is achievable, but it's unclear if this is the tightest possible bound.
  • Empirical Evaluation: The paper is theoretical; future work could involve implementing the algorithm and testing its performance on real-world or synthetic datasets.

Summary updated

Abstract

We study the fair and efficient allocation of a set of indivisible goods among agents, where each good has several copies, and each agent has an additively separable concave valuation function with a threshold. These valuations capture the property of diminishing marginal returns, and they are more general than the well-studied case of additive valuations. We present a polynomial-time algorithm that approximates the optimal Nash social welfare (NSW) up to a factor of e1/e ≈ 1.445. This matches with the state-of-the-art approximation factor for additive valuations. The computed allocation also satisfies the popular fairness guarantee of envy-freeness up to one good (EF1) up to a factor of 2 + ε. For instances without thresholds, it is also approximately Pareto-optimal. For instances satisfying a large market property, we show an improved approximation factor. Lastly, we show that the upper bounds on the optimal NSW introduced in Cole and Gkatzelis (2018) and Barman et al. (2018) have the same value.
BibTeX
@article{chaudhury2022fair,
  author = {Bhaskar Ray Chaudhury and Yun Kuen Cheung and Jugal Garg and Naveen Garg and Martin Hoefer and Kurt Mehlhorn},
  title = {{Fair Division of Indivisible Goods for a Class of Concave Valuations}},
  journal = {J. Artif. Intell. Res.},
  year = {2022},
  doi = {10.1613/jair.1.12911},
}
Figure