﻿ Fair Division 1

# Fair Division 1

What I've been considering is the problem where each person knows exactly how much everybody else values every bit of the cake to be divided - and they are all very intelligent and greedy and will break a promise if it suits them. The usual scenario for game theory problems in fact where they lose out badly in the prisoners' dilemma.

This is quite different from the usual cake fair division problem. In the normal problem with two people dividing a cake equally using cut and choose the one choosing has the advantage, but in the full information case the cutter has a large advantage.

What I have devised is schemes whereby in the two and three person cases the cake can be divided among the people so they each get the maximum possible common fraction of the value they put on the cake. I'm not absolutely certain yet the three person case is proof against cheating but I'm fairly confident. The only real restriction is that all the cake must be worth something to everyone.

For the two player case the solution is quite straightforward

• Both bid up the fraction till the difference is too small and one wins.

• This fraction V offered will be a tiny bit smaller than the real amount - this is the cut the winner of the bidding gets and why they bid up.

• The winner then puts onto every part of the cake what he thinks the valuation is for the one choosing - except he puts a slightly lower valuation on the bits he wants to be chosen and higher on the bits he wants for himself. The total valuation has to add up to 1. The chooser then chooses up to V and will naturally choose the bits that are good value - i.e. which have the slightly lower valuation marked.

The algorithm can be extended quite easily to deal with where one person is entitled to getting for example twice as much by his valuation as the other person did by theirs.

The three person case is considerably more complicated but I can summarize it as:

• They all bit to V say A wins.

• A offers B V of the total as above and B chooses.

• C then states a fraction W which is how much C value will eventually be in B's share compared to A's share.

• A offers to C WV/((1-W)+WV) of what he has left and C chooses

• C gives this amount to B

• B then offers V of this combined amount back to C and C chooses

• Now if C has chosen W properly he will be able to demand A also offers V of the amount he has left.

If the C valuation B puts on the part C added to his lot is less than V then the amount added was too small. A can offer a smaller amount than V to C dependent on the difference.

If the C valuation B puts on the part C added is higher than V then the amount added was too much. A can offer less than V dependent on the difference.

• When the fraction W is set by C then A can set the valuation either slightly high or slightly low on the bits that he wants C to choose depending on if W is a tiny fraction lower or higher than the ideal value. You have to have a small fraction as in the bidding f the original V which A can adjust W by if it is exactly on the mark. It is those tiny fractions that drive the whole business.

The worry about cheating is whether anyone can skew the offers much at any stage for example whether B could offer less to C on the basis that it would be in C's interests not to show there is a problem with the fraction W. I've gone through the various stages and I can't see any possibility but I have had a number of schemes I investigated before which did prove susceptible.