# Universal and Tight Online Algorithms for Generalized-Mean Welfare

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Sep 2021.

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

- [Overlap-based Vocabulary Generation Improves Cross-lingual Transfer Among Related Languages](https://mlsanity.com/paper/2203.01976/) (2022)
- [Welfare and Fairness in Multi-objective Reinforcement Learning](https://mlsanity.com/paper/2212.01382/) (2022)
- [p-Mean Regret for Stochastic Bandits](https://mlsanity.com/paper/2412.10751/) (2024)
- [Online Fair Division with Additional Information](https://mlsanity.com/paper/2505.24503/) (2025)
- [Approximate Proportionality in Online Fair Division](https://mlsanity.com/paper/2508.03253/) (2025)
- [Revisiting Social Welfare in Bandits: UCB is (Nearly) All You Need](https://mlsanity.com/paper/2510.21312/) (2025)
- [Automating Food Drop: The Power of Two Choices for Dynamic and Fair Food Allocation](https://mlsanity.com/paper/2406.06363/) (2024)
- [Online Fair Division for Personalized 2-Value Instances](https://mlsanity.com/paper/2505.22174/) (2025)
- [Improved Algorithms for Nash Welfare in Linear Bandits](https://mlsanity.com/paper/2601.22969/) (2026)
- [Bandit Max-Min Fair Allocation](https://mlsanity.com/paper/2505.05169/) (2025)
- [Price of Fairness in Bandits: A Tight Minimax Characterization](https://mlsanity.com/paper/2607.13402/) (2026)
- [Online Fair Division with Budget Constraints](https://mlsanity.com/paper/2607.23310/) (2026)

## Abstract (arXiv)

We study fair and efficient allocation of divisible goods, in an online manner, among n agents. The goods arrive online in a sequence of T time periods. The agents' values for a good are revealed only after its arrival, and the online algorithm needs to fractionally allocate the good, immediately and irrevocably, among the agents. Towards a unifying treatment of fairness and economic efficiency objectives, we develop an algorithmic framework for finding online allocations to maximize the generalized mean of the values received by the agents. In particular, working with the assumption that each agent's value for the grand bundle of goods is appropriately scaled, we address online maximization of p-mean welfare. Parameterized by an exponent term p ∈ (-∞, 1], these means encapsulate a range of welfare functions, including social welfare (p=1), egalitarian welfare (p → -∞), and Nash social welfare (p → 0). We present a simple algorithmic template that takes a threshold as input and, with judicious choices for this threshold, leads to both universal and tailored competitive guarantees. First, we show that one can compute online a single allocation that O (√n log n)-approximates the optimal p-mean welfare for all p≤ 1. The existence of such a universal allocation is interesting in and of itself. Moreover, this universal guarantee achieves essentially tight competitive ratios for specific values of p. Next, we obtain improved competitive ratios for different ranges of p by executing our algorithm with p-specific thresholds, e.g., we provide O(log 3 n)-competitive ratio for all p∈ (frac-1log 2n,1). We complement our positive results by establishing lower bounds to show that our guarantees are essentially tight for a wide range of the exponent parameter.