The 2 Cake Cutting Problem

September 17th, 2009 by Charles Ma Leave a reply »

Here’s a fun little brain teaser. There are two cakes of the same size, a chocolate cake and a strawberry cake. Ted and Kim are planning to share each of the cakes, but being the perfectly rational greedy agents they are in an imaginary universe contrived in the twisted mind of a puzzle maker, they both want to divide the cakes in a creative way, and they each want as much cake for themselves as possible, no compromises.

choccake

Ted proposes a plan. He says,

“I’m going to cut the first cake into two pieces, and after you see the cut, you get to decide which one of us gets the larger slice. Then I’ll cut the second cake, the person who got the smaller slice of the first cake gets to have the larger slice of the second cake”

Is this a good deal for Kim? If so, what should she do to maximize the amount of cake she gets? If not, what can Ted do to maximize the amount of cake he gets?

NOTE: Yes, this is what I can remember of an exam problem, if you did this subject with me and know the answer, please let some other people have a go before answering.

I’ll post the answer in a few days :)

UPDATE: The solution is in the comments!


No related posts.

Related posts brought to you by Yet Another Related Posts Plugin.

Advertisement

3 comments

  1. Not a good deal for Kim.

    Assume first cut is 90%/10%
    If Kim accepts 90% then Ted should cut an extremely large portion of the second cake (say 99%|1%)
    This means Ted = 109% while Kim = 91%
    If Kim declines the first cake then Ted should cut the second slice as equal as possible (say 51%|49%)
    This means Ted = 141% while Kim = 59%

    Kim should thus allways accept the first slice.

  2. If Ted wants the most cake he should offer a reasonable cut for the first slice (say 75%|25%) – it is important that Kim accepts this so he can make the second slice 99%|1%

    • cma says:

      Yep, you’re absolutely right! In fact, if Kim decides to play this game, Ted will cut it at exactly 25%|75%. Here is why.

      Suppose Kim picks the larger slice of the first cake, then Ted would make the smaller slice for the second cake infinitesimally small.
      So he would effectively get 1/n + 1 cakes where n > 1

      If Kim decides to let Ted have the larger slice of the first cake then he would cut the second cake almost in half. So he would effectively get 1 – 1/n + 1/2 cakes.

      Depending on what n is, Kim could always try and maximize the amount of cake she gets by choosing the option with min(1/n+1, 1 – 1/n + 1/2) for Ted.

      Thus, to maximize the amount of cake Ted gets. Ted would have to find n such that 1/n + 1 = 1 – 1/n + 1/2

      Solve for n and we find that n = 4. So Ted ends up getting 1.25 cakes regardless of what Kim gets. If n > 4, Kim will pick the larger slice of the first cake and Ted would get < 1.25 cakes. If n < 4, Kim would let Ted have the larger slice of the first cake and again, Ted would have < 1.25 of a cake. So n = 4 is the equilibrium. :)