论文标题
EFX存在三个代理商
EFX Exists for Three Agents
论文作者
论文摘要
我们研究以$ \ mathit {fair} $方式在具有添加估值的代理商中分发一组不可分割的物品的问题。所考虑的公平概念是任何项目（EFX）的嫉妒。尽管许多研究人员努力了几年，但EFX分配的存在尚未得到解决，这并没有得到两个代理的简单案例。在本文中，我们建设性地表明，EFX分配始终存在三种代理。此外，我们伪造了Caragiannis等人的猜想。通过显示一个具有三个代理的实例，该实例具有部分EFX分配（某些项目未分配），其NASH福利高于任何完整的EFX分配。
We study the problem of distributing a set of indivisible items among agents with additive valuations in a $\mathit{fair}$ manner. The fairness notion under consideration is Envy-freeness up to any item (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. 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.
