Approximately EFX and PO Allocations for Bivalued Chores
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912180420476928 |
|---|---|
| author | Lin, Zehan Wu, Xiaowei Zhou, Shengwei |
| author_facet | Lin, Zehan Wu, Xiaowei Zhou, Shengwei |
| contents | We consider the computation for allocations of indivisible chores that are approximately EFX and Pareto optimal (PO). Recently, Garg et al. (2024) show the existence of $3$-EFX and PO allocations for bi-valued instances, where the cost of an item to an agent is either $1$ or $k$ (where $k > 1$) by rounding the (fractional) earning restricted equilibrium. In this work, we improve the approximation ratio to $(2-1/k)$, while preserving the Pareto optimality. Instead of rounding fractional equilibrium, our algorithm starts with the integral EF1 equilibrium for bi-valued chores, introduced by Garg et al. (AAAI 2022) and Wu et al. (EC 2023), and reallocates items until approximate EFX is achieved. We further improve our result for the case when $k=2$ and devise an algorithm that computes EFX and PO allocations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_04550 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximately EFX and PO Allocations for Bivalued Chores Lin, Zehan Wu, Xiaowei Zhou, Shengwei Computer Science and Game Theory We consider the computation for allocations of indivisible chores that are approximately EFX and Pareto optimal (PO). Recently, Garg et al. (2024) show the existence of $3$-EFX and PO allocations for bi-valued instances, where the cost of an item to an agent is either $1$ or $k$ (where $k > 1$) by rounding the (fractional) earning restricted equilibrium. In this work, we improve the approximation ratio to $(2-1/k)$, while preserving the Pareto optimality. Instead of rounding fractional equilibrium, our algorithm starts with the integral EF1 equilibrium for bi-valued chores, introduced by Garg et al. (AAAI 2022) and Wu et al. (EC 2023), and reallocates items until approximate EFX is achieved. We further improve our result for the case when $k=2$ and devise an algorithm that computes EFX and PO allocations. |
| title | Approximately EFX and PO Allocations for Bivalued Chores |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2501.04550 |