How to Divide Indivisible Goods Fairly: Algorithm for Dividing Assets

We know how to allocate items fairly if the goods can be divided into equal portions: share and share alike. Divide the pie into equal-sized slices, with one slice per guest. Liquidate the assets of an estate and share the proceeds equally with each inheritor. Live in a time-share vacation property for the same number of weeks per year.

Indivisible goods, however, are indivisible. Examples include: real estate when joint ownership is excluded, for one example. Is there a way to ensure an “optimal envy-free allocation” between two parties?

Steven J. Brams, D. Marc Kilgour, and Christian Klamler recently wrote Two-Person Fair Division of Indivisible Items: An Efficient, Envy-Free Algorithm that provides two solutions.

Here we explain their stronger method, the “AL algorithm,” with some comments from one of the authors.

How to Divide an Inheritance Fairly

Suppose that Alice and Bob’s parents die. The will allows the two adult children to divide the inheritance between themselves in any way they see fit. There are a number of items, such as houses and cottages, cars and boats, and one piece of antique furniture. Both Alice and Bob would prefer to keep most items “in the family” rather than liquidate these assets; but they refuse to consider joint ownership. They agree to work with a mediator, and that a fair allocation would satisfy certain conditions:

• Alice and Bob will each receive the same number of items.
• Some items might not be assigned to either Alice or Bob; these “contested” items need further consideration outside of this algorithm.
• Alice and Bob will each submit their own prioritized list of the items to the mediator.
• After the allocation, the mediator will make a list for Alice, and a list for Bob, of the pairs of items allocated to each of them. Alice’s list will show she preferred her n-th item over Bob’s n-th item; likewise Bob’s list will show his pair-wise preference for his items. (This is the “envy-free” promise: to prefer one’s n-th item over the other party’s n-th item).

The paper by Brams, Kilgour and Klamler gives a mathematical proof that their algorithm will create this kind of fair allocation. The proof is too long for this article; instead, let’s focus on how the algorithm works.

How to Prepare for the Allocation Algorithm

An algorithm is a set of rules, which may be followed by a computer or by a person such as the mediator in this example.

Alice and Bob must each prepare their list of items in order of their preferences. For example, Alice might list the New York townhouse, then the vacation property in Bermuda, the yacht, the detached home in San Francisco, the Arizona ranch, the BMW, the antique dresser, and finally the pick-up truck. Bob may prefer the detached home, the ranch, the townhouse, the vacation property, the pick-up truck, the BMW, the yacht and finally the dresser. These preferences may reflect their different lifestyles, sentimental attachments, or simply the cash value of each item.

For simplicity, let’s say that Alice has an ordered list {1, 2, 3, 4, 5, 6, 7, 8}. The mediator notes that #1 corresponds to the New York townhouse, and so on. Bob’s list for this first example is {3, 4, 7, 1, 2, 6, 8, 5}.

Allocation Preferences Example 1: How will the algorithm allocate these resources? Image by Mike DeHaan

The paper calls this the AL algorithm. It begins by setting the Stage# and the # of Pairs Allotted to zero. It also begins with an empty list of items allocated to Alice, to Bob, as well as an empty list of Contested items. Then the algorithm receives the two lists of preferences. Then the algorithm follows these rules:The AL Allocation Algorithm

1. What is Alice’s preferred unallocated item? If nothing remains, stop.
2. Is Bob’s preferred unallocated item different from Alice’s? If they are the same, go to step 3. If they are different, then:
   • Allocate Alice’s item to Alice, and remove it from Bob’s list.
   • Allocate Bob’s item to Bob, and remove it from Alice’s list.
   • Add one to the # of Pairs Allotted.
   • Return to step 1.
3. Alice and Bob want the same “tied item”. If the # of Pairs Allotted equals zero, then go to step 5. If there are no further items on Alice’s list (or Bob’s list), then go to step 5. Otherwise:
   • List Alice’s unallocated items that she ranked below the tied item, in order of her preference. This is list AU (“Alice’s Unallocated” list).
   • List Bob’s unallocated items that he ranked below the tied item, in order of his preference. This is list BU.
   • Consider allocating the tied item to Alice, and then go through the BU list for Bob. For each item in the BU list:
     • If Bob gets this compensation item, count the number of items that Alice has received plus those that remain unallocated, that Bob would have preferred to this compensation item. If this number is greater than the # of Pairs Allotted, then the current compensation item is not feasible; otherwise we can allocate this compensation item in step 4.
   • Consider allocating the tied item to Bob, and then go through the AU list for Alice. For each item in the AU list:
     • If Alice gets this compensation item, count the number of items that Bob has received plus those that remain unallocated, that Alice would have preferred to this compensation item. If this number is greater than the # of Pairs Allotted, then the current compensation item is not feasible; otherwise we can allocate this compensation item in step 4.
   • If no compensation item allocation was feasible, go to step 5.
4. Much like the successful step 2: Remove the tied item from Alice’s list and from Bob’s list, and place it onto the Contested List. Return to step 1.
   • Allocate Alice’s item to Alice, and remove it from Bob’s list.
   • Allocate Bob’s item to Bob, and remove it from Alice’s list.
   • Add one to the # of Pairs Allotted.
   • Return to step 1.
5. Remove the tied item from Alice’s list and from Bob’s list, and place it onto the Contested List. Return to step 1.

The article presents a mathematical proof that this algorithm will provide one of the best envy-free allocations for any list that Alice and Bob can present. There may be several equally good allocations; or everything might go to the Contested List. However, this algorithm will provide one of the best possible allocations.

Click to Read Page Two: Allotting the Estate

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