Approximately EFX and fPO Allocations for Bivalued Chores
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.
Cite
Text
Lin et al. "Approximately EFX and fPO Allocations for Bivalued Chores." International Joint Conference on Artificial Intelligence, 2025. doi:10.24963/IJCAI.2025/440Markdown
[Lin et al. "Approximately EFX and fPO Allocations for Bivalued Chores." International Joint Conference on Artificial Intelligence, 2025.](https://mlanthology.org/ijcai/2025/lin2025ijcai-approximately/) doi:10.24963/IJCAI.2025/440BibTeX
@inproceedings{lin2025ijcai-approximately,
title = {{Approximately EFX and fPO Allocations for Bivalued Chores}},
author = {Lin, Zehan and Wu, Xiaowei and Zhou, Shengwei},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2025},
pages = {3952-3960},
doi = {10.24963/IJCAI.2025/440},
url = {https://mlanthology.org/ijcai/2025/lin2025ijcai-approximately/}
}