English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse
  1. View item / 
  2. Item Summary

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Paper

EFX exists for three agents

MPS-Authors
/persons/resource/persons225687

Ray Chaudhury,  Bhaskar
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons134167

Garg,  Jugal
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

arXiv:2002.05119.pdf
(Preprint), 509KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Ray Chaudhury, B., Garg, J., & Mehlhorn, K. (2020). EFX exists for three agents. Retrieved from http://arxiv.org/abs/2002.05119.


Cite as: https://hdl.handle.net/21.11116/0000-0006-AF99-9
Abstract
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.