A Simple Polynomial-Time EFX Repair for Cancelable Valuations

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 $\epsilon >0$, we compute in polynomial time an allocation of restricted additive chores that is simultaneously EFX, $(1+\epsilon )$-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.