Approximately EFX and fPO Allocations for Bivalued Chores

Approximately EFX and fPO Allocations for Bivalued Chores

Zehan Lin, Xiaowei Wu, Shengwei Zhou

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence
Main Track. Pages 3952-3960. https://doi.org/10.24963/ijcai.2025/440

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.
Keywords:
Game Theory and Economic Paradigms: GTEP: Fair division