CS 70 Discrete Mathematics for CS
Spring 2008 Note 8
Cake Cutting and Fair Division Algorithms
The cake-cutting problem is as follows. We have a cake, to be shared among n of us, and we want to split it amongst themselves fairly. However, each person might value different portions of the cake differently. (I like flowers; you hate them. I hate icing; you prefer it.) What’s worse, everyone is greedy and will try to end up with as much cake if they can do so without noticeably deviating from the rules of the game. Nonetheless, we want some way to split the cake that everyone will agree is fair. What can we do?
First, let’s try to make the problem statement more precise. We assume that each person has their own measure of the value of parts of the cake. If X is one of the participants, and S represents a portion of the cake, let mX (S) denote the value that X associates to S. We will assume that 0 ≤ mX (S) ≤ 1, that measures are scaled so that every person values the whole cake at exactly 1, and that measures are additive, so that mX (S ∪ T ) = mX (S) + mX (T ) if S, T are two disjoint pieces of the cake. Each participant knows their own measure, but not necessarily the measure of anyone else (we can’t read other people’s minds).
A cake-cutting protocol specifies how each of the n participants is supposed to behave. Each participant might follow the protocol, or he might deviate from the protocol if the participant thinks he can get more cake by deviating. We assume that no participant will behave in a way that detectably deviates from the protocol (for instance, no participant will just grab the whole cake and run away with it), perhaps for fear of retribution. However, if a participant can behave in a way that appears to everyone else to follow the protocol, but actually deviates from the protocol, then a participant might well do so. We classify a participant as honest if she follows the protocol, or dishonest otherwise. Of course, there is no way for any participant to know which of the other participants may be honest or dishonest.
First, we need to define what we mean by “fair.”
Definition. A cake-cutting protocol for n participants is fair for X if the following property is true: If par- ticipant X follows the protocol, then X is guaranteed to receive at least 1/n-th of the cake (by X’s measure), no matter what happens. A cake-cutting protocol is fair if it is fair for every participant.
In general, we will try to ensure that honest participants receive their just desserts; but dishonest participants are not promised anything. In other words, a fair cake-cutting protocol is supposed to ensure that each honest participant receives a piece of the cake that he thinks is worth at least 1/n, by his own measure.
Here is a simple and classic protocol for splitting a cake between n = 2 people, say Alice and Bob:
1. Alice cuts the cake into two pieces that she considers of equal worth (by her measure). 2. Bob chooses whichever piece he considers to be worth more (by his measure).
3. Alice receives the remaining piece.
This is known as the cut-and-choose protocol, because one participant cuts and the other chooses.
Theorem. The cut-and-choose protocol for n = 2 is a fair cake-cutting protocol.
Proof: If Alice follows the protocol, then both pieces are worth the same to her, so each piece must be worth exactly 1/2 by her measure. (If we call the two pieces S,T, then mA(S)+mA(T) = mA(S∪T) = 1
CS 70, Spring 2008, Note 8 1
and mA(S) = mA(T ), so mA(S) = mA(T ) = 1/2.) As a result, it doesn’t matter what Bob does; Alice is guaranteed to receive a piece that she considers to be worth exactly 1/2, as long as she follows the protocol. In other words, the protocol is fair for Alice.
The protocol is also fair for Bob. Call the two pieces S,T. We have mB(S)+mB(T) = mB(S∪T) = 1 and mB(S),mB(T) ≥ 0, so one of these two pieces must be worth at least 1/2 by Bob’s measure. Thus by choosing the larger of the two pieces, Bob ensures that his piece will be worth at least 1/2 by his measure. 2
Notice how the protocol rewards honesty: as long as Alice is honest and follows the protocol, she is guaran- teed to receive her fair share. In principle Alice could deviate from the protocol by cutting the cake into two pieces that she did not consider to be of equal worth, but then she runs the risk of receiving a piece of the cake that is worth less than 1/2. Consequently we might say that this protocol helps to “keep honest people honest,” by removing the temptation to cheat.
In contrast, asking Alice to cut the cake into two equal pieces and then choose one would create two prob- lems. First, Alice’s measure might not be the same as Bob’s measure, so even if Alice followed our instruc- tions faithfully, Bob might end up with a piece that he considers to be worth less than 1/2. Second, Alice would have every incentive to cut the cake unequally and then choose the larger of the two pieces. If Bob gets upset, she can always claim that the two pieces were equal by her measure; Bob may suspect what really happened, but Alice has plausible deniability.
So far, this has been pretty straightforward. But what about a protocol when n > 2? Take a moment to think about how you might solve the problem when there are more than two participants.
Fairness for Many Participants
Here is a first attempt at a protocol for n = 3:
1. Alice cuts the cake into three pieces that she considers of equal worth (by her measure).
2. Bob chooses whichever piece he considers to be worth most (by his measure).
3. Carol chooses whichever of the two remaining pieces she considers to be worth more (by her measure). 4. Alice receives the remaining piece.
What do you think of this protocol? Is it fair?
This protocol is certainly fair to Alice (since if she follows the protocol, she receives a piece worth 1/3 to her) and to Bob (since at least one of the three pieces must be worth at least 1/3 to him). However, it is not fair to Carol. For instance, if Alice and Bob are dishonest, they could gang up to cheat Carol: Alice could divide the cake into one very large piece and two tiny pieces. Bob would take the very large piece, and Carol would then be stuck with the tiny piece. This demonstrates that the protocol is not fair to Carol, and consequently that this is not a fair cake-cutting protocol.
In this case, Alice and Bob might have an incentive to cheat in this way. If they agree to split their winnings evenly, by cheating as described above Alice and Bob will end up with close to 1/2 of the cake, which is more than they are guaranteed if they followed the protocol. However, it is worth emphasizing that the definition of fairness does not assume that assume that all players will behave in their own interest. Even if Alice and Bob had no incentive to cheat in this way, from Carol’s point of view, the fact that they can cheat her out of her fair share is unacceptable and sufficient to condemn the protocol as not fair to Carol. The definition of fairness requires that, even if everyone else conspires to try to cheat Carol out of her fair share, Carol is still guaranteed her fair share.
CS 70, Spring 2008, Note 8 2
It’s also worth pointing out that what can happen through malice can sometimes also happen by chance. In the protocol given above, Carol might end up with less than her fair share even if Alice and Bob faithfully follow the protocol. For instance, suppose that the cake happens to be made of chocolate, vanilla, and strawberry, and Alice cuts it into an all-chocolate piece, an all-vanilla piece, and an all-strawberry piece. Imagine that Carol hates vanilla and strawberry and considers them to be worth 0 (by her measure). If Bob happens to take the chocolate piece before Carol gets a chance at it, then Carol will be stuck with a piece of the cake that is worth nothing to her. That’s not very fair to her. This kind of thing could easily happen just by bad luck.
Nonetheless, when analyzing cake-cutting protocols, it is often helpful to consider what happens if everyone else tries to gang up on you and cheat you out of your fair share. If you’re still guaranteed to get at least 1/n-th of the cake, even when everyone else is malicious and conspiring, then mere bad luck can’t hurt you.
With that preamble, here is a general protocol for fair cake-cutting for arbitrarily many participants:
1. 2. 3. 4. 5.
If n = 2, use the cut-and-choose protocol. Otherwise:
The first n − 1 participants divide the cake by recursively invoking this procedure. For i = 1,2,…,n−1, do:
Participant i divides her share into n pieces she considers of equal worth (by her measure). Participant n collects whichever of those n pieces he considers to be worth most (by his measure).
Theorem. This cake-cutting protocol is fair for every n.
Proof: The proof is by induction on n. The base case, n = 2, was already proven to be fair, so let us focus
our attention on the case where n > 2.
Let Alice be one of the first n−1 participants. Suppose Alice follows the protocol honestly. By the induction hypothesis, in step 2 Alice receives a share that she considers to be worth at least 1/(n − 1)-th of the cake. In step 4, Alice divides her share into n pieces, each of which must be worth at least 1/(n(n − 1)) to her. No matter which piece participant n collects in step 5, Alice is left with n − 1 pieces, each worth at least 1/(n(n − 1)), so Alice is left with a share that she considers to be worth at least 1/n. Therefore, the protocol is fair to each of the first n − 1 participants.
Next suppose the nth participant, call him Bob, follows the protocol honestly. Let Si denote the share that participant i receives after step 2, and let xi = mB(Si). Since step 2 divides the entire cake, we know x1 + · · · + xn−1 = 1. Also in step 5 Bob is guaranteed to collect a piece from participant i that is worth at least xi/n to him. After the protocol is finished, Bob has collected pieces that in total are worth at least x1/n+···+xn−1/n = (x1 +···+xn−1)/n = 1/n to him. Therefore, the protocol is fair to the nth participant. 2
Unfortunately, the recursive protocol shown above requires n! steps to split a cake among n participants. This is an unreasonable amount of work if we have many participants. (It also requires unreasonably precise cutting of the cake.) Is there a more efficient solution?
One answer might be to use a so-called moving-knife protocol. The idea is that someone moves a knife slowly from left to right. As soon as the area to the left of the knife covers at least 1/nth of the cake (by your measure), you are supposed to yell “Stop!” at the top of your lungs. At that point, the knife-holder cuts the cake whereever the knife was when you yelled “Stop!”, the person to yell “Stop!” receives the piece of cake to the left of the knife, and the protocol continues with the remaining n − 1 participants. It is easy to see that this is fair to everyone. It is fair to the first person to yell “Stop!”, because if he followed the protocol he receives a piece that he considers to be worth 1/n. Also, because the other n − 1 participants have not yelled “Stop!” yet, if they were following the protocol honestly, they must consider the remainder of the cake to be worth at least (n − 1)/n, and by induction, they are guaranteed to receive at least 1/(n − 1) of the remainder.
CS 70, Spring 2008, Note 8 3
The moving-knife solution is elegant and efficient. However, we might not be completely satisfied with it. For instance, if we were going to implement this in a distributed system where the participants are spread around the world, then the latency of Internet connections poses a challenge. By the time my “Stop!” message reaches the knife-holder, the knife may have moved on a significant distance and someone else closer to the knife-holder may have already claimed the piece.
This suggests a nice challenge: find an efficient, fair cake-cutting protocol for n participants, without using a moving knife. In fact, the moving-knife solution can be translated into one that does not require a moving knife, as follows. Each participant marks the first point on the cake where they would have yelled “Stop!”, if there had been a moving knife. We cut the cake at the leftmost of the marks and give that piece to whoever made that mark. Then, we continue dividing up the rest of the cake among the remaining n − 1 parties. It can be seen that this requires approximately n2/2 operations to split a cake among n parties, and it is fair for precisely the same reasons that the moving-knife protocol is. This revised protocol is now suitable for use in a distributed system. In fact, you might recognize that we have basically invented an auction. Each person “bids” by pointing to the smallest piece that they’d be willing to accept. Whoever’s bid is smallest wins the auction, and we repeat until the entire cake has been apportioned.
Envy-free Cake-Cutting
Fairness is all well and good, but some might say it does not account for human nature. For example, if n = 3, I might receive a piece that I consider to be worth 1/3, but I might notice that Alice received a piece that I consider to be worth more than 1/3 and be envious of her. This suggests looking at the notion of envy-free cake-cutting protocols.
Definition. A cake-cutting protocol is envy-free for X if it has the following property: if X follows the protocol, then X is guaranteed to receive a piece worth at least as much (by X’s measure) as anyone else’s piece is worth (by X’s measure), no matter what happens. A cake-cutting protocol is envy-free if it is envy- free for every participant.
Theorem. Every envy-free protocol is also fair.
Proof: Suppose Alice receives a piece that she considers to be worth w, and the other n − 1 participants receive pieces she considers to be worth x1,…,xn−1, respectively. We know that w+x1 +···+xn−1 = 1. If the protocol is envy-free, w ≥ xi for every i, so nw = w+w+···+w ≥ w+x1 +···+xn−1 = 1, or in other words, w ≥ 1/n. Therefore, if the protocol is envy-free, every participant receives a piece that she considers to be worth at least 1/n. 2
Theorem. The cut-and-choose protocol for n = 2 participants is envy-free.
Proof: If a person receives a piece she considers to be worth at least 1/2 by her measure, than she must consider the piece received by the other person to be worth at most 1/2, since those two valuations must sum to 1. The cut-and-choose protocol ensures that both Alice and Bob receive a piece that they consider to be worth at least 1/2. 2
Unfortunately, the recursive algorithm described earlier is not envy-free. For instance, suppose n = 3 and the three parties are Alice, Bob, and Carol. In step 2, Alice and Bob might conspire to give the whole cake to Alice. Then Carol will receive 1/3 of the cake from Alice (and nothing from Bob) in step 5, but Alice receives 2/3 of the cake, so Carol will be envious of Alice.
[ Exercise: Is the 3-party moving-knife protocol envy-free? ]
As it turns out, it is possible to build an envy-free cake-cutting protocol for n = 3 participants. For the curious, here is one:
CS 70, Spring 2008, Note 8 4
1. Alice cuts the cake into three pieces that she considers to be of equal measure.
2. Bobtrimsthepieceheconsidersworththemostsothat,aftertrimming,theremainderisexactlyworth
the same (by his measure) as the 2nd-largest. The trimmings are set aside for the end.
3. Carol takes whichever of these 3 pieces (excluding the trimmings) she considers worth the most.
4. If in step 3 Carol took the piece that Bob trimmed, then:
(a) Bob takes whichever of the two remaining pieces (excluding the trimmings) he considers worth more. Alice gets the piece that neither Carol nor Bob took.
(b) Next, to divide the trimmings, Bob cuts the trimmings into three pieces he considers of equal worth. Carol chooses one of those three (whichever she considers worth most), then Alice chooses one (whichever she considers worth more), then Bob takes whatever is left.
5. Otherwise, if in step 3 Carol did not take the piece that Bob trimmed, then:
(a) Bob must take the piece he trimmed in step 2. Alice gets the piece that neither Carol nor Bob took.
(b) Next, to divide the trimmings, Carol cuts the trimmings into three pieces she considers of equal worth. Bob chooses one of those three (whichever he considers worth most), then Alice chooses one (whichever she considers worth more), then Carol takes whatever is left.
It is possible to prove that this protocol is envy-free, but we will not do so.
As far as I know, it is an open problem to devise an efficient protocol for envy-free cake-cutting for an arbitrary number of participants.
CS 70, Spring 2008, Note 8 5