Envy-Free Division

A division of some resource among several people is envy-free if every person values their own share at least as much as they value any other person's share, using that person's own private valuation. This is a weaker, easier-to-achieve standard than "everyone gets an equal-value share" — it only requires that nobody looks across the table and wishes they had swapped, not that the pieces are literally equal by some outside measure. Two people can each honestly believe they got the better deal, and the division is still envy-free, because each is judging by their own taste.

The classic two-person solution is divide-and-choose: one person cuts a cake into two pieces they consider equal, and the other picks whichever piece they prefer. The cutter cannot complain, because by their own valuation the two pieces were equal; the chooser cannot complain, because they picked the piece they liked more. For three or more people the problem gets substantially harder — the Selfridge–Conway procedure handles three-person envy-free division of a divisible good in a bounded number of cuts, but no such bounded procedure was known for four or more people until relatively recent, complicated algorithmic results.

Interviewers use this family of puzzles to test whether a candidate can separate "fair by some absolute measure" from "fair given only what each party privately says they want," which is exactly the distinction that matters when splitting P&L, workload, or ownership stakes among people who don't all value the same things equally.