---
title: "Approximately EFX and fPO Allocations for Bivalued Chores"
authors:
  - "Zehan Lin"
  - "Xiaowei Wu"
  - "Shengwei Zhou"
doi: "10.24963/ijcai.2025/440"
url: "https://ijcai.org/proceedings/2025/440"
pdf: "https://ijcai.org/proceedings/2025/0440.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "3952-3960"
track: "Main Track"
keywords:
  - "Game Theory and Economic Paradigms: GTEP: Fair division"
---

# 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*, pages 3952-3960. DOI: [10.24963/ijcai.2025/440](https://doi.org/10.24963/ijcai.2025/440)

## 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.