A Simple Polynomial-Time EFX Repair for Cancelable Valuations

Hannaneh Akrami, Arash Ashuri, Bhaskar Ray Chaudhury, Kurt Mehlhorn, Maksim SoldatovarXiv 2026 · arXiv

TL;DR

By introducing a simple, deterministic tie-breaking rule to the classic Plaut–Roughgarden (PR) algorithm, this paper proves that the natural EFX "repair" dynamic terminates in polynomial time (at most $m$ steps for $m$ items). This result holds for the broad class of cancelable valuations—a generalization of additive preferences—and leads to improved polynomial-time approximation guarantees for the fair division of chores.

What Problem Does This Paper Address?

In the field of fair division, the goal is to distribute a set of indivisible items among agents in a way that feels fair. A gold standard fairness concept is EFX (Envy-Free up to any item), which dictates that no agent should envy another agent's bundle after removing any single item from it.

Plaut and Roughgarden (2020) showed that an EFX allocation always exists when agents share the same monotone valuation function. They proposed a highly intuitive "repair dynamic": start with any arbitrary partition of items, find an EFX violation, and repeatedly transfer an offending item to the lowest-valued bundle. While this algorithm is guaranteed to terminate because it never repeats a partition, its worst-case running time could be exponential. Even for simple, identical additive valuations, it was unknown whether this natural repair procedure could be made to run in polynomial time.

This paper addresses this efficiency gap. The authors seek to turn the PR repair dynamic into a polynomial-time algorithm without sacrificing its clean structure and useful monotonicity properties (such as ensuring the poorest agent's bundle value never decreases).

Methods

The authors discover that the exponential complexity of the original PR algorithm stems entirely from how ties are broken when selecting which item to transfer. They introduce a minimal, elegant modification:

  1. Fixed Priority Ordering: Before running the algorithm, they fix a strict total order ($\triangleleft$) on all items based on their singleton values (breaking ties arbitrarily). If item $g$ is worth less than item $h$, then $g \triangleleft h$.
  2. Highest-Priority Transfer: Whenever multiple items are eligible to be transferred to a minimum-valued bundle, the algorithm always transfers the highest-ranked eligible item according to the fixed order.

The authors analyze this rule under cancelable valuations. A valuation is cancelable if removing a common item from two bundles preserves their strict preference ranking ($v(S) > v(T) \implies v(S \setminus \{g\}) > v(T \setminus \{g\})$).

By leveraging cancelability, the authors prove a powerful combinatorial invariant: the items transferred in consecutive iterations must strictly decrease in the fixed priority ordering. Because there are only $m$ items in total, the algorithm can perform at most $m$ transfers before finding an EFX allocation.

Datasets

Not discussed in the paper. This is a theoretical paper focused on algorithmic design and mathematical proofs; no empirical datasets or experimental benchmarks were used.

Key Insights and Ideas

  • The Power of Static Tie-Breaking: It is surprising that an algorithm with an exponential upper bound can be tamed to run in a linear number of steps ($m$) simply by enforcing a static item ranking for tie-breaking. No complex history-tracking or dynamic potential functions are required.
  • Cancelability is More Than Additivity: Additive valuations (where the value of a bundle is just the sum of its item values) are inherently cancelable. However, the authors prove that cancelable valuations are a genuinely broader class. They explicitly construct a strict total order on 5 items (32 bundles) that satisfies cancelability but mathematically cannot be represented by any additive valuation function.
  • Modular Repair Tool: Because the algorithm is a repair procedure rather than a from-scratch construction, it acts as a modular tool. It preserves the minimum bundle value and does not increase the maximum bundle value, meaning it can be plugged into existing multi-phase allocation frameworks to add EFX guarantees on top of other criteria.

Key Results

  • Theorem 1.1 (Polynomial PR): For any monotone cancelable valuation or cost function, the modified PR algorithm terminates in at most $m$ item transfers and runs in polynomial time within the value-oracle model.
  • Improved Chores Allocation (Corollary 1.2): The authors apply their algorithm to the fair division of restricted additive chores (where items have negative utility/costs). By pairing a known scheduling Polynomial-Time Approximation Scheme (PTAS) with their EFX repair tool, they achieve an allocation that is simultaneously EFX, $(1+\varepsilon)$-MMS (Minmax Share), and a 2-approximation to the optimal social cost for any fixed $\varepsilon > 0$. This directly improves upon the previous best polynomial-time guarantee of $4/3$-MMS.

Limitations and Future Work

The primary limitation of this work—and a major open frontier in fair division literature—is the assumption of identical valuations (i.e., all agents share the same preference or cost function). While the paper successfully extends the identical-agent setting from additive to cancelable valuations in polynomial time, designing an efficient EFX repair dynamic for agents with distinct (general or additive) valuations remains an open and notoriously difficult challenge.

Summary updated

Abstract

The leximin++ proof of Plaut and Roughgarden for agents with identical monotone valuations gives a natural EFX-repair procedure: starting from an arbitrary partition, repeatedly transfer an eligible item to a minimum-valued bundle. The procedure terminates, but the standard argument gives no polynomial bound on the number of transfers, even for additive valuations. We show that a single deterministic tie-breaking rule makes this repair procedure polynomial for the broader class of cancelable valuations. Fix an ordering of the items consistent with their singleton values and always transfer the highest-ranked eligible item. Consecutive transferred items strictly decrease in this ordering, and hence the algorithm performs at most $m$ transfers, where $m$ is the number of items. Moreover, the repair procedure does not decrease the minimum bundle value or increase the maximum bundle value. As an application, for every fixed $\varepsilon>0$, we compute in polynomial time an allocation of restricted additive chores that is simultaneously EFX, $(1+\varepsilon)$-MMS, and a $2$-approximation to the optimal social cost. This improves upon the previous polynomial-time $4/3$-MMS guarantee. Finally, we exhibit a monotone cancelable ordering on five items with no additive representation, showing that the extension beyond additivity is genuine.
BibTeX
@misc{akrami2026simple,
  author = {Hannaneh Akrami and Arash Ashuri and Bhaskar Ray Chaudhury and Kurt Mehlhorn and Maksim Soldatov},
  title = {{A Simple Polynomial-Time EFX Repair for Cancelable Valuations}},
  year = {2026},
  eprint = {2608.08864},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.08864},
}
Figure