Approximately EFX and PO Allocations for Bivalued Chores

Zehan Lin, Xiaowei Wu, Shengwei ZhouarXiv 2025 · OpenReview

Abstract

The fair division of chores—tasks with associated costs—is a central problem in computational social choice. This paper investigates the existence and computation of allocations that are both Envy-Free up to any item (EFX) and Pareto Optimal (PO). Focusing on bi-valued chore costs {1, k}, the authors provide a new algorithm that achieves a (2 - 1/k)-approximation for EFX while maintaining PO. For the specific case of {1, 2} costs, they prove that a perfectly EFX and PO allocation always exists and can be found in polynomial time.

Introduction

In fair division, the "holy grail" is finding allocations that are both fair and efficient. While well-studied for "goods," the problem is significantly harder for "chores" (items with negative utility). The gold standard for fairness is Envy-Freeness up to any item (EFX): an agent does not envy another even after any single chore is removed from their own bundle. Combined with Pareto Optimality (PO), which ensures no agent can be made better off without making another worse off, EFX represents a robust fairness-efficiency guarantee.

The existence of EFX allocations for chores remains an open question for more than two agents. Previous work achieved a 3-approximation for bi-valued chores (where costs are either 1 or k). This research aims to tighten this bound and resolve existence for specific cost structures.

Methodology: Market Equilibria and Discrete Swaps

The authors leverage the Fisher Market framework, treating chores as items for which agents are paid to perform. The process begins with a pEF1 equilibrium—a state that is already PO and Envy-Free up to one item (EF1).

Instead of traditional rounding of fractional solutions, the paper introduces a discrete swap algorithm. Agents are categorized into groups based on their total earnings (payments received). For general {1, k} instances, the algorithm iteratively moves items from agents with high-payment chores to those with low-payment chores until the (2 - 1/k) threshold is satisfied.

Algorithm 1: The iterative procedure for achieving (2 - 1/k)-EFX and PO allocations.

Key Insights: The Power of Reallocation

A core contribution is the shift from continuous rounding to direct discrete reallocation. By focusing on the payments agents receive in equilibrium, the authors maintain PO as an invariant while iteratively improving fairness.

The algorithm identifies agents who are not (2 - 1/k)-EFX and performs a specific swap: a high-payment item is moved to an agent with lower earnings, and the bundles are updated to rebalance the "load." This process is visualized in the transition between earning states.

Visualization of the swap process: (a) shows the initial state with a potential swap, and (b) shows the resulting balanced earning distribution.

For {1, 2} instances, a more refined grouping strategy (z, z+1, z+2 earning levels) allows the algorithm to reach perfect EFX without violating PO. This suggests that smaller disparities in chore costs lead to more manageable mathematical structures.

Results and Discussion

The paper establishes two primary results:

  1. Improved Approximation: For {1, k} chores, a (2 - 1/k)-EFX and PO allocation is computable in polynomial time, improving upon the previous 3-approximation.
  2. Existence for {1, 2}: The authors prove that exact EFX and PO allocations always exist for {1, 2} costs and provide an efficient algorithm for their computation.

Limitations and Future Work

The current results rely on the bi-valued cost assumption. Future research should explore whether EFX exists for chores with arbitrary costs for n > 2 agents, or if these techniques can extend to ternary values (e.g., {0, 1, 2}). This work provides a robust framework for using market dynamics to solve complex fairness problems through iterative reallocation.

Summary updated

Abstract

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.
BibTeX
@misc{lin2025approximately,
  author = {Zehan Lin and Xiaowei Wu and Shengwei Zhou},
  title = {{Approximately EFX and PO Allocations for Bivalued Chores}},
  year = {2025},
  eprint = {2501.04550},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2501.04550},
}
Figure