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.