{"id":"arxiv/2602.10469","url":"https://arxiv.org/abs/2602.10469","tags":["cs.GT","cs.LG","math.OC"],"score":0,"title":"Online Generalized-Mean Welfare Maximization: Achieving Near-Optimal Regret from Samples","domain":"cs.GT","source":"arxiv","authors":["Zongjun Yang","Rachitesh Kumar","Christian Kroer"],"reviews":0,"subject":"cs.GT","summary":"We study online fair allocation of $T$ sequentially arriving items among $n$ agents with heterogeneous preferences, with the objective of maximizing generalized-mean welfare, defined as the $p$-mean of agents' time-averaged utilities, with $p\\in (-\\infty, 1)$. We first consider the i.i.d. arrival model and show that the pure greedy algorithm -- which myopically chooses the welfare-maximizing integral allocation -- achieves $\\widetilde{O}(1/T)$ average regret. Importantly, in contrast to prior work, our algorithm does not require distributional knowledge and achieves the optimal regret rate…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-02-11","reactions":{}}