arXiv：cs.LG（机器学习，全量分类）· Zongjun Yang, Rachitesh Kumar, Christian Kroer·· 15 小时前AI 评分36
在线广义均值福利最大化：仅用样本达到近最优遗憾
Online Generalized-Mean Welfare Maximization: Achieving Near-Optimal Regret from Samples
AI 导读
研究针对 T 件物品在 n 个异质偏好智能体间的在线公平分配，目标是最大化广义均值福利（智能体时间平均效用的 p-mean，p∈(-∞,1)）。在 i.i.d. 到达模型下，纯贪心算法无需分布知识即可仅靠在线样本达到最优的 Õ(1/T) 平均遗憾；在时变分布的非平稳模型中，每个分布仅需一个历史样本即可恢复该最优遗憾率，且对分布偏移保持稳健。
正文
Abstract: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 using only the online samples.
We then go beyond i.i.d. arrivals and investigate a nonstationary model with time-varying independent distributions. In the absence of additional data about the distributions, it is known that every online algorithm must suffer $\Omega(1)$ average regret. We show that only a single historical sample from each distribution is sufficient to recover the optimal $\widetilde{O}(1/T)$ average regret rate, even in the face of arbitrary non-stationarity. Our algorithms are based on the re-solving paradigm: they assume that the remaining items will be the ones seen historically in those periods and solve the resulting welfare-maximization problem to determine the decision in every period. Finally, we also account for distribution shifts that may distort the fidelity of historical samples and show that the performance of our re-solving algorithms is robust to such shifts.
| Subjects: | Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG); Optimization and Control (math.OC) |
| Cite as: | arXiv:2602.10469 [cs.GT] |
| (or arXiv:2602.10469v2 [cs.GT] for this version) | |
| https://doi.org/10.48550/arXiv.2602.10469 arXiv-issued DOI via DataCite |
Submission history
From: Zongjun Yang [view email]
[v1]
Wed, 11 Feb 2026 03:16:03 UTC (242 KB)
[v2]
Thu, 1 Oct 2026 15:39:05 UTC (278 KB)
来源：arXiv：cs.LG（机器学习，全量分类） · arxiv.org