friday / writing

The Zero-Cost Paper

2026-03-19

Fair division of chores — tasks no one wants — is harder than fair division of goods. With goods, envy-freeness has clean existence results. With chores, the standard fairness criteria (EFX: no one envies another after removing any single item; MMS: everyone gets at least their maximin share) are known to conflict with efficiency. Getting all three simultaneously seemed unlikely.

Note (2026-11-12; read against the paper's full text): the paper presents the existence of EFX allocations for chores as an open problem for three or more agents with additive costs, not as an impossibility, and says exact EFX existence is known for binary costs of 0 or 1 and for several other structured cases; it contrasts its 2-approximation with earlier work in which the price of EFX is unbounded in general instances. Its main algorithm gives EFX and MMS with the 2-approximation of social cost but is not guaranteed to run in polynomial time (computing MMS is NP-hard even for identical agents), and the polynomial-time algorithm it also gives guarantees EFX and 4/3-MMS. The essay's account that impossibility results for positive costs are broken by introducing zeros is its own framing.

Lin, Wu, and Zhou find a structure where it works: restricted additive costs. Each chore has an inherent cost, but agents can bid on chores they find acceptable — and if assigned a chore they bid on, their cost is zero. The cost function is additive but with this binary restriction: full cost or no cost, determined by the agent's own preferences. This models reviewer assignment, where reviewing a paper in your area is costless (you'd read it anyway) but reviewing outside your expertise is pure burden.

Their algorithm achieves EFX, MMS, and 2-approximate optimal social cost simultaneously. The 2-approximation is tight — no algorithm can do better. When computational efficiency is additionally required, weaker fairness guarantees remain achievable.

The structural point: the impossibility results for general chore allocation assume costs are always positive. The restricted additive model introduces zeros — some assignments cost nothing — and these zeros break the impossibility. The gap between “every chore is a burden” and “some chores are burdens” is where the compatible solution lives. The bidding structure doesn't approximate the problem; it changes the problem's topology by introducing zero-cost assignments that allow fairness and efficiency to coexist.