Proportionally Fair Online Allocation of Public Goods with Predictions

Siddhartha Banerjee, Vasilis Gkatzelis, Safwan Hossain, Billy Jin, Evi Micha, Nisarg Shah

Introduction

In the realm of social choice and resource allocation, the distribution of "public goods"—resources like parks, infrastructure, or shared digital services that many people can enjoy simultaneously—presents a unique challenge. Unlike private goods, where giving to one person excludes others, public goods allow for collective benefit. However, when these goods arrive sequentially over time (an "online" setting) and the budget is limited, decision-makers face a difficult trade-off: invest now in a mediocre project or save the budget for a potentially better one later.

Presented at IJCAI-23, this research explores how machine-learned predictions can bridge the gap between the uncertainty of online allocation and the ideal outcomes of offline planning. The authors demonstrate that even noisy predictions can lead to an exponential improvement in fairness guarantees.

The Problem: Proportional Fairness under Uncertainty

The core objective of this study is Proportional Fairness. In this context, a fair allocation ensures that every group of citizens receives a benefit proportional to its size and the degree of consensus among its members regarding their preferences.

In an online environment, achieving this is notoriously difficult. A "blind" algorithm—one with no knowledge of the future—might exhaust its budget on early projects that only benefit a small subset of the population, leaving nothing for later projects that might have had broader appeal. Mathematically, the "competitive ratio" (the performance gap between an online algorithm and an omniscient offline one) for blind algorithms is typically linear relative to the time horizon ($T$) and budget ($B$), denoted as $\Theta(T/B)$. This means as the time horizon grows, the fairness guarantee degrades significantly.

Methodology: Set-Aside Greedy Algorithms

To overcome the limitations of blind allocation, the authors introduce a framework called Set-Aside Greedy Algorithms. This approach integrates machine-learned predictions into the decision-making process through three key components:

  1. The Prediction Model: The algorithm is provided with a prediction ($\hat{V}_i$) of the total utility each agent $i$ is expected to derive from all goods arriving over the entire time horizon $T$. The authors account for real-world inaccuracy by parameterizing the algorithm's performance based on overestimation and underestimation factors.
  2. The "Set-Aside" Strategy: The total budget $B$ is bifurcated. A small portion is "set aside" to be spent incrementally on arriving goods. This ensures every agent receives a baseline level of utility based on their predicted total value, serving as a form of insurance against being entirely excluded from the allocation.
  3. The Greedy Component with Linear Penalty: The remaining budget is allocated greedily to maximize a logarithmic utility function. However, this is not a simple greedy approach; it includes a "linear penalty" that discourages the algorithm from spending too quickly if the current goods do not meet a certain value threshold relative to the remaining budget.

This framework is further extended into a "batched" model, allowing multiple goods to arrive per round. This unified model effectively bridges previous research on both public and private goods into a single theoretical structure.

Key Insights and Results

The research yields several significant theoretical breakthroughs:

  • The Exponential Jump: The most critical finding is the dramatic improvement in fairness guarantees. By utilizing predictions, the fairness factor improves from $\Theta(T/B)$ to $\Theta(\log(T/B))$. For example, in a scenario with 1,000 rounds and a budget of 10, the fairness factor drops from approximately 100 to roughly 7.
  • Robustness to Prediction Error: The algorithms are designed to be "gracefully degrading." If predictions are highly accurate, the algorithm achieves near-optimal fairness. If the predictions are noisy, the fairness guarantee worsens proportionally to the error, but the system remains functional and still outperforms blind alternatives.
  • Asymptotic Optimality: The authors establish a lower bound of $\Omega(\log(T/B))$ even for scenarios with perfect predictions and a single agent. This proves that their proposed algorithm is asymptotically optimal.
  • Public vs. Private Goods: The study highlights that the "cooperation" inherent in public goods—where multiple agents benefit from the same investment—actually makes the lower-bound analysis more complex than in private goods cases, requiring more sophisticated primal-dual analysis.

Limitations and Future Directions

While the paper establishes a new frontier for fair online allocation, it identifies several areas for future exploration:

  • Arrival Models: The current analysis assumes an "adversarial" arrival order (the worst-case sequence). Future research could investigate "random-order" or stochastic models, which might yield even tighter bounds.
  • Prediction Types: The model currently relies on predicting total value per agent. Exploring predictions regarding specific high-value goods or population-wide trends could further refine the allocation logic.
  • Utility Functions: The study focuses on linear utilities. Incorporating non-linear utilities—where goods have diminishing returns—would better reflect real-world scenarios like infrastructure development.

Conclusion

By proving that predictions can transform the fairness landscape from a linear struggle to a logarithmic guarantee, this paper provides a robust theoretical foundation for more equitable resource management in uncertain, dynamic environments.

Summary updated

Abstract

We design online algorithms for fair allocation of public goods to a set of N agents over a sequence of T rounds and focus on improving their performance using predictions. In the basic model, a public good arrives in each round, and every agent reveals their value for it upon arrival. The algorithm must irrevocably decide the investment in this good without exceeding a total budget of B across all rounds. The algorithm can utilize (potentially noisy) predictions of each agent’s total value for all remaining goods. The algorithm's performance is measured using a proportional fairness objective, which informally demands that every group of agents be rewarded proportional to its size and the cohesiveness of its preferences. We show that no algorithm can achieve better than Θ(T/B) proportional fairness without predictions. With reasonably accurate predictions, the situation improves significantly, and Θ(log(T/B)) proportional fairness is achieved. We also extend our results to a general setting wherein a batch of L public goods arrive in each round and O(log(min(N,L)T/B)) proportional fairness is achieved. Our exact bounds are parameterized as a function of the prediction error, with performance degrading gracefully with increasing errors.
BibTeX
@inproceedings{banerjee2023proportionally,
  author = {Siddhartha Banerjee and Vasilis Gkatzelis and Safwan Hossain and Billy Jin and Evi Micha and Nisarg Shah},
  title = {{Proportionally Fair Online Allocation of Public Goods with Predictions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/3},
}
Figure