论文标题
在线纳什福利最大化而没有预测
Online Nash Welfare Maximization Without Predictions
论文作者
论文摘要
纳什福利的最大化等于代理商实用程序的几何平均值，因此经过了广泛的研究，因为它可以平衡资源分配问题的效率和公平性。 Banerjee，Gkatzelis，Gorokh和Jin（2022）最近推出了$ T $可划分物品的在线NASH福利最大化模型和具有附加实用程序的$ n $代理商，并预测了每个代理商的实用性，以接收所有物品。他们提供了在线算法，其竞争比率是对数的。我们启动了在线NASH福利最大化\ Emph {无预测}的研究，假设代理商的实用程序接收所有项目的公用事业是有界比率的不同，或者是因为其对NASH福利的实用程序最大化分配的实用性因有限的比率而异。我们设计在线算法，其竞争比率仅取决于代理公用事业和代理数量的上述比率的对数。
The maximization of Nash welfare, which equals the geometric mean of agents' utilities, is widely studied because it balances efficiency and fairness in resource allocation problems. Banerjee, Gkatzelis, Gorokh, and Jin (2022) recently introduced the model of online Nash welfare maximization for $T$ divisible items and $N$ agents with additive utilities with predictions of each agent's utility for receiving all items. They gave online algorithms whose competitive ratios are logarithmic. We initiate the study of online Nash welfare maximization \emph{without predictions}, assuming either that the agents' utilities for receiving all items differ by a bounded ratio, or that their utilities for the Nash welfare maximizing allocation differ by a bounded ratio. We design online algorithms whose competitive ratios only depend on the logarithms of the aforementioned ratios of agents' utilities and the number of agents.
