New Math Shows How to Split Scarce Goods Fairly, Instantly

Every day, computers hand out things that can't be taken back — a delivery driver gets a job, an advertiser wins a slot, a shopper grabs a seat. Computer scientists call this "online fair division," and it's genuinely hard, because you must decide instantly and live with the result. Three researchers — Saar Cohen, Nicholas Teh and Michael Wooldridge — have published new math showing how to do it noticeably better than before.

Fairness here has technical names worth translating. "PROP1" means everyone ends up with something almost as good as their fair share, allowing for one item they'd rather swap. "EF1" means nobody envies anyone else by more than a single item. Earlier work guaranteed each person a fraction of their fair share that shrinks as the group grows. The new method shrinks far more slowly, so the guaranteed slice stays bigger, and a version of it gives each person nearly their whole ideal bundle.

The paper also delivers bad news, and this is the honest catch. Some fairness hopes are mathematically impossible. If someone picks the worst possible order in advance, no clever algorithm can reliably avoid envy — the odds collapse to almost zero, and with as few as n+1 items the chance can fall to one over n-factorial. For another fairness standard ("maximin share"), the odds never beat five in six, no matter how generous your definition.

There's a silver lining: if you allow a few items to be reassigned or removed — roughly a logarithmic number, which grows very slowly — plain random allocation gets arbitrarily close to perfectly fair. That's a surprisingly simple recipe. No app ships this tomorrow, but it tells auction designers, gig platforms and cloud providers what is actually achievable, and warns you not to believe anyone promising a perfectly even split.