Fair and Envy-Free Cake-Cutting 3 May 2007
Manuel Blum
DEFINITION: A PROTOCOL is a set of instructions for n participants. A
protocol is like an algorithm EXCEPT that the participants may choose to
not follow the protocol.
Certain promises are made to those who follow protocol, and these are
guaranteed whether the others follow protocol or not. No guarantees are
made to those who do not follow protocol.
DEFINITION: A CAKE CUTTING PROTOCOL is a protocol for n participants,
without the benefit of any external trusted party, to partition the cake
into a finite number of pieces and distribute the pieces "fairly" to all n.
DEFINITION: A CUT is a partition of any piece of cake (maybe the whole
cake) into two (measurable) pieces.
ASSUMPTIONS:
* each person has a personal value system for assigning a real
positive value to each piece of cake.
* each person's value system gives value 1 to the entire cake.
* value is a measure: fix a person; if a cake is divided into a finite
number of (measurable) pieces, then for that person, each piece has
positive value, and the sum of the values of all the pieces of cake
equals 1.
* Each person has a sure eye: can look at and immediately determine
the value (in her value system) of any piece of cake.
* Each person has a steady hand and can cut a cake exactly as he
chooses to cut it. In particular, for any real number x, 0 < x < 1,
a person can divide any piece of cake having value v, say, into 2 pieces
having values xv and (1-x)v respectively.
* cake is not necessarily uniform: it may have chocolate, vanilla,
frosting, and fruit. Some parts of the cake (eg chocolate) may be more
valuable to one person than another.
* each person follows protocol except possibly in the matter of
declaring honestly the size or value he or she assigns each piece. For
example, if the protocol calls for Alice to cut the cake into 3 equal
pieces, she will indeed divide it into 3 pieces, not 2 or 4. However,
the pieces may not have equal value to her (in which case she is not
following protocol).
DEFINITION: A cake cutting protocol is FAIR if each participant who
follows protocol is guaranteed to receive at least 1/n of the cake
according to his/her own personal value system.
DEFINITION: A cake cutting protocol is ENVY-FREE if each participant who
follows protocol is guaranteed to receive by his/her measure at least as
much cake as any other participant, i.e., no person gets more cake!
For example, the standard 2-person protocol is envy-free:
Alice: cut cake into two equal pieces
Bob: choose the piece of greater value
If Alice follows protocol, she will divide the cake into two pieces of
equal value to her. Suppose it turns out that the two pieces are worth
1/3 and 2/3 to Bob.
If Bob follows protocol, he will get the piece worth 2/3 by his
measure. If he does not follow protocol, he may or may not get the
bigger piece (by his measure).
Notice that ENVY-FREE => FAIR (why?) but not the other way around
(why not?) .
An Envy-free Cake Cutting protocol for n=3
by Selfridge and Conway
STAGE 0.
0.1. Alice is to cut the cake into three equal pieces [by her measure].
0.2. Bob is to trim the largest piece to create a 2-way tie for largest
[by his measure], and sets the trimmings aside.
Note that no one has yet gotten a piece of cake.
THIS ENDS STAGE 0.
STAGE 1.
Trimmings aside, there are now 3 "pieces," which together we call cake1,
and the "trimmings," which we call cake2.
Cake1 is distributed in reverse order (Charlie, Bob, Alice) as follows:
1.1 Charlie picks [what he considers to be] the largest piece.
1.2. Bob takes the trimmed piece if Charlie has not taken it;
otherwise Bob takes [what he considers to be] the largest of the two pieces.
1.3. Alice takes the last remaining (untrimmed!) piece of cake1.
THIS ENDS STAGE 1.
As you may have noticed, this protocol has one gal, Alice, and two guys,
Bob and Charlie.
This helps to clarify the next and final stage 2:
Call the guy who took the trimmed piece T, and the other guy NT.
STAGE 2.
Cake2 (the trimmings) is distributed as follows:
2.1. NT divides cake2 into [what he thinks are] thirds.
2.2. T picks first, Alice picks second, NT gets the last of it.
THIS ENDS STAGE 2.
THIS ENDS THE PROTOCOL.
THEOREM: The above protocol is envy-free.
PROOF: By the end of stage 0, the protocol has generated 2 cakes: cake1
(in 3 pieces) and cake2 (trimmings).
By the end of stage 1, as we shall see, cake1 has been distributed,
one piece per participant, in an envy-free fashion. By the end of stage
2, as we shall see, cake2 has been divided into 3 pieces and cake1+cake2
has been distributed in envy-free fashion.*.
----------
* Here we use the fact that if a participant Pi values his piece of
cake1 at least as much as he values any other person's piece of cake1,
and if he values his piece of cake2 at least as much as he values any
other person's piece of cake2, then Pi values his final 2 pieces of cake
at least as much as he values any other participant's two pieces of
cake. This argument will be used for Bob and Charlie, but not Alice.
----------
It remains to prove that the protocol is envy-free to each of the
participants, Alice, Bob, and Charlie. Proofs for the latter 2 are
divided into 2 cases, depending on whether Bob or Charlie is T. In
each case, we show that the protocol is envy-free immediately after
stage 1, then extend this to show that it is envy-free at the end of
stage 2.
ENVY_FREE to ALICE: Alice divides the cake into 3 equal pieces. By the
end of stage 1, she gets one of the untrimmed pieces.
So at that point she will not envy either of the 2 guys, one of whom got
a trimmed piece, the other an untrimmed piece.
In fact, A will not envy T, the guy who got the trimmed piece, even if
that guy gets ALL the trimmings. Thus it is okay that T gets first pick
at a so-called "third" of the trimmings.
So Alice will not envy T. After that, she will get at least as much of
the remaining trimming as NT. Thus Alice will not envy NT.
ENVY-FREE to BOB: At the end of stage 1, Bob has one of the two largest
pieces, so at that point he envies neither Alice nor Charlie.
We now consider 2 cases:
CASE BOB = T: At the end of stage 1, Bob has the trimmed piece, which by
his measure is at least as large as each of the other two pieces of
cake1. In stage 2, he is given first pick at one of three pieces of
trimming, so he will not envy whoever gets second or third choice.
CASE BOB = NT: At the end of stage 1, Bob does not envy Alice or
Charlie. At the start of stage 2, Bob divides the trimmings into 3 equal
parts, so he will not envy either of the other two even though he gets
last pick on the trimmings.
ENVY-FREE to CHARLIE: In stage 1, Charlie gets first choice of the 3
pieces. So at the end of stage 1, he does not envy either Alice or Bob.
We now consider 2 cases:
CASE CHARLIE = T: Charlie gets first choice on the 3 pieces of trimming,
so he will not envy the other 2 after they get their (smaller) pieces of
trimming.
CASE CHARLIE = NT: Charlie decided that the untrimmed piece is the
largest of the 3 pieces, and took that piece, so he does not envy the
other two at the end of stage 1. As NT, he divides the trimmings into 3
equal pieces, so he will not envy the other two even though he gets last
pick at the trimmings.
THIS ENDS THE PROOF.