Conference item
The frontier of intractability for EFX with two agents
- Abstract:
- We consider the problem of sharing a set of indivisible goods among agents in a fair manner, namely such that the allocation is envy-free up to any good (EFX). We focus on the problem of computing an EFX allocation in the two-agent case and characterize the computational complexity of the problem for most well-known valuation classes. We present a simple greedy algorithm that solves the problem when the agent valuations are weakly well-layered, a class which contains gross substitutes and budget-additive valuations. For the next largest valuation class we prove a negative result: the problem is PLS-complete for submodular valuations. All of our results also hold for the setting where there are many agents with identical valuations.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 387.6KB, Terms of use)
-
- Publisher copy:
- 10.1007/978-3-031-43254-5_17
Authors
+ Independent Research Fund Denmark
More from this funder
- Funder identifier:
- https://ror.org/05svhj534
- Grant:
- 9040-00433B
+ Swiss State Secretariat for Education, Research and Innovation
More from this funder
- Funder identifier:
- https://ror.org/00mt8k932
- Grant:
- MB22.00026
- Publisher:
- Springer
- Host title:
- Algorithmic Game Theory: 16th International Symposium, SAGT 2023, Egham, UK, September 4–7, 2023, Proceedings
- Pages:
- 290-307
- Series:
- Lecture Notes in Computer Science
- Series number:
- 14238
- Place of publication:
- Cham, Switzerland
- Publication date:
- 2023-09-04
- Acceptance date:
- 2023-07-01
- Event title:
- 16th International Symposium on Algorithmic Game Theory (SAGT 2023)
- Event location:
- Egham, UK
- Event website:
- https://www.royalholloway.ac.uk/research-and-teaching/departments-and-schools/computer-science/sagt-2023
- Event start date:
- 2023-09-04
- Event end date:
- 2023-09-07
- DOI:
- EISSN:
-
1611-3349
- ISSN:
-
0302-9743
- EISBN:
- 9783031432545
- ISBN:
- 9783031432538
- Language:
-
English
- Pubs id:
-
1526743
- Local pid:
-
pubs:1526743
- Deposit date:
-
2024-09-03
Terms of use
- Copyright holder:
- Goldberg et al.
- Copyright date:
- 2023
- Rights statement:
- © 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG.
- Notes:
- This is the accepted manuscript version of the paper. The final version is available online from Springer at https://dx.doi.org/10.1007/978-3-031-43254-5_17
If you are the owner of this record, you can report an update to it here: Report update to this record