Approximately EFX and fPO Allocations for Bivalued Chores

Lin, Zehan; Wu, Xiaowei; Zhou, Shengwei

doi:10.24963/ijcai.2025/440

Approximately EFX and fPO Allocations for Bivalued Chores

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 3952-3960.

https://doi.org/10.24963/ijcai.2025/440

Keywords

Game Theory and Economic Paradigms: GTEP: Fair division

Abstract

We consider the computation for allocations of indivisible chores that are approximately EFX and fractional Pareto optimal (fPO). It has been shown that 3-EFX and fPO allocations for bi-valued instances always exist, 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 fractional Pareto optimality. Instead of rounding fractional equilibrium, our algorithm starts with the integral EF1 equilibrium for bi-valued chores 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 fPO allocations.

Zehan Lin, Xiaowei Wu, and Shengwei Zhou. 2025. Approximately EFX and fPO Allocations for Bivalued Chores. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 3952–3960. https://doi.org/10.24963/ijcai.2025/440

@inproceedings{ijcai2025p440,
  title     = {Approximately EFX and fPO Allocations for Bivalued Chores},
  author    = {Lin, Zehan and Wu, Xiaowei and Zhou, Shengwei},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {3952--3960},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/440},
  url       = {https://doi.org/10.24963/ijcai.2025/440},
}

TY  - CPAPER
TI  - Approximately EFX and fPO Allocations for Bivalued Chores
AU  - Lin, Zehan
AU  - Wu, Xiaowei
AU  - Zhou, Shengwei
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 3952
EP  - 3960
DO  - 10.24963/ijcai.2025/440
UR  - https://doi.org/10.24963/ijcai.2025/440
ER  -