Exact division

An exact or even division is a type of fair division where all the players believe everyone received the same amount.

There is no finite procedure for exact division but there are moving knife procedures for two players. For more than two players only near exact procedures are known, this is sufficient though to enable envy-free fair division procedures to be devised for any number of players.

Two players

The original procedure for exact division of a cake devised by A.K.Austin is as follows: [Jack Robertson and William Webb (1998). "Cake-Cutting Algorithms: Be Fair If You Can", AK Peters Ltd, . ISBN 1-56881-076-8.]

*The first player places one knife on the left of the cake and a second parallel to it on the right where he judges it splits the cake in two.
*The first player moves both knives to the right so half the cake is always between the two knives.
*The second player says stop when they think half the cake is between the knives.

If the first player reaches the end he must have his left knife positioned where the right knife started. The intermediate value theorem establishes the second player must be satisfied the cake is halved at some point. Giving the pieces at random to the players can be used to ensure they don't favour either part.

One knife can be used to achieve the same effect. The first player rotates the knife over the cake through 180° keeping a half on either side and the second player says when they agree. The first player must of course end the turn with the knife on the same line as where it started.

Exact division with any rational ratio of entitlements can also be achieved for two players by a slightly more complicated procedure.

Near exact division

For more than two players there is no known procedure for exact division, but near exact divisions are possible. This means for any given $epsilon\; >\; 0$ one can ensure the players each believe the values everyone has differ by less than $epsilon$.

This is achieved by the players all splitting up the cake into tiny bits and assigning a value to each bit. This means each bit has a vector of values, one per player. The bits are then selected so the players get allocations in near exact proportion to their entitlements. This can always be done due to a theorem by V.Bergström.

References