perplexus.info :: Logic : Game Theory on dividing cakes

Game Theory on dividing cakes (Posted on 2004-12-27)

A well-known method of dividing a cake between two people is to have the first person to cut the cake and have the second person to have the first pick. This will guarantee that the first person will cut the cake in half so that the second person cannot leave him with a smaller piece.

Now we want to divide the cake among n people. Let's make the following assumptions:
(a) Each person cannot cut the cake more than once
(b) Everyone is logical
(c) Everyone wishes to get the largest possible piece
(d) Everyone wishes to narrow the gap with those who have a bigger piece than he does
(e) No one cares about anyone who has a smaller piece than themselves.

Can you generalize the strategy to n people? Give your logical steps/proof that this strategy will yield a fair result.

Submitted by Bon

Rating: 1.5000 (2 votes)

Solution: (Hide)

Let's call the first person P[1], second P[2], etc..., up to P[n].
P[1] knew that the largest size for the smallest piece after n'th cut is 1/n. Thus he should cut 1/n of the cake. If he didn't, the smallest size will possibly be less than 1/n. Now the cake is divided into two parts: 1/n and (n-1)/n. P[2] knows that if he cut the 1/n piece, he will get a piece less than size 1/n, as there are two pieces that are smaller than 1/n now. Thus follow the similar logic of P[1], he will cut 1/n off the (n-1)/n piece. Similarly, P[3] will not cut the 1/n pieces, or else this will make his largest possible piece will be at most 1/n while at least one other person will have a piece larger than 1/n. The same logic goes for P[4], ..., P[n-1]. Thus the cake will be cut in n pieces, each of size 1/n.

Comments: ( You must be logged in to post comments.)

Subject	Author	Date
possible sol	Andrei	2005-01-08 17:24:53
Fair cuts...	Erik O.	2004-12-28 18:04:53
re: One fair cut deserves another	Steve Herman	2004-12-28 14:37:15
One fair cut deserves another	Steve Herman	2004-12-28 14:23:45
It's Monday.....	Penny	2004-12-27 23:20:32
re: Question	Penny	2004-12-27 18:03:59
Clarifications	Eric	2004-12-27 16:56:50
Question	Penny	2004-12-27 16:10:35

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info