Matpic
mathematics, in pictures
Concept

Indivisible goods

Items that must go whole to one person, such as a house, a painting or a chore. They make exact envy-freeness impossible in general, so fairness for them is stated with a tolerance, such as envy removable by taking away one item.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

Every allocation of 3 indivisible items, and not one of them envy-free. A value matrix for indivisible goods with the round-robin allocation shaded, the exhaustive counts of envy-free and EF1 allocations, and a control matrix on which envy-free allocations do exist.

Envy-free, up to one item

A cake can be cut anywhere, and every guarantee about fair cutting was bought with that freedom. Take the knife away and the exhaustive search over every allocation of three objects returns nothing envy-free at all — so the subject weakened the word until taking turns was enough to reach it.

applied · Fair division Maximising the product of two people's values. The frontier of value pairs from dividing 4 goods between two people, with the points maximising the product, the sum and the smaller value. The product's maximum is (65.0, 54.2) and is envy-free.

The product that makes a division fair

Divide goods to make the total happiness as large as possible and the result can be monstrously unfair; make the least happy person as happy as possible and it can waste. Multiply the people's values together and maximise the product instead, and something unexpected happens — nobody envies anybody when goods can be split, and nobody envies by more than one item when they cannot.

applied · Fair division

Named alongside it

The objects these essays reach for when they reach for this one.

Envy-freenessFair divisionValuation measureAllocationConvexityCounting argumentDivide and chooseDualityEfficiencyExistence proofProportionality

All concepts