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.
This code is very interesting to me. I manage a corporate IT department and am very interested in fairness as a guiding principle in management. I recently changed our departmental structure to be one of 11 separate functional groups. I set a number of slots that each group would have open, and allowed all department members to rank the groups by their preference. I am now looking for the most fair way to determine group membership. The items in my fair division problem are divisible, but divisible into a set number of subparts. This would be similar to dividing up sets of similar items, such as in a will or divorce I suppose. Does the code allow for constraints on each item to be set indicating the number of subparts that an item can be divided into, or does it consider items to be infinitely divisible?
ReplyDelete"Does the code allow for constraints on each item to be set indicating the number of subparts that an item can be divided into, or does it consider items to be infinitely divisible?"
ReplyDeleteAt the moment you would have to hack the data for this. So say you wanted an item to be only quatered. You could enter it as four indivisible items. So "Car wheels" becomes wheel 1,wheel 2, wheel 3 and wheel 4.
Your problem sounds interesting. If you email me some more details at stuffsplitter [at] gmail.com i will try help you with it.
You also have the problem that a particular group may not suit a person. So Alice may like the programming group most but does the programming group want her?
Hi Ian
ReplyDeleteActually your problem is a variation on the hospitals/residents problem
http://en.wikipedia.org/wiki/Stable_marriage_problem#Applications
And an interesting one at that. Calculating the answer to your problem is doable.