ausblenden:
Schlagwörter:
Computer Science, Computer Science and Game Theory, cs.GT,
Zusammenfassung:
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.
