English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  An EF2X Allocation Protocol for Restricted Additive Valuations

Akrami, H., Rezvan, R., & Seddighin, M. (2022). An EF2X Allocation Protocol for Restricted Additive Valuations. Retrieved from https://arxiv.org/abs/2202.13676.

Item is

Files

show Files
hide Files
:
arXiv:2202.13676.pdf (Preprint), 356KB
Name:
arXiv:2202.13676.pdf
Description:
File downloaded from arXiv at 2023-01-04 15:28
OA-Status:
Green
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Akrami, Hannaneh1, Author           
Rezvan, Rojin2, Author
Seddighin, Masoud2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: Computer Science, Computer Science and Game Theory, cs.GT
 Abstract: We study the problem of fairly allocating a set of $m$ indivisible goods to a
set of $n$ agents. Envy-freeness up to any good (EFX) criteria -- which
requires that no agent prefers the bundle of another agent after removal of any
single good -- is known to be a remarkable analogous of envy-freeness when the
resource is a set of indivisible goods. In this paper, we investigate EFX
notion for the restricted additive valuations, that is, every good has some
non-negative value, and every agent is interested in only some of the goods.
We introduce a natural relaxation of EFX called EFkX which requires that no
agent envies another agent after removal of any $k$ goods. Our main
contribution is an algorithm that finds a complete (i.e., no good is discarded)
EF2X allocation for the restricted additive valuations. In our algorithm we
devise new concepts, namely "configuration" and "envy-elimination" that might
be of independent interest.
We also use our new tools to find an EFX allocation for restricted additive
valuations that discards at most $\lfloor n/2 \rfloor -1$ goods. This improves
the state of the art for the restricted additive valuations by a factor of $2$.

Details

show
hide
Language(s): eng - English
 Dates: 2022-02-282022-08-092022
 Publication Status: Published online
 Pages: 31 p.
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 2202.13676
BibTex Citekey: Akrami2202.13676
URI: https://arxiv.org/abs/2202.13676
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show