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

Advertisements

Tags: , , ,

2 Responses to “Cake Cutting Algorithms – 3 : Moving Knife Algorithm”

  1. Cake Cutting Algorithm -4 : Trimming Algorithm « Me, Myself and Mathematics Says:

    […] Me, Myself and Mathematics Saurabh Joshi’s Blog about math, algorithms, theorems, puzzles …. « Cake Cutting Algorithms – 3 : Moving Knife Algorithm […]

  2. Cake Cutting Algorithms - 7 : Divide and Conquer « Me, Myself and Mathematics Says:

    […] that the simple fair division can not be achieved in with a deterministic discrete ( unlike moving-knife algorithm ) algorithm.  Many believe that the lower bound for simple fair division, where queries to […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: