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.
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.