Monday, July 06, 2009

Filling knapsacks with candies

This paper by Marco Dall’Aglio and Raffaele Mosca on using linear programming (and dynamic programming)
it gives two examples of dividing non divisible goods between two people. The paper uses hard candies as a metaphor for any indivisible item.

The valuations are not based out of 100% but just plain numerical values.

candy 1 2 3 4 5 6 7 8
Alice 12 18 50 40 20 20 10 5
Bob 5 10 35 30 15 22 30 28

Which as data for glpk looks like this

data;
param m := 2;
param n := 0;
param o := 8;

param d : :=
1
2
;
param c : 1 2 3 4 5 6 7 8 :=
1 12 18 50 40 20 20 10 5
2 5 10 35 30 15 22 30 28
;end;

the worst person got 102 of what they wanted

Person alice gets item number 1 3 and 4
Person bob gets item number 2 5 6 7 8
This is the same allocation as the paper come up with.

The next example given is

candy 1 2 3 4
Alice 32 28 22 18
Bob 25 25 25 25

which is the data file

data;
param m := 2;
param n := 0;
param o := 4;

param d : :=
1
2
;

param c : 1 2 3 4 :=
1 32 28 22 18
2 25 25 25 25
;end;

Alice gets item 1 and 2
Bob gets item 3,4
The worst performing person gets 50.

To use these data files with the fair divider for two people (the code of which is here)
./glpsol -m fair2.mod -d data -o fair.sol

As pointed out in the comments this isn't earth shaking or anything it just shows another use of fair division which can be used when items cannot be divided.

3 comments:

artied said...

Hellllooh!

What was the point in that summary of someone else's work esp after you had given the link.

There is neither elaboration, context or comment in your post. Wassup? You're stuff is usually much better than this.....

Iamreddave said...

Fair point artied. I am just collecting up examples of where fair division problems have been given and solving them. Not earth shattering but if someone googles the paper they might turn up some source code that can help them.

I'll try keep the points more innovative.

Dave Masterson said...

That taught you! Back to the lab....