Tuesday, May 19, 2009

Fair Division

"The only way to rectify our reasonings is to make them as tangible as those of the Mathematicians, so that we can find our error at a glance, and when there are disputes among persons, we can simply say: Let us calculate [calculemus], without further ado, to see who is right" Leibniz

If you want to divide items between two people you want to make sure that the person who gets least gets as much as possible.

This Maximin algorithm where you maximise what the person who gets least gets. To do this each person should put a valuation on each item. You can then use linear programming to divide items fairly between people. This program is written for the GLPK(there is a tutorial on it here)

This program is a modified version of this one

param m, integer,:= 2;
/* number of people dividing stuff */

param n, integer, > 0;
/* number of items to be divided */

set I := 1..m;
/* set of people */

set J := 1..n;
/* set of items */

param b{i in I},:= 100;
/* resource capacity of person i.
How much each person can want */

param c{i in I, j in J}, >= 0;
/* amount received if item j
is given to agent i */

var worst;
/*how is the worst person doing?*/

var x{i in I, j in J},>=0;
here ,>=0;
means that the items can be subdivided.
here , binary;
means that items cannot be subdivided
x[i,j] = 1 means job j is assigned to agent i */

s.t. one{j in J}: sum{i in I} x[i,j] = 1;
/* item j must be assigned.
An item can be split due to >=0
being used instead of binary;*/

s.t. lim{i in I}: sum{j in J} c[i,j] * x[i,j] <= b[i];
/* total amount received by all items
to person i must not exceed the person's capacity */

s.t. wor{i in I}: sum{j in J} c[1,j] * x[1,j] >= worst;
s.t. wor2{i in I}: sum{j in J} c[2,j] * x[2,j] >= worst;
/*constraint on who gets worst deal*/
maximize obj: worst;


param n := 4;

/*Divorce between Donald and Ivana Trump
described in Win-Win solution.
Items to be divided are Conneticut estate, Palm beach mansion,
Trump plaza apartment, Trump Tower Triplex
param n := 4;
param c : 1 2 3 4 :=
1 10 40 10 40
2 40 20 30 10 ;

This last data part param c is important. The first line the columns are the items to be divided. The rows are the valuations placed on them. So c[i,j] is the value person i places on item j.
With splitting items allowed this results in

No. Column name St Activity
------ ------------ -- -------------
1 worst B 73.3333
2 x[1,1] NL 0
3 x[2,1] B 1
4 x[1,2] B 0.833333
5 x[2,2] B 0.166667
6 x[1,3] NL 0
7 x[2,3] B 1
8 x[1,4] B 1
9 x[2,4] NL 0

With splitting items not allowed the answer comes out as

No. Column name Activity
------ ------------ -------------
1 worst 70
2 x[1,1] * 0
3 x[2,1] * 1
4 x[1,2] * 1
5 x[2,2] * 0
6 x[1,3] * 0
7 x[2,3] * 1
8 x[1,4] * 1

This algorithm can be used to divide up items in a divorce, resources between countries and loads of other areas.
I will try make this easier for people to use. Any suggestions/comments are welcome.

No comments: