Water-Filling is Universally Minimax Optimal

View PDF HTML (experimental)

Abstract:Allocation of dynamically-arriving (i.e., online) divisible resources among a set of offline agents is a fundamental problem, with applications to online marketplaces, scheduling, portfolio selection, signal processing, and many other areas. The water-filling algorithm, which allocates an incoming resource to maximize the minimum load of compatible agents, is ubiquitous in many of these applications whenever the underlying objectives prefer more balanced solutions; however, the analysis and guarantees differ across settings. We provide a justification for the widespread use of water-filling by showing that it is a universally minimax optimal policy in a strong sense. Formally, our main result implies that water-filling is minimax optimal for a large class of objectives -- including both Schur-concave maximization and Schur-convex minimization -- under $\alpha$-regret and competitive ratio measures. This optimality holds for every fixed tuple of agents and resource counts. Remarkably, water-filling achieves these guarantees as a myopic policy, remaining entirely agnostic to the objective function, agent count, and resource availability. Our techniques notably depart from the popular primal-dual analysis of online algorithms, and instead develop a novel way to apply the theory of majorization in online settings to achieve universality guarantees.

Subjects:

Data Structures and Algorithms (cs.DS); Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG)

Cite as: arXiv:2603.26893 [cs.DS]

(or arXiv:2603.26893v1 [cs.DS] for this version)

https://doi.org/10.48550/arXiv.2603.26893

arXiv-issued DOI via DataCite (pending registration)

Submission history

From: Ramiro Deo-Campo Vuong [view email] [v1] Fri, 27 Mar 2026 18:13:07 UTC (102 KB)