On Fair and Efficient Allocations of Indivisible Public Goods

Jugal Garg, Pooja Kulkarni, Aniket Murhekar

Abstract

The simultaneous achievement of fairness and efficiency in the allocation of indivisible resources is a central challenge in computational social choice. While the existence of allocations that are Envy-Free up to one item (EF1) and Pareto Optimal (PO) is known, finding them efficiently has remained elusive. This paper presents the first constructive, pseudo-polynomial time algorithm for finding allocations that are both EF1 and Fractionally Pareto Optimal (fPO). By utilizing Fisher market frameworks and price-adjustment mechanisms, the authors demonstrate that these problems become strictly polynomial-time solvable in practical settings where agents use a restricted set of utility values.

Introduction

Fair division involves the distribution of resources among agents with diverse preferences. For divisible goods, such as land or fluids, market-clearing solutions like the Competitive Equilibrium from Equal Incomes (CEEI) provide robust fairness and efficiency. However, when goods are indivisible—such as houses, course seats, or shifts—the problem becomes a complex combinatorial challenge.

Two primary desiderata guide this field:

  1. Envy-Freeness up to one good (EF1): An agent does not envy another agent's bundle after the removal of at most one item from that bundle.
  2. Pareto Optimality (PO): No alternative allocation can make at least one agent better off without making another worse off.

While it is established that EF1 and PO allocations always exist, the computational task of finding them is daunting. Standard PO is co-NP-complete to verify, and previous algorithms for finding EF1+PO allocations were either non-constructive or relied on approximations. This paper addresses these gaps by providing a deterministic, constructive approach.

Methodology: Fisher Markets and Price-Rising

The authors approach the allocation problem through the lens of Fisher Markets. In this model, goods are assigned prices, and agents are treated as having budgets to "purchase" their most preferred items. The algorithm focuses on the Maximum Bang-per-Buck (MBB) condition, where agents only receive items that provide the highest utility relative to their price.

The proposed algorithm employs a "Price-Rising and Transfers" strategy. It begins with a welfare-maximizing allocation and iteratively checks for fairness violations (EF1 or EQ1). If a violation is found, the algorithm searches for "alternating paths" within a graph representing agents and goods to redistribute items. If no such path exists, the algorithm systematically raises the prices for a subset of "least spender" agents until a new market edge—and thus a new potential transfer—emerges. Unlike previous methods that perturbed valuations to find approximate solutions, this method works directly with original values.

Fractional Pareto Optimality (fPO)

A key contribution of this work is the focus on Fractional Pareto Optimality (fPO). An allocation is fPO if it is not Pareto dominated even by fractional allocations (where goods can be split).

  • Verifiability: Unlike standard PO, which is computationally hard to check, fPO can be verified efficiently. This is crucial for centralized authorities (e.g., a university registrar) who must prove to participants that the resulting allocation is efficient.
  • Strength: fPO is a stronger condition than PO; every fPO allocation is necessarily PO. By targeting fPO, the authors ensure a higher standard of efficiency that remains computationally manageable.

Computational Complexity and Tractability

The paper maps the complexity of finding EF1+fPO allocations to the Polynomial Local Search (PLS) class. The general algorithm is pseudo-polynomial, with a running time of $poly(n, m, v_{max})$, where $v_{max}$ represents the maximum utility value assigned to any good.

However, the authors identify significant "islands of tractability" that make the problem practical for real-world use:

  • k-ary Instances (Ratings): In many scenarios, agents express preferences using a limited scale (e.g., a 1-5 star scale). If the number of distinct utility values ($k$) is constant, the algorithm runs in strictly polynomial time.
  • Constant Number of Agents: For instances with a fixed number of agents ($n$), both EF1+PO and EQ1+PO can be computed in polynomial time.
  • Nash Welfare: The authors also provide a polynomial-time algorithm for maximizing Nash welfare—the geometric mean of utilities—when both the number of agents and the types of values are constant.

Equitability (EQ1)

Beyond envy-freeness, the paper explores Equitability up to one good (EQ1). While EF1 is based on an agent's own valuation of others' bundles, EQ1 requires that agents feel they have received a "fair share" relative to the utility others receive. The authors prove the existence of EQ1+fPO allocations for instances with strictly positive valuations and provide a pseudo-polynomial algorithm to find them.

Conclusion and Future Work

This research bridges the gap between theoretical existence proofs and practical algorithmic implementation in fair division. By focusing on fPO and identifying the role of limited valuation scales, the authors provide a roadmap for implementing fair and efficient allocation systems in real-world environments.

Future research directions include:

  • Developing a "strongly" polynomial algorithm that is independent of the magnitude of utility values ($v_{max}$).
  • Extending Equitability (EQ1) results to instances where agents may value some goods at zero.
  • Applying these fairness and efficiency guarantees to the allocation of "chores" (items with negative utility).

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 ≤ 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