Simple tie-breaking rule makes EFX repair polynomial for cancelable valuations

Fair division of indivisible goods is a classic challenge in computational game theory. The popular EFX (envy-free up to any item) notion guarantees that no agent envies another after removing a single item. Plaut and Roughgarden's leximin++ procedure repairs an arbitrary partition by repeatedly transferring an eligible item to the minimum-valued bundle, but its termination time had no polynomial bound—even for simple additive valuations. Now, researchers Hannaneh Akrami, Arash Ashuri, Bhaskar Ray Chaudhury, Kurt Mehlhorn, and Maksim Soldatov show that a single deterministic tie-breaking rule fixes this. By fixing an ordering of items consistent with their singleton values and always transferring the highest-ranked eligible item, consecutive transfers strictly decrease in that ordering. The result: at most m transfers total, where m is the number of items, making the procedure polynomial-time. The algorithm also preserves fairness guarantees, never decreasing the minimum bundle value or increasing the maximum bundle value.

The breakthrough extends beyond additive valuations to the broader class of cancelable valuations—a generalization that captures non-additive preferences. As a direct application, the team achieves a polynomial-time algorithm for restricted additive chores that is simultaneously EFX, (1+ε)-MMS (maximin share), and a 2-approximation to optimal social cost, improving the previous state-of-the-art 4/3-MMS guarantee. To demonstrate the genuine power of cancelability, they construct a monotone cancelable ordering on five items that has no additive representation, proving the result is not just a restatement of known bounds. This work provides a clean, practical tool for multi-agent resource allocation, with implications for cloud computing, scheduling, and any system where items must be distributed fairly under computational constraints.