EF1 and EFX Orientations
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909321236840448 |
|---|---|
| author | Deligkas, Argyrios Eiben, Eduard Goldsmith, Tiger-Lily Korchemna, Viktoriia |
| author_facet | Deligkas, Argyrios Eiben, Eduard Goldsmith, Tiger-Lily Korchemna, Viktoriia |
| contents | We study the problem of finding fair allocations -- EF1 and EFX -- of indivisible goods with orientations. In an orientation, every agent gets items from their own predetermined set. For EF1, we show that EF1 orientations always exist when agents have monotone valuations, via a pseudopolynomial-time algorithm. This surprisingly positive result is the main contribution of our paper. We complement this result with a comprehensive set of scenarios where our algorithm, or a slight modification of it, finds an EF1 orientation in polynomial time. For EFX, we focus on the recently proposed graph instances, where every agent corresponds to a vertex on a graph and their allowed set of items consists of the edges incident to their vertex. It was shown that finding an EFX orientation is NP-complete in general. We prove that it remains intractable even when the graph has a vertex cover of size 8, or when we have a multigraph with only 10 vertices. We essentially match these strong negative results with a fixed-parameter tractable algorithm that is virtually the best someone could hope for. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_13616 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | EF1 and EFX Orientations Deligkas, Argyrios Eiben, Eduard Goldsmith, Tiger-Lily Korchemna, Viktoriia Computer Science and Game Theory Computational Complexity Data Structures and Algorithms We study the problem of finding fair allocations -- EF1 and EFX -- of indivisible goods with orientations. In an orientation, every agent gets items from their own predetermined set. For EF1, we show that EF1 orientations always exist when agents have monotone valuations, via a pseudopolynomial-time algorithm. This surprisingly positive result is the main contribution of our paper. We complement this result with a comprehensive set of scenarios where our algorithm, or a slight modification of it, finds an EF1 orientation in polynomial time. For EFX, we focus on the recently proposed graph instances, where every agent corresponds to a vertex on a graph and their allowed set of items consists of the edges incident to their vertex. It was shown that finding an EFX orientation is NP-complete in general. We prove that it remains intractable even when the graph has a vertex cover of size 8, or when we have a multigraph with only 10 vertices. We essentially match these strong negative results with a fixed-parameter tractable algorithm that is virtually the best someone could hope for. |
| title | EF1 and EFX Orientations |
| topic | Computer Science and Game Theory Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2409.13616 |