The product that makes a division fair

The procedures that guarantee each person a fair share work by asking questions and cutting. There is a different way to arrive at a division, which asks for everyone’s values once and then chooses the division that is best by some measure of the whole group. The question is which measure.

The obvious candidates fail in instructive ways. Maximising the sum of everyone’s values gives each good to whoever values it most, which is efficient and can leave someone with nothing. Maximising the minimum protects the worst-off person and can waste goods that would help others at no cost to anybody. A third candidate, older than either as a principle of bargaining, is to maximise the product of everyone’s values — the Nash welfare, after John Nash’s 1950 solution to the bargaining problem. It sounds like a compromise between the other two. It turns out to have properties neither of them has.

Two people, four goods, three rules #

The frontier is the set of divisions nobody can improve on without making someone worse off. With linear values it is a polygonal line: the goods are handed over in order of the ratio of the two people’s values — person 1 gets first claim on good a, which they value 40 to person 2’s 25 — and each vertex is a point where one more good has changed hands. Every division on the frontier gives one person more exactly by giving the other less.

The three rules pick three different points. The sum is maximised at a vertex: give a and b to person 1, c and d to person 2, for values 70 and 50. The minimum is maximised where the frontier crosses the diagonal, at 59.1 each. The product is maximised where a level curve $u_1 u_2 = \text{constant}$ touches the frontier, which here is part way along an edge: person 1 gets all of good a and five-sixths of good b, for values 65.0 and 54.2.

At the product’s point nobody envies anybody. Person 1 values their own bundle at 65 and person 2’s at the remaining 35. Person 2 values their own at 54.2 and person 1’s at 45.8. At the sum’s point, person 2 values their own bundle at 50 and person 1’s at 50 — no envy either, by coincidence of these numbers — but a small change in the values breaks it, and the product’s point stays envy-free under every change, for a reason that comes from prices.

Where the product came from #

The product was not invented for dividing goods. Nash proposed it in 1950 as the answer to a bargaining problem: two parties who can agree on any of a set of outcomes, or fail to agree and fall back on a disagreement point. He listed conditions a reasonable settlement should satisfy — that it be efficient, that it treat symmetric parties symmetrically, that it not depend on the units each party measures gains in, and that removing outcomes nobody chose should not change the choice — and showed that exactly one settlement meets all of them: the one maximising the product of the two parties’ gains over the disagreement point.

The division problem is the special case in which the disagreement point is nothing at all. Every gain is then a value, and Nash’s settlement is the product’s maximum. The conditions carry their meaning straight over. Efficiency is the frontier. Symmetry is equal treatment of people with equal values. Independence of units is the property drawn in the next figure, and it is the condition that singles the product out from every other symmetric efficient rule.

That is the same kind of result as Shapley’s four conditions: a list of requirements that sound modest, each of which rules out a family of rules, and together leave exactly one. The difference is that Nash’s list produces a rule that is also envy-free for divisible goods, a property nobody put on the list — which is what makes the result feel less like a definition and more like a discovery.

A rule that ignores the units #

The first property that sets the product apart concerns what the people’s numbers mean.

A person’s values are a way of reporting preferences, and preferences have no natural unit. Saying a good is worth 40 and another 20 says the first is worth twice the second; saying 400 and 200 says exactly the same. A rule for dividing goods ought not to care which of those a person writes down.

The sum fails this completely. Multiplying one person’s values by three triples their weight in the total, and every good goes to them. The product does not move, because multiplying one person’s values by a constant multiplies every division’s product by the same constant, and the division with the largest product is still the one with the largest product. The product is the rule that respects each person’s scale — which is also why it is the natural rule to use when nobody’s units can be compared with anybody else’s, the situation interpersonal comparison always raises.

The minimum shares the product’s failure in a different way: rescaling one person’s values changes who counts as worst off, and the division chases that person’s inflated numbers.

Prices from equal budgets #

The envy-freeness of the product’s point is not a coincidence of the example, and the explanation is a market.

Give every person the same budget — one unit of money each. Put a price on every good. Each person spends their budget on whatever goods give them the most value per unit of money, and the prices are equilibrium prices if every good is exactly used up. The division that results is called a competitive equilibrium from equal incomes.

Envy-freeness is now immediate. Each person had the same budget and could have bought the other’s bundle; they bought their own because it was the best they could afford. So nobody envies anybody, and the market clears, so nothing is wasted: the division is efficient as well.

The connection to the product is a theorem of Edmund Eisenberg and David Gale from 1959. With linear values, the division that maximises the sum of the logarithms of people’s values — which is the division maximising their product — is exactly the competitive equilibrium from equal incomes, and the prices are the Lagrange multipliers of the maximisation. That is the same reading of prices that makes the dual of a linear program a list of rates: each good’s price is how much the objective would gain from a little more of it. The product’s point is envy-free because it is a market with equal budgets, and markets with equal budgets are envy-free.

The logarithm is also why the product behaves well. The sum of logarithms is a concave function of the division, so it has a single maximum and no traps, and concavity makes a person’s gain count for more the less they already have — a built-in preference for spreading value around that the sum lacks and the minimum overdoes.

Proportional too, and for free #

A division that is envy-free among $n$ people with divisible goods is automatically proportional: if nobody values another bundle above their own, then nobody’s own bundle can be worth less than $1/n$ of the whole to them, since the $n$ bundles add up to everything. The equal-budget market gives the same conclusion directly. With a budget of one and total spending of $n$, each person could have bought exactly a $1/n$ share of every good, and that share is worth $1/n$ of the whole; they bought something at least as good.

So the product’s division delivers, in one step and without a single cut query, the guarantee that halving procedures need $n \log n$ questions to deliver — along with envy-freeness, which those procedures do not provide. The difference is what each approach is allowed to know. The procedures learn about valuations one question at a time and have to cope with a cake whose value is spread in any shape; the product takes every value as given in advance, for goods that come in a small number of homogeneous kinds. Put the two side by side and the price of the query model is visible: it is the cost of not knowing the valuations up front.

The prices are also the same kind of object as the ones that settle an assignment of people to tasks. There, a price on each person and each task certifies that an assignment is cheapest; here, a price on each good certifies that a division is a market outcome. In both cases the certificate is a set of numbers produced by duality, and in both it lets a claim about a whole family of alternatives be checked one line at a time.

When the goods cannot be split #

Everything so far assumed the goods could be divided in any proportion. For indivisible items — a car, a piano, a painting — the prices argument collapses, and so does envy-freeness: with one item and two people, somebody envies whoever gets it. The subject’s response was to weaken the word: an allocation is envy-free up to one item if any envy one person has for another’s bundle disappears when some single item is removed from that bundle.

Round-robin picking achieves that weaker property. So does the product, and it achieves efficiency at the same time, which round-robin does not.

For indivisible items the rule needs one adjustment: if some allocation can give everyone a positive value, only those are considered, and among them the one with the largest product wins; otherwise the rule gives positive value to as many people as possible first. With that adjustment, the allocation maximising the product is always envy-free up to one item and always efficient. Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel Procaccia, Nisarg Shah and Junxing Wang proved it in 2016, in a paper whose title called the result the unreasonable fairness of maximum Nash welfare.

The proof is an exchange argument that the product makes almost automatic. Suppose person $i$ envies person $j$ even after any one item is removed from $j$’s bundle. Among $j$’s items, pick the one whose value to $i$ is largest relative to its value to $j$, and move it from $j$ to $i$. The strong envy guarantees that $i$’s value rises by proportionally more than $j$’s falls — and a product increases when one factor rises by a larger fraction than another falls. That contradicts the allocation having the largest product. So no such envy exists.

The search makes the theorem’s content visible and also its limits. The product never violates envy-freeness up to one item, as the theorem says it cannot. The sum violates it in over a third of instances. But when an outright envy-free allocation exists — in 281 of 300 — the product’s maximum is not always it, finding one only 191 times. The product guarantees the weaker property and efficiency together; it does not go looking for the stronger one.

The cost of the product for indivisible goods #

For divisible goods the product’s maximum is easy to compute: the logarithms make it a concave maximisation, solved exactly by convex programming, and for linear values by a combinatorial algorithm in polynomial time. For indivisible goods the picture reverses. Finding the allocation of largest product is NP-hard, and hard even to approximate within some constant factor, so the exhaustive search in the figures — 729 allocations per instance — is not a method but a demonstration, and at fifty items and ten people it would be hopeless.

What makes the rule usable anyway is that practical instances are small and structured, and integer-programming solvers handle them. The non-profit website Spliddit, built by some of the same authors, divides goods among people this way, asking each person to spread 1,000 points over the items and computing the product-maximising split. The theorem is the reason that choice is defensible to the people using it: whatever the allocation, each can check that removing one item from anybody else’s share would cure their envy.

Why not the sum with a fairness constraint #

A natural alternative is to maximise the sum subject to envy-freeness up to one item. For divisible goods the analogue — maximise the sum subject to envy-freeness — is a legitimate rule, and it can beat the product on total value.

Two things tell against it. It still depends on the units: rescaling a person’s values changes which constrained division has the largest sum, so the constraint does not repair the sum’s basic defect. And it is a combination of an objective and a constraint that has to be justified separately, while the product produces envy-freeness without being asked. A single objective that is scale-free and fair as a consequence is a stronger argument for a rule than an objective that needs a fairness constraint bolted on, and it is the reason the product is the rule the theory keeps returning to.

What the searches and frontiers leave out #

The frontier figures are two people with four divisible goods, and the theorem that the product’s point is a competitive equilibrium holds for any number of people and goods; the two-person picture is the only one in which the frontier can be drawn as a line.

The search over 300 instances confirms the indivisible theorem on 300 instances of one size. The theorem is proved for every instance by the exchange argument, and nothing about random instances of six items could have established it — or could establish the negative facts, such as how badly the product can do at finding outright envy-free allocations when they exist, which the counts only sample.

And the values drawn are additive: a bundle is worth the sum of its items. When items complement each other — two shoes, or a car and its keys — additivity fails, and so does the theorem. For such values the product’s maximum need not be envy-free up to one item, and much less is known.

Still open: envy-free up to any item #

Envy-freeness up to one item allows the envy to be cured by removing the item the envious person likes best from the other’s bundle. A stronger version asks for more: envy-free up to any item, where removing any single item, even the one the envious person values least, is enough.

For two people such allocations always exist, and in 2020 Bhaskar Ray Chaudhury, Jugal Garg and Kurt Mehlhorn proved that they always exist for three people with additive values. For four or more people nobody knows whether an allocation envy-free up to any item always exists. The product’s maximum is known not to be one in general, exhaustive searches have found no counterexample, and the question has become one of the central open problems of the subject — a statement about finitely many items and finitely many people, checkable in every instance, and unresolved.

A compromise that is not a compromise #

Maximising a product looks at first like splitting the difference between an aggregate and an egalitarian rule. It is not in between them. It is the one rule of the three that does not care what units people report in, the one whose optimum is a market with equal budgets, and the one that is envy-free for divisible goods and envy-free up to one item for indivisible ones — as a consequence, not by constraint.

The reason all of that comes from one objective is the logarithm. Maximising a product is maximising a sum of logarithms, and a sum of logarithms is scale-free because the logarithm turns a rescaling into a constant shift, concave because the logarithm is, and priced by equal budgets because its derivative, one over a person’s value, is exactly the weight a market with equal incomes gives them.