English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  EFX exists for three agents

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

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/21.11116/0000-0006-AF99-9 Version Permalink: https://hdl.handle.net/21.11116/0000-0006-AF9A-8
Genre: Paper

Files

show Files
hide Files
:
arXiv:2002.05119.pdf (Preprint), 509KB
View   Save
File Permalink:
https://hdl.handle.net/21.11116/0000-0006-AF9B-7
Name:
arXiv:2002.05119.pdf
Description:
File downloaded from arXiv at 2020-07-10 10:58
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
View
Copyright Date:
-
Copyright Info:
Full version of a paper published at Economics and Computation (EC) 2020
License:
http://creativecommons.org/licenses/by/4.0/

Locators

show

Creators

show
hide
 Creators:
Ray Chaudhury, Bhaskar1, Author           
Garg, Jugal1, Author           
Mehlhorn, Kurt1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: Computer Science, Computer Science and Game Theory, cs.GT,
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2020-02-122020-05-302020
 Publication Status: Published online
 Pages: 28 p.
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 2002.05119
URI: http://arxiv.org/abs/2002.05119
BibTex Citekey: RayChaudhury_arXiv2002.05119
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show