How to Divide Indivisible Goods Fairly: Algorithm for Dividing Assets

Allotting the Estate in the First Example

Let’s allot the estate in the first example.

The first two pairs are allotted easily, since there is no conflict among these selections for Alice and for Bob.

In stage 3, Alice gets the yacht, her third choice, while Bob’s third and fourth choices were already taken by Alice. However, the pick-up truck is now at the top of his list as his fifth preference. The algorithm does not see a conflict, since Bob only prefers two of Alice’s items (and no unallocated items) to this truck. So this pairing counts as allotment 3.

To begin stage 4, Alice does not get her fourth preference, the San Francisco house, because Bob had already taken it in stage 1. Likewise, the ranch went to Bob in stage 2.

Now Alice and Bob are both down to their sixth preference, the BMW. The algorithm provisionally tries to allocate it to Alice, but then Bob would get the antique dresser. That’s his least preferred item; Bob would prefer all four items assigned to Alice (including the BMW in this stage). But so far, the # of Pairs Allotted is only 3. Therefore the algorithm decides this is not a feasible allocation.

Now the algorithm tries to allocate the BMW to Bob. Alice would receive the antique dresser as compensation. Since Alice prefers the dresser over the pick-up truck that Bob had already received, she only prefers 3 of Bob’s items. That’s the same number as the # of Pairs Allotted up to this point, so this is indeed a feasible allocation.

The Second Example of Allocation Leaves Items Contested

Suppose Bob had different priorities. In the second example, he and Alice have opposite preferences at the top and bottom of their lists, but the middle portion is identical.

Allocating the Estate in the Second Example

It’s easy to assign the first pair in the second example.

In stage 2, is it feasible to give Alice the yacht, and Bob the house in San Francisco? Bob would prefer two of Alice’s items, the yacht and the NY townhouse, over the SF house. Since we’ve only allotted one pair so far, the algorithm refuses to do this allocation.

Likewise, if Alice gets the SF house, she would prefer both the yacht and the Bermuda property which went to Bob.

Therefore the algorithm puts both the SF house and the yacht into the Contested List.

The same holds for the ranch and BMW. These cannot be allocated in an envy-free manner, so the algorithm adds them to the Contested List.

Finally, since Alice and Bob have different preferences for the antique dresser and the pick-up truck, the algorithm assigns them accordingly.

The Problem of Allocating the Contested List

Unfortunately the algorithm does not deal further with the Contested List. In this author’s view, a mediator might suggest several approaches:

1. Alice and Bob could prioritize the Contested List again, and use the algorithm. However, if their priorities are consistent with their first lists, then all the items will be contested again.
2. Alice and Bob could negotiate, perhaps swapping two low-value items for one that is more prized.
3. The mediator might liquidate the assets and divide the money evenly.

However, options 2 and 3 go beyond the mathematical algorithm’s proven fairness.

Interview with Dr. Marc Kilgour about the AL Algorithm

Decoded Science interviewed Dr. Marc Kilgour by e-mail about this algorithm, and asked, “… do you expect that the AL algorithm could be extended to ‘n‘ players (parties) with ‘m‘ contested items to be allocated? My guess is that the principle would be feasible; would it be difficult to prove the extension.”

Dr. Marc Kilgour: “I don’t know, but I doubt it. The ‘m‘ part is not a problem. But the ‘n‘ is. Allocation of indivisible items is a harder problem than allocation of divisible items. For divisible items, it becomes impossible to meet several criteria of fairness simultaneously as ‘n‘ increases. I think that will happen for indivisible items too, but I don’t think anybody knows.”

DS: “… removed from the math: do you have any indication that some people, who enjoy negotiating, would prefer to dissemble or lie rather than commit honestly to a list of preferences?”

Dr. MK: “Yes, people often prefer to game situations, or gamble. We cannot prove that you always do better telling the truth, but we can prove that if you don’t you may do worse. Nonetheless, some people will no doubt try to beat the system.”

Benefits and Limitations of the AL Algorithm to Divide Indivisible Goods

The paper offers a mathematical proof that the AL algorithm is “fair” and “envy-free” according to certain specifications. It is also simple enough for a mediator to follow manually; or it could be implemented as a computer program. The math shows that no other allocation would be better for one party without being worse for the other.

Unfortunately, the AL algorithm cannot guarantee that all items would be allocated; and it does not describe how to resolve the contested items. Finally, at this time, the algorithm has only been proven to be fair for two parties rather than a larger number of people.

Regardless of its current limitations, the AL algorithm does succeed in its mission: to divide indivisible goods “fairly and without envy.”

© Copyright 2014 Mike DeHaan, All rights Reserved. Written For: Decoded Science