Monday, June 29, 2009

Fair Division of an estate

This page describes a fair division of an estate between 5 people. The process is described in the "method of Sealed Bids" section. It that requires each participant has money they can use to pay off the others. I think this is a fairly serious drawback as not everyone has loads of money. Also in the case of an estate division it seems slightly galling that the person with more money gets more things, possibly of only sentimental value, then others.

The division works by
"# Step 1. Bidding. Each player produces a sealed bid in which he or she attaches a dollar value to each item in S. A player's fair share is 1/N of his total assessment.

# Step 2. Allocation. Each item in S goes to the highest bidder for that item. If her/his assessed value of the items received exceeds her/his fair share, she/he must pay the difference. If the assessed value of the items received falls short of a fair share, then she/he is paid out of money that others have had to pay.

# Step 3. Dividing the Surplus There is almost always a surplus of cash that is divided equally among the players. "
given results in people getting

Al BMW, Saab, Miro
Ben House
Cal Cottage
Don Klee
Ed Yacht

And the minimum receive is $62,500 + $52,100+$18,340=132 940 out of a possible $679,000 or 19% of their desire.

If instead of assuming each player has money to buy stuff off the others I assumed each layer had equal claim to happiness. So I give each persons 100% desire is worth $679000 and those who claimed less then that use the remainder of their allocation as cash.

So this gives a table of desire of this

data;
param m := 5;
param n := 1;
param o := 7;

/* n divisible items, o non divisible items*/

/*Divorce between Donald and Ivana Trump described in Win-Win solution.
Items to be divided are
4 divisible items:cash
2 non divisible items: House cottage, bmw,saab,yacht,miro, klee
Item Al Ben Cal Don Ed
House 29.46 31.66 28.71 25.77 30.19
Cottage 8.84 7.22 9.2 8.76 8.1
BMW 4.27 3.6 3.68 4.06 4.06
Saab 3.68 2.8 3.33 3.6 2.87
Yacht 17.67 18.4 17.53 19 19.51
Miro 13.99 13.13 7.36 11.05 9.57
Klee 22.09 19.88 14.58 26.36 21.94
cash 0 3.31 15.61 1.4 3.76
*/

param d : 1 2 3 4 5 6 7 :=
1 29.46 8.84 4.27 3.68 17.67 13.99 22.09
2 31.66 7.22 3.6 2.8 18.4 13.13 19.88
3 28.71 9.2 3.68 3.33 17.53 7.36 14.58
4 25.77 8.76 4.06 3.6 19 11.05 26.36
5 30.19 8.1 4.06 2.87 19.51 9.57 21.94;

param c : 1 :=
1 0
2 3.31
3 15.61
4 1.4
5 3.76;

end;


Running this on the linear programming fair division calculator program(you need to add s.t. wor5{i in I}: ((sum{j in J} c[5,j] * x[5,j])+(sum{k in K} d[5,k] * y[5,k])) >= worst;). gives a the person who gets least 20.5388%

Al BMW Saab Miro
Ben House
Cal 0.726381 of the cash Cottage
Don Klee
Ed Yacht 0.273619 of the cash

which is an slight improvement of over on the initial allocation. Everyone gets the same items as in the initial allocation but the money is divided amongst those who receive the least rather then everyone.

Sunday, June 28, 2009

Fair Division in Treaty Negotiations

Raiffa in "the art and science of negotiation" describes the Panama Canal treaty negotiations in 1974. He got the value each country attached to each issue from the US negotiating team. In the fair division book chapter 5 describes this negotiation using their Adjusted winner algorithm. One weakness with this algorithm is that all items must be divisible.
There is no way to fix issues as non divisible as there is in my program (you will need to remove s.t. wor3 and s.t. wor4).
So if you take the data as

data;
param m := 2;
param n := 9;
param o := 1;

/*m people, n divisible items, o non divisible items*/
/*
1 non divisible items expansion routes
US Panama
US defense rights 22 9
use rights 22 15
Land and water 15 15
expansion rights 14 3
duration 11 15
expansion routes 6 5
compensation 4 11
jurisdiction 2 7
US military rights 2 7
defense role of Panama 2 13
*/

param c : 1 2 3 4 5 6 7 8 9 :=
1 22 22 15 14 11 4 2 2 2
2 9 15 15 3 15 11 7 7 13;

param d : 1 :=
1 6
2 5;
end;

where expansion routes is not divisible.

US gets item number us defense rights, use rights, expansion rights,expansion routes
Panama gets duration, expansion routes, compensation, jurisdiction and us military rights. For Land and water the US gets .1333 of this and Panama get 0.86667 which is ok as land and water are the sorts of things that can be divided up. Each country got 66% of what they wanted, In this case my program gets the same results as the Adjusted winner program.

Thursday, June 25, 2009

A better fair division program

One problem with the wildly unpopular fair division programs discussed previously is that they assume either everything can be cut into pieces or nothing can.
In the real world as Solomon noticed some items cannot be divided up. But some items are easily splittable . So I have improved the fair division program to deal with combined divisible and indivisible items.

Another problem is that the code only dealt with the two person case. I have fixed this by adding a new constraint for each extra person.

The code for this Mathprog program fair.mod is here. I am providing the source code in case anyone can suggest improvements. Also the world is full of decisions that get made for us that we have no way to challenge or understand. So I would like people to be able to see why the reasoning in and results of an arbitration,

The program (glpk) is run by

Put this data in a data file. Call glpk on it.
./glpsol -m fair.mod -d data -o fair.sol
So the data file could be

data;
param m := 4;
param n := 4;
param o := 2;
/*m people, n divisible items, o non divisible items*/

/*
Items to be divided are
4 divisible items: cash, land, cake, gold
2 non divisible items: dog, table
*/

param c : 1 2 3 4 :=
1 20 30 0 20
2 30 20 0 20
3 20 30 0 20
4 0 10 40 40;

param d : 1 2 :=
1 10 20
2 20 10
3 20 10
4 10 0;
end;

Which means person 1 thinks 20% of the value to them in the estate is in the cash, 10% is in the dog etc.

So now you can divide up goods fairly between m people. I have never seen a program that does this before. Using this program the that parties in a will, divorce, international dispute, merger and all sorts of other areas can achieve optimal solutions. The solutions will be proportional, envy-free (in the two person case) and Pareto optimal.

Now to make the dispute resolution program more usable.