Dividing the indivisible

The problem of how to fairly divide goods between people has been around since the dawn of humanity. Even the Hebrew Bible mentions it. In the book of Genesis (13: 5-13), Abraham and Lot divide a piece of land using the I cut, you choose method, which has one person dividing the land in two and the other choosing the piece he prefers.

This works well when you are trying to share something you can divide any way you like, like a piece of land or a cake. But what if the goods you are trying to share out are indivisible? This happens, for example, in divorce cases, or when dividing an estate among relatives of a deceased person. You can't cut a flat screen TV or diamond ring, so how should you go about sharing out the goods in a way that causes the least resentment?

Some easy methods

The NA method: An example

Suppose there are six items labelled 1, 2, 3, 4, 5 and 6, and that the preference rankings, in descending order, are:

A: 1 2 3 4 5 6 B: 2 3 1 5 6 4. Since the two top items are different, allocate 1 to A and 2 to B. The rankings of the remaining items (assuming the players don't change their minds) are: A: 3 4 5 6 B: 3 5 6 4. Since item 3 is top on the list for both, it goes into the contested pile. The rankings for the remaining items are: A: 4 5 6 B: 5 6 4. Since the two top items are different, allocate 4 to A and 5 to B. This leaves item 6 on each player's list, which also goes into the contested pile. So the final allocation is:

A gets 1 and 4; B gets 2 and 5. The contested pile contains 3 and 6.

Let's suppose the goods are to be divided between two people, A and B, whom we will refer to as players. (Since we don't care about whether A and B are male or female, we will also use the pronoun "it" when referring to them.) Let's also suppose that each can rank the items on offer in order of preference, with no two items occupying the same rank, and that both players are honest about their preferences. You could get A and B to take turns in picking items, but this puts the person who goes first at an advantage. For example, if both players have the same item at the top of their list, then the one who goes first is the one who gets it, to the detriment of the other. The same goes for any other item that occupies the same rank for both players.

To avoid this problem, Alan J. Taylor and I came up with another method, equally simple. Start with the items that are on the top of the players' preference lists. If the two items differ — say A wants the car and B wants the house — then each gets its preferred item. If they are the same — both want the house — the item goes into a contested pile. Now ask both players to list the remaining items in order of preference and repeat, until every item has either been allocated or gone into the contested pile (which will then have to be dealt with separately). Let's call this method for allocating items Noncontested Allocation (NA). See the box for an example.

In the unlikely event that both players have exactly the same preferences, all items will go into the contested pile and we will have to select another method for parcelling out the items. But if this isn't the case — and in practice it rarely is — this algorithm has an advantage over simply taking turns: the allocation (of the noncontested items) it produces is envy free.

Avoiding envy

To see what we mean by this, let's look at an example. Suppose there are six items labelled 1, 2, 3, 4, 5 and 6. Suppose that player A's preference ranking (in descending order) is:

A: 1 2 3 4 5 6

and that it has received items 1, 3 and 5. It might of course grumble over not having received 2 rather than 3, or 4 rather than 5, but overall the situation is quite satisfactory. You can pair each item A did receive with an item it didn't receive, so that A prefers its own item in the pair over the other: 1 is preferable to 2, 3 is preferable to 4, and 5 is preferable to 6.

Who gets this beauty?

We can generalise this intuition and phrase it in mathematical language. Write $S_ A$ for the set of items that have been allocated to A and $S_ B$ for the set of items that have been allocated to B. We assume that the sets $S_ A$ and $S_ B$ contain the same number of items. We say that the allocation is envy free from A’s point of view if there is a function

$f_ A: S_ A \rightarrow S_ B,$

(which associates to each item $x$ in $S_ A$ an item $f_ A(x)$ in $S_ B$ ) so that for all items $x$ in $S_ A,$ player A prefers $x$ to $f_ A(x).$ We require that the function $f_ A$ matches items in $S_ A$ and $S_ B$ pairwise, so that for no two items $x_1$ and $x_2$ in $S_ A$ do we have $f_ A(x_1) = f_ A(x_2).$ In technical language, $f_ A$ is required to be an injection.

Similarly, we say that the allocation is envy free from B’s point of view if there is an injection

$f_ B: S_ B \rightarrow S_ A,$

(associating to each item $y$ in $S_ B$ an item $f_ B(y)$ in $S_ A$ ) so that for all items $y$ in $S_ B,$ player B prefers $y$ to $f_ B(y).$

We say that an allocation is envy free (overall, for both players) if there are two functions $f_ A$ and $f_ B$ satisfying the above conditions.

To illustrate this, let's suppose that, as before, A's preference ranking of the six items is

A: 1 2 3 4 5 6,

and that B's preference ranking of the same items is

B: 2 4 6 1 3 5.

A receives 1, 3 and 5, so $S_ A=\{ 1,3, 5\}$ and $S_ B=\{ 2,4, 6\} .$ The functions $f_ A$ and $f_ B$ defined by

$f_ A(1) = 2, f_ A(3)=4, f_ A(5)=6$

and

$f_ B(2)=1, f_ B(4)=3, f_ B(6)=5$

show that the allocation is envy free from both players’ points of view, so it is envy free overall. (In this example the two functions are inverses of each other — one is the reverse of the other — but this need not generally be the case.)

In practice, in a divorce case or when there is an estate to divide up, there may not always be an envy free allocation of all the items. As we have seen above, the algorithm NA may only allocate some of the items, leaving the rest in the contested pile. But it turns out that if any items are allocated, then that allocation is always envy free (you can check this for yourself for the example in the box above).

An even better method

The AL method: An example

Suppose there are four items labelled 1, 2, 3, 4, and that the preference rankings, in descending order, are:

A: 1 2 3 4 B: 2 3 4 1.

Since the two top-ranked items are different, allocate item 1 to A and item 2 to B. Of the remaining items, A and B both prefer 3 next. Let's consider giving 3 to B and the only remaining item, 4, to A. This is not an envy free allocation, because we can't pair item 4 (in A's share) with any item in B's share that A likes less than 4.

So let's try allocating item 3 to A and 4 to B. Now the allocation is envy free from A's point of view, as A prefers 1 to 2 and 3 to 4. It's also envy free from B's point of view, as B prefers 2 to 3 and 4 to 1. Thus, the final allocation is:

A gets 1 and 3; B gets 2 and 4.

Applying the simpler algorithm NA to this example would result in a contested pile containing 3 and 4. So the example also shows that AL can yield a complete allocation when NA would only be able to allocate some of the items.

This is good, but the problem is that NA may not find the largest envy free allocation, that is, the one with the smallest contested pile. There is help, however. D. Marc Kilgour, Christian Klamler and I devised a second algorithm, related to NA, that does just that. We start as we did before. If both players rank different items at the top of their preference list, then each gets its preferred one. If the top item is the same, it goes to the contested pile, and you repeat the process for the second item on each player's list. If this is the same for both, put it into the contested pile and move to the third, and so on. Unless the preference rankings are exactly the same, the players will each be allocated an item at some point.

Once that has happened, proceed as follows. Look at the remaining items and see which comes first on each player's list. If the two are different, allocate them accordingly. If they are the same, then check if there is a way of allocating this item to one player and another item to the other that does not cause envy. If there is, then allocate the two items accordingly, and repeat the process for the remaining items, descending down the players' preference lists. See the box for an example.

This method is called AL (for "algorithm"). It is more complicated than NA, though not for the players themselves: all they have to do is submit their preference lists to the person applying the method (or a computer). The advantage is that AL is guaranteed to find the largest envy free allocation there is.

If it's not bigger, is it better?

What happens if there are other largest envy free allocations that dole out the same number of items but in a different way? AL may find more than one: when you hit upon an item desired by both players at the same time applying AL, you check to see if you can allocate it and a less preferred item without causing envy. There may be several ways of doing this. What is more, AL finds all the "best" allocations, where "best" is defined in the following way.

Suppose that two methods allocate different sets $S_ A$ and $T_ A$ to player A, with both sets containing the same number of items. We say that A likes $S_ A$ at least as much as $T_ A$ if there is an injection

$g_ A: S_ A \rightarrow T_ A,$

so that for any item $x$ in $S_ A$ , player A likes $x$ at least as much as $g_ A(x)$ . If for some $x$ in $S_ A$ the preference is strict, then we say that A prefers $S_ A$ to $T_ A.$

In an analogous way we can define when player B likes a subset $S_ B$ at least as much, or prefers it to, a subset $T_ B.$

We say that an allocation that gives set $S_ A$ to A and set $S_ B$ to B Pareto-dominates the allocation that gives set $T_ A$ to A and set $T_ B$ to B if A likes $S_ A$ at least as much as $T_ A$ and B likes $S_ B$ at least as much as $T_ B,$ with at least one player actually preferring its allocation under $(S_ A, S_ B)$ . An allocation that is not Pareto-dominated by any other allocation is called Pareto-optimal. It is possible to show that AL finds all maximal envy-free allocations that are Pareto-optimal.

Conclusion

Perhaps these algorithms can settle disputes more amicably.

The obvious question now is what to do with the contested pile. The answer is that you will have to use different, more sophisticated algorithms to deal with it. Some of these might involve getting more information from the players about their preferences. But both the algorithms we looked at, in particular AL, work very well when players have different tastes. This is quite often the case, for example in divorces: one partner may be keen on all the gardening tools, while the other prefers the electronic gadgets. Their preference lists will be sufficiently different to allocate a reasonable number of items in an envy free way, before getting down to the hairy business of the contested pile.

Both methods, NA and AL, have the advantage of being very simple to use. All you need is a preference list from each player, and you can easily program a computer to perform them routinely. NA has the added advantage that players can change their minds about their preferences after an allocation has been made. This is useful: if one of a pair of matching armchairs has been allocated to your adversary, you probably lose interest in the other. AL doesn't allow such chopping and changing, but there is a way around this too. Package items into batches (two matching armchairs are considered as one item) that are as independent of each other as possible.

We believe that our algorithms, in particular AL, might help to settle many divorces, as well as other disputes over property, more amicably. AL is eminently practicable. If there is not an envy free division of all items, it will find the largest number that can be divided in an envy free way, saying who gets what.

About the author

Steven J. Brams is Professor of Politics at New York University. He is the author or co-author of 15 books that involve applications of game theory and social choice theory to voting and elections, bargaining and fairness, international relations, and the Bible and theology. His most recent books are Game Theory and the Humanities: Bridging Two Worlds (2011) and Mathematics and Democracy: Designing Better Voting and Fair-Division Procedures (2008) (both reviewed on Plus, follow the links); and two books on fair division with Alan D. Taylor, The Win-Win Solution: Guaranteeing Fair Shares to Everybody (1999) and Fair Division: From Cake-Cutting to Dispute Resolution (1996).

He is a Fellow of the American Association for the Advancement of Science, the Public Choice Society, and a Guggenheim Fellow. He was a Russell Sage Foundation Visiting Scholar and has been President of the Peace Science Society (International) and the Public Choice Society.

Plus.Maths.org