15-451 Algorithms 12/03/09
Fair division and cake cutting
- Setup and definitions
- 2 people
- fair cake cutting
- envy-free cake cutting
===========================================================================
(A good book on this kind of material is Brams and Taylor, "Fair Division".)
Today we'll be talking about the concept of fair division of some
collection of resources, which has many important applications in
economics and the social sciences. The metaphor we'll be using is how
to fairly divide a cake (though some of the protocols won't
necessarily so practical for actually cutting cake...).
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.
ASSUMPTIONS:
* each person has a personal value system for assigning a real,
non-negative value to each piece of cake, with entire cake having
value 1. But the cake is not necessarily uniform (may have
chocolate, vanilla, frosting, etc) and some parts of the cake (eg
chocolate) may be more valuable to one person than another.
* value is a measure: if a cake is divided into a finite number of
pieces, then for any person, the sum of the values of all the
pieces of cake equals 1.
* the cake is a divisible good (can be cut in any way you like). In
particular, take a piece of cake with value v to you. For any real
number x, 0 < x < 1, you can divide it into 2 pieces having values
xv and (1-x)v respectively to you.
* each person follows *observable* aspects of the protocol. For
example, if the protocol calls for Alice to cut the cake into 3
pieces of equal value to her, 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). So, e.g.,
not going to worry about someone stealing the entire cake in the
middle of the 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.
[Note: it's possible for every person to have *more* than 1/n of the
cake - how??]
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/her measure as any other participant.
2-people
========
Say we have two people, Alice and Bob. If we have Alice cut and give
Bob a piece, is that a fair protocol? No. What would be better?
The standard 2-person protocol is fair and envy-free:
Alice: cut cake into two equal pieces (equal to her)
Bob: choose the piece of greater value (value to him)
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
(can anyone see an example of an allocation that would be fair but not
envy-free? You'll need at least 3 players).
=======================================================================
Fair division for n players
===========================
Can we design a protocol that's fair for n > 2 players? Let's think
about 3 players. What if Alice splits, then Bob chooses one for himself,
then Charlie chooses one for himself, and then Alice gets what's
left. Is this fair? Why not?
Here's a better way.
Method 1 (continuous protocol)
-----------------------------
A knife is slowly swept across the cake. When the portion size
reaches 1/n according to your own value system, raise your hand.
First person to raise their hand gets the piece of cake (break ties
arbitrarily).
Why is this fair? (anyone who gets cake before you gets at most
1/n value according to you, so there's always at least 1/n left)
Is it envy-free? No.
One problem with above protocol is the sweeping knife requires
continuous time. But we can also make a discrete version of it.
Method 2 (discrete protocol)
---------------------------
1. Have first person cut piece P of value 1/n (value to himself).
2. Go through rest of people one at a time. When it's your turn, if P
has value > 1/n to you, you may trim it if you want to. (Protocol
says: trim to value exactly 1/n).
3. The last person to trim P gets it (if nobody did, then person 1
gets it).
Then repeat with the remainder.
Why is this fair? Only way someone else can get P is if its value is
at most 1/n to you. (And, you're never forced to take P if its
value is < 1/n)
(Hint for actual cake: just make marks in the icing, don't actually
cut cake until step 3).
================================================================
Envy-free cake cutting is much harder. For general n, best known is
envy-free procedure in asymptotic sense (can get envy < epsilon for
any epsilon > 0 as # cuts goes to infinity). We will focus on n=3,
where you can get it exactly.
3-person envy-free cake-cutting (by Selfridge and Conway)
---------------------------------------------------------
Let's call the three people Alice, Bob, and Charlie. We're going to
do this in two stages. First, let's create an envy-free division in
which we have some extra "trimmings". Once we have that, we can then
figure out a way to divide the trimmings so that this remains
envy-free.
First stage - Divide cake with trimmings
Start by having Alice divide the cake in thirds (by her measure).
Then have Bob trim the largest piece so that it's now (to him) equal
in value to the second largest. Let's call this piece "T" (for
"trimmed"). We'll deal with the part taken off later -- put it
aside for now.
Now we have players go in order Charlie, Bob, Alice picking the slice
they like best but with the condition that Bob must pick slice T if
Charlie didn't take it already.
Claim: the first state is envy free.
Proof: It is envy-free to Charlie since he picks first. It is
envy-free to Bob since he has two equally-favorite pieces. And it is
envy-free to Alice since she split things equally in the first place,
so the only slice she might not want is T, but the protocol guarantees
she doesn't have to take it.
Second stage - Deal with trimmings
So you might think that now we're just back at our original problem.
However, we have one key new property that we can exploit - Alice will
remain envy-free regardless of the amount of cake that we give to the
person who received piece T (since she originally cut the cake into
equal thirds). However, she might envy the person who didn't get T,
so we can't just forget about her.
Now, whichever of Bob or Charlie *didn't* get T cuts the trimmings
into thirds. The other of them (the one who *did* get T) chooses
first, then Alice, then the person who cut goes last.
Claim: the second stage is envy free too.
Proof: It's envy free to the person who chooses first obviously. It's
also envy free to Alice since she never envies the person who got T
and she goes before the other one. Finally, it's envy-free to the
person who goes last since he did the cutting and made 3 equal pieces.
So, we're done. Note: it's critical here that values are additive, so
if you don't envy someone's stage-1 slice and you don't envy their
stage-2 slice then you don't envy their combination.
--
As a side note, there are many other types of fair division
protocols and problems. E.g., can also look at the inverse of these
problems (say if you wanted to divide chores up such that any person
got at most 1/n of the work).