## Cake Cutting Algorithms – 3 : Moving Knife Algorithm

Hello all,

Last time we have looked at “Successive Pair Algorithm” for simple fair division of a cake. Let us look at a different algorithm now. Why would we require a different algorithm? Let us see.

In the successive pair algorithm, every time $n^{th}$ arrives we would require all pieces to be cut into $n$ equal pieces. Let total number of pieces required to divide a cake amongst $n$ candidates be denoted by $T(n)$ ( it is a standard notation for time complexity calculation ). Therefore, total number of pieces would be :

$T(n) = n * T(n-1) = n* (n-1) * T(n-2) = n!$

Essentially, it indicates that if 10 candidates are contending for the cake, there will be 3,628,800 pieces at the end. Don’t you think it is a bit too much ? At the end, each candidate will have a fair share of cake powder :-). Certainly, we want a more elegant solution.

Let us see how following strategy works out for old friends Pinku, Rinku and Chinku :

Let the knife be at the leftmost end of the cake. Slowly but gradually shift the knife towards right. Whenever someone says “stop”, we will make a cut there and give the piece to the left of the knife to that person. For the remaining portion, we will play “Cut and Choose” as we only have two contenders left. Why does this strategy works??

Well, assume for example that Pinku is the first one to say “stop”. Let the piece to the left of the knife be denoted by $X_{k_1}$ for the first time, $X_{k_2}$ for the second time and so on. Clearly, Pinku is smart enough to say “stop” only when $f_p(X_{k_1}) \geq 1/3$. Chinku and Rinku did not bother to say “stop” implies that $f_c(X_{k_1}) , f_r(X_{k_1}) < 1/3$. Both Chinku and Rinku believes that the remaining piece is at least $2/3$. Chinku and Rinku will play “Cut and Choose” or rather “I cut you choose” to get their fair share.

This strategy can be extended for $n$ contenders. Whether it works or not, can easily be shown by mathematical induction.

Base case : For n=1 it is fairly trivial.

Hypothesis : Assume this stretagy works for $n-1$ contenders.

Induction Step : As we argued earlier, the first person to say “stop” believes that the cake is worth at least $1/n$ and others believe that the rest of the cake is worth at least $1-(1/n) = (n-1)/n$. The first person is given his/her share to his/her satisfaction. For the remaining $n-1$ persons, the rest of the cake is fairly divided $(1/(n-1)) * ((n-1)/n) = 1/n$.

This algorithm is called “Moving Knife Algorithm”. It generates exactly $n$ pieces with $n-1$ cuts. Still, I would say this algorithm is not good enough. It is obvious that one would require minimum of $n-1$ cuts to divide a cake into $n$ pieces, so where is the problem? If you look at this algorithm carefully, you would find out that this algorithm requires all contenders to make decision at each and every point while the knife is on move. If we denote the leftmost point of the cake as 0 and the rightmost point as 1, we will have infinitely many possible values in between. In short, this algorithm is an infinite step algorithm. Even though, this algorithm can work quite well in practice, it does not work well in theory. ( This is a strange example where something works in practice but not in theory :-). In practice, a person has a limitation in measuring, or in simpler words, we would not be able to tell a difference whether the knife is 3.7889213 cm away or 3.7889214 cm away ).

So, even though this is probably the most optimal solution practically, we need better finite step algorithms. We shall see later some of those.

–Saurabh Joshi