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 3 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 Envy-free up to one item, and up to any: three people, five items. A value matrix for three people, five items with two allocations beneath it: one envy-free up to one item but not up to any, and one envy-free; the counts over all 243 allocations beside it.

Envy that any single item would cure

Envy-free up to one item lets a person's envy be excused if removing the envied bundle's best item would cure it. The stronger standard asks that removing any item would — even the one that person values least. Every allocation of three people's items can be searched, and an allocation meeting the stronger standard was there every time; for two people cut and choose finds one, for three it took until 2020 to prove, and for four nobody knows.

applied · Fair division

Named alongside it

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

Envy-freenessFair divisionValuation measureAllocationConjectureConvexityCounting argumentDivide and chooseDualityEfficiencyExhaustive searchExistence proof

All concepts