On Fair and Efficient Allocations of Indivisible Public Goods

Jugal Garg, Pooja Kulkarni, Aniket Murhekar

Introduction

Fair division is a cornerstone of microeconomic theory, traditionally focusing on the allocation of private goods—resources where consumption by one individual precludes consumption by another. However, many societal resources, such as public libraries, parks, or infrastructure, are public goods, which can be enjoyed simultaneously by multiple agents. This paper investigates the fair allocation of indivisible public goods, where a community must select a subset of $k$ items from $m$ available options to satisfy $n$ agents with diverse preferences.

The Model Hierarchy

A central contribution of this work is establishing a formal relationship between three distinct allocation models: PrivateGoods, PublicGoods, and PublicDecisions. Through polynomial-time reductions, the authors demonstrate that the PublicGoods model occupies a middle ground in terms of complexity and generality.

The hierarchy of MNW problems across different resource models.

As shown in the reduction chain for Maximum Nash Welfare (MNW), solving the public goods problem is at least as difficult as the private goods case, but no more difficult than the general public decision-making problem. This formal bridge allows researchers to translate insights across different domains of social choice theory.

Computational Complexity and the "Complexity Jump"

While private goods allocation with binary valuations (where agents either like or dislike an item) is computationally efficient (in P), the transition to public goods introduces a significant "complexity jump."

Computational complexity of finding fair allocations across different settings.

The authors prove that finding MNW or leximin-optimal allocations for public goods is NP-hard even under the simplest constraints, such as binary valuations or having only two agents. This hardness highlights a fundamental mathematical difference in how public goods aggregate utility across a population compared to the additive nature of private goods.

Fairness and Efficiency Guarantees

Despite the computational challenges, the paper shows that the Maximum Nash Welfare (MNW) and leximin mechanisms remain powerful tools for public goods.

  • MNW Allocations: By maximizing the product of agents' utilities, MNW allocations are proven to satisfy Pareto Optimality (PO) and a refined version of Proportionality up to one good (Prop1). In the public goods context, Prop1 is defined as the utility an agent would receive if they could swap one selected good for their most preferred unselected good.
  • Leximin Allocations: These maximize the utility of the worst-off agent, then the second worst-off, and so on. These allocations provide even stronger guarantees, satisfying the Round-Robin Share (RRS), Prop1, and PO.

Algorithmic Solutions

To address the NP-hardness of the problem, the authors propose several algorithmic strategies:

  1. Pseudo-polynomial Time Algorithms: Using dynamic programming, exact solutions can be found in $O(m \cdot (mV)^t)$ time, where $t$ is the number of agent types and $V$ is the maximum valuation. This makes the problem tractable when the population consists of a few distinct groups (e.g., students vs. faculty).
  2. Approximation Algorithms: The authors introduce a greedy approximation algorithm that provides an $O(n)$-factor approximation for MNW, guaranteed to satisfy RRS and Prop1 in polynomial time.

Conclusion and Future Directions

This research provides a robust framework for the fair allocation of public goods, bridging the gap between private goods and general public decisions. While the "complexity jump" poses a challenge, the robustness of MNW and leximin offers a clear path forward. Future work remains to address general budget constraints where items have varying costs and to explore the possibility of constant-factor approximations for these NP-hard problems.

Summary updated

Abstract

We study fair allocation of indivisible public goods subject to cardinality (budget) constraints. In this model, we have n agents and m available public goods, and we want to select $k \leq m$ goods in a fair and efficient manner. We first establish fundamental connections between the models of private goods, public goods, and public decision making by presenting polynomial-time reductions for the popular solution concepts of maximum Nash welfare (MNW) and leximin. These mechanisms are known to provide remarkable fairness and efficiency guarantees in private goods and public decision making settings. We show that they retain these desirable properties even in the public goods case. We prove that MNW allocations provide fairness guarantees of Proportionality up to one good (Prop1), $1/n$ approximation to Round Robin Share (RRS), and the efficiency guarantee of Pareto Optimality (PO). Further, we show that the problems of finding MNW or leximin-optimal allocations are NP-hard, even in the case of constantly many agents, or binary valuations. This is in sharp contrast to the private goods setting that admits polynomial-time algorithms under binary valuations. We also design pseudo-polynomial time algorithms for computing an exact MNW or leximin-optimal allocation for the cases of (i) constantly many agents, and (ii) constantly many goods with additive valuations. We also present an O(n)-factor approximation algorithm for MNW which also satisfies RRS, Prop1, and 1/2-Prop.
BibTeX
@inproceedings{garg2021fair,
  author = {Jugal Garg and Pooja Kulkarni and Aniket Murhekar},
  title = {{On Fair and Efficient Allocations of Indivisible Public Goods}},
  booktitle = {FSTTCS},
  year = {2021},
  doi = {10.4230/lipics.fsttcs.2021.22},
}
Figure