cs.GTFeb 11, 2026

Online Generalized-Mean Welfare Maximization: Achieving Near-Optimal Regret from Samples

Authors: Zongjun Yang, Rachitesh Kumar, Christian Kroer

Organizations: Columbia University · Carnegie Mellon University

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We study online fair allocation of TT sequentially arriving items among nn agents with heterogeneous preferences, with the objective of maximizing generalized-mean welfare, defined as the pp-mean of agents' time-averaged utilities, with p∈(−∞,1)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 O~(1/T)\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 Ω(1)Ω(1) average regret. We show that only a single historical sample from each distribution is sufficient to recover the optimal O~(1/T)\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.

Figures & tables

Figure 1: Different generalized-mean welfare functions, parametrized by different values of pp .
Table 2
 it†∈arg⁡max⁡i∈[n]f(Wt−1†+vt(o)⋅eit),xt†←eit†.i_{t}^{\dagger}\in\arg\max_{i\in[n]}f\left(\frac{\bm{W}_{t-1}^{\dagger}+\bm{v}_{t}^{(\mathtt{o})}\cdot\bm{e}_{i}}{t}\right),\bm{x}_{t}^{\dagger}\leftarrow\bm{e}_{i_{t}^{\dagger}}. (4)
Algorithm 1 Greedy Algorithm for Stationary Arrivals.
 max⁡u≥0,zt,⋯ ,zT≥0\displaystyle\max_{\bm{u}\geq 0,\bm{z}_{t},\cdots,\bm{z}_{T}\geq 0}log⁡f(u)\displaystyle\log f(\bm{u}) (5)
 s.t.\displaystyle\textnormal{s.t.}ui≤1T(Wt−1,i†+vt,i(o)⋅zt,i+∑τ=t+1Tvτ,i(h)⋅zτ,i),  ∀i∈[n]\displaystyle u_{i}\leq\frac{1}{T}\left({W}_{t-1,i}^{\dagger}+v_{t,i}^{(\mathtt{o})}\cdot z_{t,i}+\sum_{\tau=t+1}^{T}v_{\tau,i}^{(\mathtt{h})}\cdot z_{\tau,i}\right),\ \ \forall i\in[n] 
  ∥zτ∥1≤1∀τ∈{t+1,⋯ ,T}.\displaystyle\|\bm{z}_{\tau}\|_{1}\leq 1\quad\quad\forall\tau\in\{t+1,\cdots,T\}. 
Algorithm 2 Online Primal Re-solving
 βt†←arg⁡min⁡β∈R+n{1T(⟨β,Wt−1†⟩+max⁡i∈[n]βivt,i(o)+∑τ=t+1Tmax⁡i∈[n]βivτ,i(h))+(−log⁡f)+⋆(−β)}.\bm{\beta}_{t}^{\dagger}\leftarrow\arg\min_{\bm{\beta}\in\mathbb{R}_{+}^{n}}\left\{\frac{1}{T}\left(\langle\bm{\beta},\bm{W}_{t-1}^{\dagger}\rangle+\max_{i\in[n]}\beta_{i}v_{t,i}^{(\mathtt{o})}+\sum_{\tau=t+1}^{T}\max_{i\in[n]}\beta_{i}v_{\tau,i}^{(\mathtt{h})}\right)+\left(-\log f\right)_{+}^{\star}(-\bm{\beta})\right\}. (6)
Algorithm 3 Online Dual Re-solving.
Primal, dual programsMeaningPast utilityTail items
Pt(r), Dt(r)P_{t}^{(\mathtt{r})},\ D_{t}^{(\mathtt{r})}Re-solving program, solved by the algorithm at step tt .Wt−1†\bm{W}_{t-1}^{\dagger}(vt(o),vt+1:T(h))(\bm{v}_{t}^{(\mathtt{o})},\bm{v}_{t+1:T}^{(\mathtt{h})}) : the true item tt , followed by historical sample
Pt(c), Dt(c)P_{t}^{(\mathtt{c})},\ D_{t}^{(\mathtt{c})}Coupling program constructed for analysis.Wt†\bm{W}_{t}^{\dagger}vt+1:T(c) ⁣= ⁣{vt+1:T(o),\lx@crefcreftypecap refnumsection: re-solve-3,jointly sampled with vt+1:T(o),\lx@crefcreftypecap refnumsec: robust.\bm{v}_{t+1:T}^{(\mathtt{c})}\!=\!\begin{cases}\bm{v}_{t+1:T}^{(\mathtt{o})},&\text{\lx@cref{creftypecap~refnum}{section: re-solve-3}},\\ \text{jointly sampled with }v_{t+1:T}^{(\mathtt{o})},&\text{\lx@cref{creftypecap~refnum}{sec: robust}}.\end{cases}
Table 3: Re-solving and coupling programs.
Figure 2: Simulations of the greedy algorithm and the re-solving algorithm on the Instagram notification dataset (left) and the MovieLens dataset (right) with the Nash welfare objective (p=0)(p=0) , under three inputs models: i.i.d. (top) , periodic (middle) , and true temporal (bottom) .
 Instagram (n=4)(n=4)MovieLens (n=10)(n=10)
Time per item (ms)27.627.629.629.6
Table 4: Time per allocated item of the re-solving algorithm when T=10,000T=10,000 . Single-thread execution. Device: Intel Core i5-14600KF CPU ( 5.35.3 GHz) with 3232 GB of RAM, under Ubuntu 24.04 with Python 3.12 and NumPy 2.4.
Figure 3: Simulations of infrequent dual re-solving with re-solving interval τ∈{1,10,50,500}\tau\in\{1,10,50,500\} on the Instagram notification dataset (left) and the MovieLens dataset (right) with the Nash welfare objective (p=0)(p=0) , under three inputs models: i.i.d. (top) , periodic (middle) , and true temporal (bottom) . The dashed curve τ=1\tau=1 is the standard dual re-solving algorithm.
Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Simulations of the greedy algorithm and the re-solving algorithm on the Instagram notification dataset (left) and the MovieLens dataset (right) with the p=−1p=-1 in the objective, under three inputs models: i.i.d. (top) , periodic (middle) , and true temporal (bottom) .
Figure 5: Simulations of the greedy algorithm and the re-solving algorithm on the Instagram notification dataset (left) and the MovieLens dataset (right) with the p=0.5p=0.5 in the objective, under three inputs models: i.i.d. (top) , periodic (middle) , and true temporal (bottom) .

Explore similar work

CardsList

  1. Fair Online Resource Allocation

    Jun 17, 2026Christopher En, Yuri Faenza, Andrea Lodi +1Algorithmic FairnessWelfare

    Columbia University, IEOR Department · Cornell Tech · Universidad de Chile

  2. Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copies

    Aug 23, 2024Arun Verma, Indrajit Saha, Makoto Yokoo +1Algorithmic Fairness

    Singapore-MIT Alliance for Research and Technology, Republic of Singapore · Faculty of ISEE, Kyushu University, Japan · Department of Computer Science, National University of Singapore, Republic of Singapore

  3. Online Fair Division with Budget Constraints

    Jul 25, 2026Saar Cohen, Nicholas Teh, Paul W. Goldberg +1Algorithmic FairnessFirst-Price Auctions

    Department of Computer Science, University of Oxford, UK