Dividing the Indivisible


Steven J. Brams in Plus Magazine:

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?

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.

More here.