Online Social Welfare Function-based Resource Allocation
This work provides a general framework for online resource allocation for decision-makers aiming to optimize social welfare, offering a robust algorithm with theoretical guarantees.
The paper addresses the problem of repeatedly allocating finite resources to a population over multiple time steps, where individual utilities are aggregated using a social welfare function (SWF). The authors propose SWF-UCB, an online learning algorithm that achieves near-optimal regret of \(\tilde{O}(n+\sqrt{nkT})\) for \(k\) resources among \(n\) individuals over \(T\) time steps.
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.