Extension of Additive Valuations to General Valuations on the Existence of EFX
Extension of Additive Valuations to General Valuations on the Existence of EFX
复制标题
将附加估值扩展到对 EFX 存在的一般估值
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Ryoga Mahara
中科院分区：
文献类型：
--
作者：
Ryoga Mahara
无嫉妒是公平分配中研究最广泛的概念之一。因为当项目不可分时，不嫉妒的分配并不总是存在，所以考虑了几种放松。其中，最引人注目的概念可能是对任何项目的嫉妒自由度（EFX）。非正式地说，EFX要求没有代理i羡慕另一个代理j后，任何项目删除j的捆绑。EFX分配的存在是一个主要的开放问题。我们研究的存在性EFX分配时，代理商有一般的估值。对于一般估值，已知EFX分配总是存在的（i）当n = 2或（ii）当所有代理人具有相同的估值时，其中n是代理人的数量。我们还知道，当最多可以保留n-1个未分配的项目时，EFX分配总是存在的。我们开发了新技术，并将加法估值的一些结果扩展到EFX分配存在的一般估值。我们表明，EFX分配总是存在（i）当所有代理人有两个一般估值之一时，或（ii）当项目的数量是最多n + 3。我们还证明了当最多可以保留n-2个未分配项时，EFX分配总是存在的。除了积极的结果，我们构造了一个n = 3的实例，其中现有的方法不起作用。资金来源：这项工作得到了京都大学和丰田汽车公司的部分支持[联合项目“交通社会的高级数学科学”]。
Envy freeness is one of the most widely studied notions in fair division. Because envy-free allocations do not always exist when items are indivisible, several relaxations have been considered. Among them, possibly the most compelling notion is envy freeness up to any item (EFX). Informally speaking, EFX requires that no agent i envies another agent j after the removal of any item in j’s bundle. The existence of EFX allocations is a major open problem. We study the existence of EFX allocations when agents have general valuations. For general valuations, it is known that an EFX allocation always exists (i) when n = 2 or (ii) when all agents have identical valuations, where n is the number of agents. It is also known that an EFX allocation always exists when one can leave at most n − 1 items unallocated. We develop new techniques and extend some results of additive valuations to general valuations on the existence of EFX allocations. We show that an EFX allocation always exists (i) when all agents have one of two general valuations or (ii) when the number of items is at most n + 3. We also show that an EFX allocation always exists when one can leave at most n − 2 items unallocated. In addition to the positive results, we construct an instance with n = 3, in which an existing approach does not work. Funding: This work was partially supported by Kyoto University and Toyota Motor Corporation [Joint Project “Advanced Mathematical Science for Mobility Society”].
登录
查看更多内容
最大纳什福利和有关 EFX 的其他故事
DOI：
10.24963/ijcai.2020/4
发表时间：
2020
期刊：
--
影响因子：
--
作者：
Amanatidis G
通讯作者：
Amanatidis G
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
通过 Rainbow Cycle Number 改善 EFX 保证
DOI：
10.1145/3465456.3467605
发表时间：
2021
期刊：
Proceedings of the 22nd ACM Conference on Economics and Computation (EC
影响因子：
--
作者：
Chaudhury, Bhaskar Ray;Garg, Jugal;Mehlhorn, Kurt;Mehta, Ruta;Misra, Pranabendu
通讯作者：
Misra, Pranabendu
具有子模估值的纳什社会福利常数因子近似算法
DOI：
10.1109/focs52979.2021.00012
发表时间：
2022
期刊：
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
--
作者：
Li, Wenzheng;Vondrak, Jan
通讯作者：
Vondrak, Jan