# Fair Allocation of Indivisible Public Goods

arXiv: https://arxiv.org/abs/1805.03164 · HTML: https://mlsanity.com/paper/1805.03164/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 May 2018.

## Built on by (most cited first, 22 of 22)

- [Fairness in Federated Learning via Core-Stability](https://mlsanity.com/paper/2211.02091/) (2022)
- [Welfare and Fairness in Multi-objective Reinforcement Learning](https://mlsanity.com/paper/2212.01382/) (2022)
- [Temporal Fairness in Multiwinner Voting](https://mlsanity.com/paper/2312.04417/) (2023)
- [Temporal Elections: Welfare, Strategyproofness, and Proportionality](https://mlsanity.com/paper/2408.13637/) (2024)
- [Generative Social Choice: The Next Generation](https://mlsanity.com/paper/2505.22939/) (2025)
- [Strengthening Proportionality in Temporal Voting](https://mlsanity.com/paper/2505.22513/) (2025)
- [How Good is a Video Summary? A New Benchmarking Dataset and Evaluation Framework Towards Realistic Video Summarization](https://mlsanity.com/paper/2101.10514/) (2021)
- [Not in My Backyard! Temporal Voting Over Public Chores](https://mlsanity.com/paper/2508.08810/) (2025)
- [Group Fairness in Peer Review](https://mlsanity.com/paper/2410.03474/) (2024)
- [Core-Stable Committees under Restricted Domains](https://mlsanity.com/paper/2108.01987/) (2021)
- [The Leximin Approach for a Sequence of Collective Decisions](https://mlsanity.com/paper/2305.18024/) (2023)
- [Fairness in Contextual Resource Allocation Systems: Metrics and Incompatibility Results](https://mlsanity.com/paper/2212.01725/) (2022)
- [Robust Allocations with Diversity Constraints](https://mlsanity.com/paper/2109.15015/) (2021)
- [What Should We Optimize in Participatory Budgeting? An Experimental Study](https://mlsanity.com/paper/2111.07308/) (2021)
- [Harm Ratio: A Novel and Versatile Fairness Criterion](https://mlsanity.com/paper/2410.02977/) (2024)
- [A Linear Theory of Multi-Winner Voting](https://mlsanity.com/paper/2503.03082/) (2025)
- [Generating Fair Consensus Statements with Social Choice on Token-Level MDPs](https://mlsanity.com/paper/2510.14106/) (2025)
- [Fair Transit Stop Placement: A Clustering Perspective and Beyond](https://mlsanity.com/paper/2602.06776/) (2026)
- [Fairness in the Multi-Secretary Problem](https://mlsanity.com/paper/2511.23097/) (2025)
- [Procedural Fairness in Multi-Agent Bandits](https://mlsanity.com/paper/2601.10600/) (2026)
- [From Competition to Collaboration: Designing Sustainable Mechanisms Between LLMs and Online Forums](https://mlsanity.com/paper/2602.04572/) (2026)
- [A General Theory of Proportionality with Additive Utilities](https://mlsanity.com/paper/2602.08504/) (2026)

## Abstract (arXiv)

We consider the problem of fairly allocating indivisible public goods. We model the public goods as elements with feasibility constraints on what subsets of elements can be chosen, and assume that agents have additive utilities across elements. Our model generalizes existing frameworks such as fair public decision making and participatory budgeting. We study a groupwise fairness notion called the core, which generalizes well-studied notions of proportionality and Pareto efficiency, and requires that each subset of agents must receive an outcome that is fair relative to its size. In contrast to the case of divisible public goods (where fractional allocations are permitted), the core is not guaranteed to exist when allocating indivisible public goods. Our primary contributions are the notion of an additive approximation to the core (with a tiny multiplicative loss), and polynomial time algorithms that achieve a small additive approximation, where the additive factor is relative to the largest utility of an agent for an element. If the feasibility constraints define a matroid, we show an additive approximation of 2. A similar approach yields a constant additive bound when the feasibility constraints define a matching. More generally, if the feasibility constraints define an arbitrary packing polytope with mild restrictions, we show an additive guarantee that is logarithmic in the width of the polytope. Our algorithms are based on variants of the convex program for maximizing the Nash social welfare, but differ significantly from previous work in how it is used. Our guarantees are meaningful even when there are fewer elements than the number of agents. As far as we are aware, our work is the first to approximate the core in indivisible settings.