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

arXiv:2602.10469 · cs.GT, cs.LG, math.OC · Submitted 2026-02-11 · Read on arXiv

cs.GT, cs.LG, math.OC

Submitted: 2026-02-11

Updated: 2026-10-01

Terminology

• Regret — 5× in this paper · explained in 3 episodes
• Distribution Shift — 1× in this paper · explained in 7 episodes
• Distribution Shifts — 1× in this paper · explained in 2 episodes
• Fidelity — 1× in this paper · explained in 2 episodes
• Non-stationarity — 1× in this paper · explained in 2 episodes

Sources

• Uniformly Bounded Regret in Dynamic Fair Allocation
• Non-Stationary Online Resource Allocation: Learning from a Single Sample
• The Long Arm of Nashian Allocation in Online $p$-Mean Welfare Maximization
• Fair Notification Optimization: An Auction Approach
• Online Fair Allocation with Best-of-Many-Worlds Guarantees

Related papers

• Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits
• In-Context Credit Assignment via the Core
• Optimal Regret for Online Market Making with Limit Order Book
• Breaking 1/epsilon Barrier in Quantum Zero-Sum Games: Generalizing Metric Subregularity for Spectraplexes
• Enhancing Affine Maximizer Auctions with Correlation-Aware Payment
• LLM Bidders Preserve the Mechanism-Level Orderings of Human Bidders