arXiv:2602.01400stat.MLcs.LG2026-02

基于社会福利函数的在线资源分配,实现动态最优决策与实时推断。

Online Social Welfare Function-based Resource Allocation

  • 利用单调性将个体效用置信序列推广到整体福利,构建通用框架。
  • 提出SWF-UCB算法,在多轮分配中实现近似最优$ ilde{O}(n+ oot{n}{kT})$ regret。
  • 适用于公平性、效率等不同社会目标,支持在线检验与政策评估。

在多个实际场景中,中心化决策者需在多个时间步内反复分配有限资源给群体。个体获得资源后产生随机效用;为刻画分配对整体的影响,个体期望效用通过社会福利函数(SWF)聚合。本文形式化该设定,提出适用于任意单调、凹且Lipschitz连续的SWF的通用置信序列框架。核心洞察是:仅凭单调性即可将个体效用的置信序列提升为最优福利的任意时有效性边界。在此基础上,提出不依赖具体SWF的在线学习算法SWF-UCB,实现近似最优$ ilde{O}(n+ oot{n}{kT})$的后悔值($k$个资源分给$n$个个体,共$T$个时间步)。在加权幂平均、Kolm、Gini三类典型SWF上实例化,分别设计专用查询算法。实验验证$ oot{T}$缩放规律,并揭示$k$与SWF参数间的复杂交互。该框架自然支持序贯假设检验、最优停止与策略评估等推断任务。

原文摘要 · Abstract (English)

In many real-world settings, a centralized decision-maker must repeatedly allocate finite resources to a population over multiple time steps. Individuals who receive a resource derive some stochastic utility; to characterize the population-level effects of an allocation, the expected individual utilities are then aggregated using a social welfare function (SWF). We formalize this setting and present a general confidence sequence framework for SWF-based online learning and inference, valid for any monotonic, concave, and Lipschitz-continuous SWF. Our key insight is that monotonicity alone suffices to lift confidence sequences from individual utilities to anytime-valid bounds on optimal welfare. Building on this foundation, we propose SWF-UCB, a SWF-agnostic online learning algorithm that achieves near-optimal $\tilde{O}(n+\sqrt{nkT})$ regret (for $k$ resources distributed among $n$ individuals at each of $T$ time steps). We instantiate our framework on three normatively distinct SWF families: Weighted Power Mean, Kolm, and Gini, providing bespoke oracle algorithms for each. Experiments confirm $\sqrt{T}$ scaling and reveal rich interactions between $k$ and SWF parameters. This framework naturally supports inference applications such as sequential hypothesis testing, optimal stopping, and policy evaluation.

资源分配在线学习社会福利置信序列

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。