将添加剂估价延伸至对是否存在EFX的一般估价 (Extension of additive valuations to general valuations on the existence of EFX)

Envy-freeness is one of the most widely studied notions in fair division. Since envy-free allocations do not always exist when items are indivisible, several relaxations have been considered. Among them, possibly the most compelling concept is envy-freeness up to any item (EFX). We study the existence of EFX allocations for general valuations. The existence of EFX allocations is a major open problem. 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 as it is.

翻译：自由度是公平分配中最广泛研究的概念之一。由于在项目不可分割的情况下并不总是存在无嫉妒分配,因此考虑了一些放松,其中最令人信服的概念可能是任何项目(EFX)的无嫉妒程度。我们研究是否存在用于一般估值的EFX分配额。EFX分配额的存在是一个重大的未决问题。对于一般估值,已知EFX分配额始终存在:(一) 当所有代理商都有相同估值时,当美元=2美元或(二) 当所有代理商都有相同估值时,即美元为代理商数目时,即存在无嫉妒性分配。我们也知道,当一个人能够以最多n-1美元离开项目时,EFX分配额总是存在。我们开发新技术,并将添加性估值的某些结果扩大到对EFX分配额的存在情况的一般评价。我们表明,EFX分配额始终存在(一)当所有代理商都有两种一般估值时,或者(二)当所有代理商拥有最多美元+3美元的估值时,当所有代理商拥有相同的价值时,即有EFX分配额。我们还表明,当一个人可以以正值方式离开美元-2美元作为正值的物品时,我们没有正值。

相关内容