Cake Cutting Algorithms – 2

Well,

In the last post we have seen how can we have a fair share division of a cake for two contenders. However, life is not as simple as we believe it to be.

Let’s introduce a new character to our drama. Chinku joins in the party so he also need a fair share of the cake. What do we do now? Let us try examining possible solutions one by one.

Method 1:

Let’s assume that Pinku and Rinku already have their fair share. When Chinku joins in, the cake has to be divided in a way so as to make everyone believe that they got 1/3rd of the cake. We can let Chinku take 1/3rd piece from Pinku as well as Rinku’s share.

This method will fail for obvious reason because Chinku’s evaluation of a piece may differ from that of Pinku and Rinku’s.

Method 2:

Actually, we can again play Cut and Choose with a bit of modification. Let Pinku and Rinku divide their respective pieces into 3 equal pieces (X_{11}=X_{12}=X_{13} \geq \frac{1}{6} from Pinku’s perspective, similarly X_{21}=X_{22}=X{32} \geq \frac{1}{6} from Rinku’s perspective). and Let Chinku choose one piece from X_{1i} and one piece from X_{2j}.

It is clear that with such a strategy Pinku as well as Rinku will be satisfied. Because f_p(\sum _{k \neq i} X_{1k}) \geq \frac{1}{3} and same can be argued for f_r(). Now, we need to see whether Chinku will get a fair share or not. Because, Chinku is the chooser, he will choose a piece X_{1i} | f_c(X_{1i}) \geq f_c(X_1)/3 and X_{2j} | f_c(X_{2j}) \geq f_c(X_2)/3. Chinku will get a fair share because

f_c(X_{1i} + X_{2j}) = f_c(X_{1i}) + f_c(X_{2j}) \geq \frac{f_c(X_1) + f_c(X_2)}{3} = \frac{f_c(X_1 + X_2)}{3 } = \frac{f_c(X)}{3} = \frac{1}{3}

Okay, so far so good. What will we do if Dinku joins the party??? We can go on and on about adding more and more contenders. So let us generalize this algorithm.

  1. Assume cake is divided fairly amongst n-1 persons. Obviously, for n=1 he/she has the whole cake.
  2. When n^{th} person joins, let everyone but n divide his/her share into n equal pieces from their perspective.
  3. Let n choose one piece from each person P_i‘s share.
  4. P_i | 1 \leq i \leq (n-1) is happy because he/she originally had share \geq 1/(n-1) and after the new person takes one piece he/she has
  5. \geq 1/(n-1) * (1/n+1/n +\dots (n-1)\, times ) = 1/(n-1) * (n-1)/n = 1/n
  6. Person P_n is happy because he has X_{1i_1} + X_{2i_2} +\dots + X_{(n-1)i_{n-1}} \geq (\sum _{j=1} ^{j=n-1} X_j) / n = 1/n

The above mentioned algorithm is called “Successive pair algorithm”. In the next post, we will look at more algorithms for fair share division where more than two contenders are involved.

Advertisements

Tags:

One Response to “Cake Cutting Algorithms – 2”

  1. Cake Cutting Algorithms - 3 : Moving Knife Algorithm « Me, Myself and Mathematics Says:

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

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: