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.
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."
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:
- 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).
- 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