EFX Allocations Exist for Binary Valuations
We study the fair division problem and the existence of allocations satisfying the fairness criterion envy-freeness up to any item (EFX). The existence of EFX allocations is a major open problem in the fair division literature. We consider binary valuations where the marginal gain of the value by receiving an extra item is either $0$ or $1$. Babaioff et al. [2021] proved that EFX allocations always exist for binary and submodular valuations. In this paper, by using completely different techniques, we extend this existence result to general binary valuations that are not necessarily submodular, and we present a polynomial time algorithm for computing an EFX allocation.
Code (0)
등록된 구현이 없습니다.
Tasks
FairnessSimilar Papers 제목 키워드 기반
Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division
We study the fair division of indivisible items and provide new insights into the EFX problem, which is widely regarded as the central open question in fair division, and the PMMS problem, a strictly stronger variant of …
Dividing Good and Better Items Among Agents with Bivalued Submodular Valuations
We study the problem of fairly allocating a set of indivisible goods among agents with {\em bivalued submodular valuations} -- each good provides a marginal gain of either $a$ or $b$ ($a < b$) and goods have decreasing m…
Understanding EFX Allocations: Counting and Variants
Envy-freeness up to any good (EFX) is a popular and important fairness property in the fair allocation of indivisible goods, of which its existence in general is still an open question. In this work, we investigate the p…
FairnessEnvy-freeness up to one item: Shall we add or remove resources?
We consider a fair division model in which agents have general valuations for bundles of indivisible items. We propose two new axiomatic properties for allocations in this model: EF1+- and EFX+-. We compare these with th…
On the existence of EFX allocations in multigraphs
We study the problem of "fairly" dividing indivisible goods to several agents that have valuation set functions over the sets of goods. As fair we consider the allocations that are envy-free up to any good (EFX), i.e., n…