CS 15-451 Analysis of Algorithms 2 December 2004
Manuel & Avrim Blum
Today: Fair Cake Cutting
Envy-Free Cake Cutting.
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 guarantees are made to those who follow the protocol.
No guarantees are made to those who don't.
DEFINITION: A CAKE CUTTING PROTOCOL is a protocol for n
participants to divide a cake among themselves.
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 pieces, then for that person, each piece
has positive value, and the sum of the values of all the
pieces of cake equals 1.
* 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.
Each person has a steady hand and can cut a cake exactly
as he chooses to cut it.
* 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
they assign 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
own personal value system.
DEFINITION: A cake cutting protocol is ENVY-FREE
if each participant who follows protocol is guaranteed
to receive at least as much cake by his measure
as any other participant.
For example, the standard 2-persone 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 set 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 among the participants
in an envy-free fashion. By the end of stage 2, as we shall see,
cake2 has been divided into 3 pieces and distributed also in
envy-free fashion. Thus the entire cake is distributed among
the 3 participants in envy-free fashion*.
----------
* Here we use the fact that if 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.
----------
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 which 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.