Twice as many goods as people

A cake can be cut anywhere, and every theorem about cutting it fairly — one cuts and the other chooses, the trimmed piece for three, the moving knives — uses that freedom. Goods that cannot be cut are another matter. Two people and one painting cannot be made envy-free; neither can three people and two cars. Envy-free, up to one item answered by weakening the demand: allow envy, provided it would vanish if one good were taken out of the envied bundle, and such an allocation always exists. Envy that any single item would cure tightened the weakening again and found the question open.

This essay asks a different question about the original, unweakened demand. Envy-free allocation is sometimes impossible. How often? If people’s values for the goods are drawn at random, what is the chance that some way of handing out the goods leaves nobody preferring anybody else’s bundle — and how does it depend on how many goods there are per person? The answer has a sharp shape: almost never with one good each, almost always with two.

What envy-free means for goods #

Each person has a value for each good, and values her bundle at the sum of its goods’ values; the values here are drawn independently and uniformly between 0 and 1. An allocation gives every good to somebody. It is envy-free if each person values her own bundle at least as highly as she values each other person’s bundle. In the hero, Ada values her bundle at 0.86, Ben’s at 0.85 and Cy’s at 0.34; Ben’s own is worth 1.83 to him, against 0.64 and 0.75; Cy’s own is 1.29 to her, against 1.05 and 1.24. Close, in places, but nobody would swap.

Whether such an allocation exists can only be decided, in general, by search. Even for two people with identical values it is the partition problem — can a set of numbers be split into two halves of equal sum — which is one of the classical problems for which no fast method is known, and envy-freeness with more people is at least as hard. The figures decide every random instance exactly, by assigning goods one at a time and abandoning a partial assignment as soon as somebody’s envy exceeds everything she could still gain from the goods not yet assigned. That pruning makes instances with an envy-free allocation quick and instances without one slow, and it is why the experiments stop at five people.

The sizes involved explain why pruning matters. Three people and six goods have $3^6 = 729$ allocations, few enough to list. Five people and eleven goods have $5^{11}$, about 49 million, and a search that had to visit them all for each of a hundred instances would take far too long. The pruning rule cuts most of them away early: once the goods assigned so far have given someone a rival bundle she values more than her own by a margin larger than the total value she places on all the unassigned goods, nothing later can repair it, and the whole branch below is skipped. An instance that has an envy-free allocation is usually settled after a few hundred steps. One that has none must be refuted branch by branch, and those instances, clustered just below two goods per person, take almost all of the computing time.

The hero’s allocation also shows how thin the margins can be. Ada’s own bundle is worth 0.86 to her and Ben’s is worth 0.85; a small change in one of her values would turn this allocation into one with envy, and the search would have to look for another.

The curve #

The shape is the same for every number of people. With fewer goods than people it is impossible, because somebody receives nothing and envies anybody holding a good she values. At exactly one good each it is uncommon, and less common with more people: 0.54 with two, 0.23 with three, 0.10 with four, 0.05 with five. Then the curve climbs. Between one and two goods per person it passes from rare to almost certain, and at two goods per person, the dashed line, it stands between 0.90 and 0.99. Just beyond, the experiments met no instance at all without an envy-free allocation.

The climb is steepest with the most people. With five people, nine goods leave 0.59 of instances shareable and ten goods leave 0.99. A single extra good, the one that brings the count to two per person, almost removes the possibility of unavoidable envy.

One good each #

The bottom of the curve can be computed exactly. If there are exactly as many goods as people, everyone gets one good. A person who does not get her favourite good envies whoever does. So an envy-free allocation exists exactly when the people’s favourite goods are all different, in which case each takes her own favourite.

With independent random values, each person’s favourite is equally likely to be any of the $n$ goods, independently of everyone else’s, so the chance that all $n$ favourites differ is

$$\frac{n!}{n^n},$$

which is $1/2$ for two people, $2/9$ for three, $3/32$ for four, and about one in 160 for seven. It is the same count as the chance that $n$ people have different birthdays in a year of only $n$ days — the birthday problem at its most crowded. By Stirling’s formula it falls like $e^{-n}$ times a slowly growing factor, so with many people and one good each, envy is unavoidable almost always. The same argument, that envy-freeness with one good each is a question about a perfect matching of people to favourite goods, is the simplest case of the condition in Hall’s theorem, where the obstruction is a group of people with too few acceptable goods between them.

Why two each is enough #

The jump at two goods per person has been made precise. In 2014 John Dickerson, Jonathan Goldman, Jeremy Karp, Ariel Procaccia and Tuomas Sandholm proved that with independent random values an envy-free allocation exists with probability tending to 1 once the number of goods grows faster than $n \log n$, and fails with probability tending to 1 when there are only slightly more goods than people. Pasin Manurangsi and Warut Suksompong then found the true threshold in 2020, and it depends on arithmetic. If the number of goods is a multiple of the number of people, two goods each already suffice with probability tending to 1. If it is not, much more is needed: about $n \log n / \log\log n$ goods.

The reason for the divisibility is that envy-freeness with random values is mostly a question of counting. When every person gets the same number of goods, each can be given goods she values highly — near the top of her own ranking — and the bundles are comparable. When the goods do not divide evenly, someone gets fewer goods than someone else, and with random values the person with fewer goods tends to value the larger bundle more, unless her few goods are exceptionally good for her; that requires many goods to choose from. In the small experiments here the divisibility effect on existence is faint, because with three to five people $\log n/\log\log n$ is barely larger than 2. It shows clearly in the next figure but one, where the allocation is made by a fixed procedure rather than found by search.

The person with the fewest goods #

The side panel of the curve figure gives the share at $2n - 1$ goods beside the share at $2n$: 0.69 against 0.90 for two people, 0.56 against 0.94 for three, 0.59 against 0.95 for four, 0.59 against 0.99 for five. One good fewer than two each costs a third or more of the instances, and the reason can be seen by thinking about who gets least.

With $2n - 1$ goods, if nobody is to have a bundle much larger than anyone else’s, then one person gets a single good while everyone else gets two. That person must value her one good at least as highly as she values every two-good bundle. Her values are uniform, so each two-good bundle is worth, to her, a sum of two uniform numbers, which averages 1; her single good is worth at most 1. She can be content only if she is given something near the top of her own scale and the others’ pairs are made of goods she happens to value little. Both are possible, and in about half of the instances the search finds a way to arrange them, but there is no slack. With $2n$ goods everyone can have two, the comparison is between pairs on both sides, and the slack appears at once.

The same reasoning explains why unevenness can be worse than scarcity. Giving the single-good person a second good from someone else’s bundle only moves the problem: now that someone has one good. With a count not divisible by $n$ there is always a person at the short end of the distribution, and her envy is the binding constraint. Manurangsi and Suksompong’s theorem says that for large $n$ it stays binding until the goods are so many that the short person can be given goods so good, by her own values, that a bundle of one fewer still wins — and that takes a logarithmic number of goods per person, not two.

A weaker standard #

Envy-freeness compares bundles. Proportionality asks only that each person value her own bundle at least $1/n$ of her value for everything. With additive values envy-freeness implies it: a person who values her own bundle at least as highly as each of the other $n - 1$ values it at no less than the average, which is $1/n$ of the total.

The proportional curve always lies above the envy-free one, and the gap is widest when goods are few: with three goods, 0.57 against 0.23, and with five, 0.87 against 0.56. The gap is instances in which every person can be made content with her share of the total and yet someone still prefers somebody else’s bundle. By six goods both are near 1. Proportionality is the guarantee that the oldest cake-cutting procedures deliver, and with indivisible goods it fails for the same reason envy-freeness does, the shortage of goods to spread.

A draft gets close and rarely gets there #

How would anyone find an envy-free allocation in practice? The simplest procedure is a draft: the people take turns, as in picking sides for a game, each choosing her favourite remaining good. It needs no search and no knowledge of anyone else’s values.

The draft always achieves envy-freeness up to one good. Whenever a person picks, she takes something at least as good, by her own values, as what the next person takes on the next pick; so her picks dominate everyone’s after her, and the only good she can envy is someone’s first pick before hers. But envy-free outright is another matter. With three people the draft’s result is envy-free in 0.48 of instances at six goods, 0.72 at nine and 0.92 at twelve, while some envy-free allocation exists at six goods in 0.94 of them. Between the multiples of three the draft’s share falls back or stalls: at seven and eight goods it is 0.45, because the first person in the order gets an extra good and the last person envies her.

So the divisibility that the theorem predicts appears here clearly, in the procedure rather than in existence. The draft is the same mechanism that the product of utilities improves on: a rule that is easy to run and fair up to a single good, but leaves envy that a cleverer allocation of the same goods would remove.

Five goods, no way out #

The last figure shows an instance from the gap. Five goods among three people means somebody receives at most one good. In this instance, whoever receives just one good values at least one of the other bundles more, whatever single good she is given and however the rest are split. All 243 allocations were checked. The least bad of them leaves a largest envy of 0.168, out of values that run up to about 1. At five goods, 31% of random instances are like this — shareable proportionally, but not without envy — and at six goods, 6%.

Envy that stops suddenly #

The surprising thing is not that envy can be unavoidable; it is how suddenly it stops being so. Random problems of many kinds show such thresholds. A random graph becomes connected at a sharp threshold in the number of edges, and a random logical formula becomes unsatisfiable at a sharp threshold in its number of clauses. Here the parameter is goods per person, and the threshold sits at two for every number of people tried, provided the goods divide evenly. Fair division, which is usually a matter of clever procedures and existence theorems, turns out to be, for random preferences, a matter of having enough goods.

There is a second surprise in the dependence on arithmetic. Whether there are 14 or 15 goods among 7 people — two each, or two each and one over — changes the asymptotic answer from almost always to almost never, until the number of goods is far larger. A count that is not a multiple of the number of people is not “slightly worse” but qualitatively worse.

Estimates from a few hundred instances #

The curves are estimates from samples of 100 to 400 instances per point, so each value has a sampling error of a few hundredths; the step from 0.59 to 0.99 at five people is far outside that error, but the exact heights are not. More importantly, the experiments reach only five people, and the theorems are about what happens as the number of people grows. The threshold at $n \log n/\log\log n$ for goods not divisible by $n$ cannot be seen at all at this scale, and the figures say nothing for or against it.

The values are independent and uniform. Real preferences are correlated — everybody wants the best car — and correlated values make envy-free allocations much rarer, since people compete for the same goods. The results describe random problems, not hard ones.

Allocations searched, the thresholds quoted #

Computed here: the existence of an envy-free allocation for every sampled instance, by exhaustive search with pruning, with each allocation found checked directly; the one-good-each case checked to coincide with distinct favourites on 200 instances, and the share of distinct favourites on 3,000 instances for each $n$ from 2 to 7 against $n!/n^n$; proportional existence by the same search; the draft’s result for 600 instances at each count of goods from 3 to 21, checked to be envy-free up to one good every time; and the instance with five goods, checked on all 243 allocations.

Quoted: the theorems of Dickerson, Goldman, Karp, Procaccia and Sandholm, and of Manurangsi and Suksompong, and the hardness of deciding existence in general.

Still open: the threshold for other preferences #

For independent uniform values the threshold is now known. For other random models it is largely open. When values are correlated — each good has a common quality, and people’s values are that quality plus private noise — the number of goods needed for envy-freeness with high probability is not known in general, and the experiments that exist suggest it grows much faster. The same question for chores, where everything has negative value and people want less rather than more, has been studied more recently and its thresholds are only partly settled. And for the weakening of envy-free up to any item, whether such allocations exist for every instance with four or more people is the open problem that essay ended on; for random instances they exist with high probability, which is a statement about typical cases and not about the worst.

Enough goods to go round #

Random goods can be shared without envy only rarely when there is one good each — exactly when everyone’s favourite differs, with chance $n!/n^n$ — and almost always when there are two each. Exact search over every sampled instance shows the climb between, steepest with the most people. A draft is always fair up to one good but envy-free outright only in steps, when the goods divide evenly among the people, which is the arithmetic that the threshold theorems turn into a dichotomy.