水位填充法在多种资源分配场景中均最优，无需知道目标函数和资源总量。
Water-Filling is Universally Minimax Optimal
- 基于排序理论设计通用在线分配策略，不依赖具体目标函数。
- 在α-后悔率与竞争比下对大量目标函数实现最小最大最优。
- 只需局部决策，适用于动态资源分配的各类实际场景。
将动态到达的可分资源分配给固定数量的离线参与者，是在线市场、调度、投资组合选择、信号处理等多个领域的基础问题。水位填充算法通过将新资源分配给兼容性最高的参与者以最大化最小负载，在偏好均衡解的场景中广泛应用。本文证明，水位填充是一种强意义上的普遍最小最大最优策略：其在α-后悔率和竞争比度量下，对包括舒尔凹最大化与舒尔凸最小化在内的大量目标函数均达到最优。该最优性对任意固定的参与者与资源数量组合均成立。值得注意的是，水位填充作为仅依赖局部信息的贪心策略，完全无需知晓目标函数、参与者数量或资源总量。我们的方法突破了传统对偶分析框架，首次将排序理论应用于在线设置，实现了跨目标函数的统一最优保证。
原文摘要 · Abstract (English)
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 $α$-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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。