The problem of fairly dividing a divisible good, such as cake or land, between two people probably goes back to the dawn of civilization. The first mention I know in Western literature of the well-known procedure, "I cut, you choose," occurs in the Hebrew Bible, wherein Abraham and Lot divide the land that lies before them, with Abraham obtaining Canaan and Lot obtaining Jordan (Genesis 13: 5-13).
But this problem pales in comparison to that of fairly dividing indivisible items, such as in a divorce or in the division of an estate between two heirs. Recently, however, two colleagues and I came up with an algorithm for doing precisely this, whose technical details can be found in an article in the February 2014 issue of the Notices of the American Mathematical Society. We assume that an even number of items is to be divided, and we want (1) each person to get exactly half the items, (2) neither person to envy the other for the items it gets ("envy-freeness"), and (3) there to be no better division for both people ("efficiency").
A simple example will illustrate how this can be done. Suppose there are four items that person 1 (P1) and person 2 (P2) want to divide, with each person to get two of the items. Assume P1 and P2 rank the items -- an artwork (A), a boat (B), a car (C), and a desk (D) -- from best to worst as follows:
P1: A > B > C > D
P2: B > C > D > A
It seems clear that P1 should get A, because it's P1's first choice and P2's last choice. But it's not so obvious how to divide the remaining three items, giving one to P1 and the other two to P2, because both people rank the remaining three items exactly the same way (B > C > D).
A common way that the spouses in a divorce divide the marital property is that they make alternating choices. Suppose P1 starts. He will choose A, and P2 will then choose B, which would also be true if P2 starts. But now there is a problem: The next item that has not already been allocated is one both people want, namely C.
Isn't it unfair to give the person who started the next choice, which will be C, leaving D to the other person? If P2 had started, she will end up with B and C (her two best choices), whereas P1 will get only his best and fourth-best choices, which is not envy-free.
If we want to prevent envy, can we allocate the items so that P1 prefers each one of his two items to a different item of P2, and P2 prefers each one of her items to a different item of P1. The answer is yes -- if we give P1 A and C, and we give P2 B and D -- because:
P1 prefers A to B and C to D
P2 prefers B to C and D to A
Presumably, if there is such a pairwise matching of individual items, each person will prefer his or her package to the other person's, which we call an envy-free division.
Unfortunately, there may be not be an envy-free division of all the items. But what our fair-division algorithm does find is a matching that allocates, in an envy-free way, as many items as possible. Here is a six-item example:
P1: A > B > C > D > E > F
P2: B > C > A > E > F > D
There are 20 possible ways of dividing these items into two three-item packages, so it would be really tedious to test whether any one is envy-free.
Our algorithm quickly shows that there is not one. But it also shows that there is an envy-free division of four of the six items: Give P1 items A and D, and give P2 items B and E. (Can you show that this is an envy-free division?) As for the left-over items, C and F, we put them into a "contested pile," for which there are other algorithms to divide them if there are sufficiently many (two is too few, because both people prefer C to F in the example).
Our algorithm is eminently practicable, requiring only that two people rank the items they are trying to divide from best to worst. If there is not an envy-free division of all of them, it will find the largest number that can be divided in an envy-free way, saying who gets what. Might it not help to settle many divorces, as well as other disputes over property, more amicably?
Steven J. Brams is a professor in NYU's Wilf Family Department of Politics. He is the author of Game Theory and the Humanities: Bridging Two Worlds (2011) and Mathematics and Democracy: Designing Better Voting and Fair-Division Procedures (2008), among other works.