EFX Exists for Three Agents
EFX Exists for Three Agents
复制标题
EFX 存在三个代理
DOI：
10.1145/3391403.3399511
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Mehlhorn, Kurt
中科院分区：
文献类型：
--
作者：
Chaudhury, Bhaskar R.;Garg, Jugal;Mehlhorn, Kurt
研究了一组不可分项目在具有可加性定价的智能体之间公平分配的问题。所考虑的公平概念是对任何项目的嫉妒自由（EFX）。尽管许多研究人员多年来作出了重大努力，但除了两种药剂的简单情况外，EFX分配的存在尚未得到解决。本文建设性地证明了三个agent的EFX分配总是存在的。此外，我们通过展示一个具有三个代理的实例来证伪Caragiannis等人的猜想，其中部分EFX分配（某些项目未分配）具有比任何完全EFX分配更高的纳什福利。
We study the problem of distributing a set of indivisible items among agents with additive valuations in a fairmanner. The fairness notion under consideration is Envy-freeness up to anyitem (EFX). Despite significant efforts by many researchers for several years, the existence of EFX allocations has not been settled beyond the simple case of two agents. In this paper, we show constructively that an EFX allocation always exists for three agents. Furthermore, we falsify the conjecture by Caragiannis et al.[9] by showing an instance with three agents for which there is a partial EFX allocation (some items are not allocated) with higher Nash welfare than that of any complete EFX allocation.
登录
查看更多内容
DOI：
10.1145/2764468.2764490
发表时间：
2015-06
期刊：
Proceedings of the Sixteenth ACM Conference on Economics and Computation
影响因子：
--
作者：
David Kurokawa;Ariel D. Procaccia;Nisarg Shah
通讯作者：
David Kurokawa;Ariel D. Procaccia;Nisarg Shah
DOI：
10.1145/3391403.3399526
发表时间：
2019-02
期刊：
Proceedings of the 21st ACM Conference on Economics and Computation
影响因子：
--
作者：
J. Garg;Setareh Taki
通讯作者：
J. Garg;Setareh Taki
可分离分段线性凹效用下不可分项的纳什社会福利
DOI：
--
发表时间：
2016
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Nima Anari;Tung Mai;S. Gharan;V. Vazirani
通讯作者：
V. Vazirani
DOI：
--
发表时间：
2017
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
J. Garg;M. Hoefer;K. Mehlhorn
通讯作者：
K. Mehlhorn
改进纳什社会福利近似值
影响因子：
5
作者：
McGlaughlin, Peter;Garg, Jugal
通讯作者：
Garg, Jugal