If you want to find a way of dividing up some indivisible items between entities then here is a way to do it that eliminates envy as the outcome. The suggestion is that this could be a good way to divide up possessions during a divorce - algorithms get into everything.

There are already techniques for sharing resources in a way that is fair using a distributed system.  The best known is the "you cut I choose" method of sharing a cake. There are also algorithms that allow the division of a cake between multiple participants such that each has to be satisfied with the outcome in the sense that they feel that they may not have got as much cake as they wanted but at least they got as much as their "opponents". 

A more complex problem than dividing a continuous resource is the task of sharing out indivisible items among a group of people each of whom assigns a different set of values to the items. A new paper by New York University’s Steven Brams, Wilfrid Laurier University’s D. Marc Kilgour, and the University of Graz’s Christian Klamler and published this month in Notices of the American Mathematical Society, outlines a pair of algorithms.

The first previously known algorithm, BT, has the two players A and B make independent choices of their most preferred items in the set of items yet to be allocated. If A and B name two different items then they each get the item they desire.  If they name the same item then it is put into the Contested Pile, CP. This continues until all items have been allocated or placed in the CP.

This algorithm finds an allocation that is Envy Free (EF) in the sense that each player receives the same number of items and each player prefers the subset of items they have. The idea of EF is actually quite subtle. Basically it comes down to the fact that for every item A has there is an item of B's that is less desired.

Another way of saying this is that if for each item x that A has the number of items belonging to B that A prefers to x is not greater than the the similar number of items that A has and prefers to x .

The important thing about an EF assignment is that there is no alternative assignment that both parties would prefer on the basis of their rankings. 

For example if the rankings are:

A: 1 2 3 4 

B: 2 3 4 1

then using the algorithm A gets 1 and B gets 2. The new ranking is:

A: 3 4 

B: 3 4

Now we have a tie so the 3 goes into the CP and so does 4. Thus the final allocation is A gets 1 and B gets 2 and two items are not distributed as CP={3,4}

This algorithm is fast and it allows each person to assign rankings as the division proceeds, and thus take account of changing usefulness, e.g. if you don't get the TV there is no point in having the game console. The big problem with it is that it doesn't always find the maximal EF assignment.

The paper presents a slightly more complex algorithm, AL, that will always find a maximal assignment in the sense that there isn't another EF assignment that allocates more items to the players.

Roughly the algorithm works in the same way until there is a tie when it attempts to find an assignment of the tied item to either A or B and another item that results in an envy free assignment. Exactly how this is done is a matter of actually trying out a test assignment of all of the possible items. To do this the players have to assign all their rankings before the allocation procedure is started. The algorithm runs in polynomial time if you only want a single maximal assignment. If you want to see all possible maximal assignments then it is exponential. 

As long as the players assign true rankings to the items then the more complex algorithm will find the maximal EF assignment. It is interesting to note that as the number of items increases, the probability of a complete EF assignment approaches one. 

The bad news is that you can cheat.

If you lie about your ranking you can end up with an assignment that, when you true ranking is revealed, provokes envy. However, as the authors note the danger is that you won't work things out perfectly, because it depends on the ranking of the other player and you could end up worse off. The best strategy is to play fair and end up with an envy free allocation. 

"In many disputes, including divorce and estate division, only an allocation in which the disputants receive about the same number of items will be perceived as fair. BT and AL work well for that
purpose, especially when they allocate most, if not all, the items. While BT is a paragon of simplicity, AL is not much harder to apply, as we show, which should facilitate its acceptance as a practicable procedure."

So the next time you file for divorce, remember to hire a programmer as well as a lawyer.