Universal and Tight Online Algorithms for Generalized-Mean Welfare
Universal and Tight Online Algorithms for Generalized-Mean Welfare
复制标题
用于广义平均福利的通用且严格的在线算法
DOI：
10.1609/aaai.v36i5.20406
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Arnab Maiti
中科院分区：
文献类型：
--
作者：
Siddharth Barman;Arindam Khan;Arnab Maiti
我们研究在n个代理商之间以在线方式公平有效地分配可分割商品。货物以T个时间段的顺序到达网上。智能体对商品的价值只有在商品到达后才会显示出来，在线算法需要在智能体之间立即且不可撤销地分配商品。为了统一对待公平和经济效率目标，我们开发了一个算法框架，用于寻找在线分配，以最大化代理收到的价值的广义平均值。特别是，在假设每个代理人对大捆商品的价值是适当缩放的情况下，我们解决了p-均值福利的在线最大化问题。由（- inty, 1）中的指数项p参数化，这些均值封装了一系列福利函数，包括社会福利（p=1）、平等福利（p至- inty）和纳什社会福利（p至0）。
We study fair and efficient allocation of divisible goods, in an online manner, among n agents. The goods arrive online in a sequence of T time periods. The agents' values for a good are revealed only after its arrival, and the online algorithm needs to fractionally allocate the good, immediately and irrevocably, among the agents. Towards a unifying treatment of fairness and economic efficiency objectives, we develop an algorithmic framework for finding online allocations to maximize the generalized mean of the values received by the agents. In particular, working with the assumption that each agent's value for the grand bundle of goods is appropriately scaled, we address online maximization of p-mean welfare. Parameterized by an exponent term p in (-infty, 1], these means encapsulate a range of welfare functions, including social welfare (p=1), egalitarian welfare (p to -infty), and Nash social welfare (p to 0).
We present a simple algorithmic template that takes a threshold as input and, with judicious choices for this threshold, leads to both universal and tailored competitive guarantees. First, we show that one can compute online a single allocation that O (sqrt(n) log n)-approximates the optimal p-mean welfare for all p
登录
查看更多内容
DOI：
10.1145/3219166.3219179
发表时间：
2018-06
期刊：
Proceedings of the 2018 ACM Conference on Economics and Computation
影响因子：
--
作者：
Gerdus Benade;Aleksandr M. Kazachkov;Ariel D. Procaccia;Alexandros Psomas
通讯作者：
Gerdus Benade;Aleksandr M. Kazachkov;Ariel D. Procaccia;Alexandros Psomas
影响因子：
22.7
作者：
M. Mitzenmacher;Sergei Vassilvitskii
通讯作者：
M. Mitzenmacher;Sergei Vassilvitskii
在线纳什社会福利最大化与预测
DOI：
--
发表时间：
2022
期刊：
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Gorokh, Artur;Banerjee, Siddhartha;Jin, Billy;Gkatzelis, Vasilis
通讯作者：
Gkatzelis, Vasilis
公平高效的在线分配和标准化估值
DOI：
--
发表时间：
2021
期刊：
35th AAAI Conference on Artificial Intelligence (AAAI 2021
影响因子：
--
作者：
Gkatzelis, Vasilis;Psomas, Alexandros;Tan, Xizhi
通讯作者：
Tan, Xizhi