### Cake cutting:

```CAKE CUTTING
NOT JUST A CHILD’S PLAY
How does one fairly divide goods among
several people?
What is “fairness” ?
Envy-freeness
Proportionality
• Each participant prefers
keeping his own allocation
to swapping with any other
participant.
• Each of the n participants
receives at least 1/n of his
value for getting everything.
Divisible goods and Indivisible goods
Divisible goods
• Such as land, time, or
memory on a computer.
Indivisible goods
• Such as a house or the
computer itself.
What’s cake-cutting ?
Cake Cutting =
Allocating a heterogeneous divisible good among
multiple players with different preferences
Outline
• 1. Cake cutting mechanisms
• 2. Complexity of cake cutting
• 3. A game-theoretic viewpoint
• 4. Optimizing welfare
Cake cutting mechanisms
Chapter 1
Cut and Choose
• The famous cut and choose algorithm:
• 1st step: the first player divides the cake into two
pieces that he values equally.
• 2rd step: the second player then chooses the piece
that he prefers.
• 3rd step: the first player receives the remaining
piece.
Is the cut and choose algorithm fair?
Proportional?
Envy-free?
• Yes! Note that --
• Yes! In fact –
• The first player values
both pieces at exactly
1/2,
• While the second
preferred piece, which
must be worth at least
1/2.
• For the case of two
players, the concepts
of envy-freeness and
proportionality
coincide!
• As we move from the two player setting to the nplayer setting, fairness becomes harder to achieve.
• Nevertheless, several elegant algorithms guarantee
proportional allocations.
Dubins-Spanier 1961
• In each stage, a referee slowly moves a knife over the cake from
left to right.
• When the knife reaches a point such that the piece of cake to
the left of that point is worth 1/n to one of the players, this player
shouts “stop”.
• The referee makes a cut, and the piece of cake to the left of the
cut is given to the player.
• The satisfied player and allocated piece are then removed.
• The process is repeated with the remaining players and leftover
cake, until there is only one player left. The last player receives
the unclaimed piece.
Even-Paz 1984
• Assume for ease of exposition that the number of
players is a power of 2.
• Similarly to the discretized version of the latter
algorithm, each time the procedure is executed,
the players make marks where the cake to the left
of the mark is valued at 1/2 (rather than 1/n, as
before).
Even-Paz 1984
• Rather than removing a single player ---• we separate the players into two subsets of equal size,
such that all the marks made by the players of the first
subset lie to the left of the marks made by the players of
the second subset.
• The players in the first subset then receive the piece of
cake that lies to the left of their rightmost mark, while the
players in the second subset receive the remaining cake.
Even-Paz 1984
• Then, resursion !
-----------------------------------------------------------------------------• A single player participates in exactly log n calls to
the procedure, and therefore each player receives
a piece of cake worth at least (1/2) = 1/.
How to guarantee envy-freeness?
• While proportionality is well understood, envyfreeness is a far more elusive property.
• Proportionality is always implied by envy-freeness, in
the case of divide the whole cake.
How to guarantee envy-freeness?
• For three players,
----------- Selfridge-Conway 1960--------• For an arbitrary number of players,
------------Brams-Taylor 1992-----------------
Selfridge-Conway 1960
Stage 0
• Player 1 divides the cake into three equal pieces
according to his valuation.
• Player 2 trims the largest piece (that is, cuts off a
slice) such that there is a tie between the two largest
pieces in his eyes.
• We call the original cake without the trimmings Cake
1, and we call the trimmings Cake 2.
Selfridge-Conway 1960
Stage 1 (Division of cake 1)
Stage 2 (Division of cake 2)
• Order: 3 - 2 – 1
• Ū divides cake 2 into
three equal pieces
according to his
valuation.
• Player 3 chooses one of the
three pieces of Cake 1.
• Either player 2 or player 3
denote that player by U,
and the other player by Ū.
• Player1 is allocated the
remaining(untrimmed)
piece.
• Players U, 1, and Ū
choose the pieces of
Cake 2, in that order.
Brams-Taylor 1992
• The first envy-free cake cutting algorithm for an
arbitrary number of players!
• However—
• Through the computational lens, the algorithm’s
running time is unbounded.
Brams-Taylor 1992
• A bounded envy-free algorithm for the five-player
case was recently proposed by Saberi and Wang
2009.
• However, the n-player case remains open!
• Is envy-free cake cutting inherently complex?
Complexity of cake cutting
Chapter 2
Robertson-Webb’s model 1998
Evaluation query
Cut query
• Which asks a player i
for his value for the
subinterval between
two given points x and
y:
•  ,  =  [, ] .
• which asks a player i to
mark a subinterval
worth a given value α
starting at a given point
x:
•  , α =  [, ]
• S.t.
•  [, ] = α.
Robertson-Webb’s model
Dubins-Spanier
• The number of required cut queries:
• n+(n-1)+(n-2)+…+2 =
(+2)(−1)
=
2
O(2 )
Even-Paz
• The number of required cut queries:
• 1*n+2*(n/2)+4*(n/4)+…+(n/2)*2= log
The complexity of proportional cake cutting
• Are there proportional cake cutting algorithms that
require significantly fewer than  queries?
• Woeginger-Sgall 2007
• allocates connected pieces requires at least c ∗
log queries , where c is a constant.
• Edmonds-Pruhs 2006
• allocates disconnected pieces, also requires at
least c ∗ log queries.
The complexity of envy-free cake cutting
• We would like to be able to establish that bounded
envy-free cake cutting algorithms do not exist.
• Stromquist 2008
• established such a nonexistence result under the
assumption that the algorithm must allocate
connected pieces (even for the 3-person case).
The complexity of envy-free cake cutting
• When connected pieces are not assumed—
• Procaccia 2009
• In the Robertson-Webb model, required to
compute an envy-free allocation is at least on the
order of 2 .
• Envy-freeness is provably harder than proportionality.
Ways to circumvent the problem
• Approximately approach
----------- Lipton et al. 2004---------------• Special valuation structure
------------Chen et al. 2010-----------------
A game-theoretical viewpoint
Chapter 3
Strategyproof
• Strategyproof: Players must not be able to gain from
manipulating the algorithm, regardless of the
actions of others.
Cut and choose algorithm is not
strategyproof
Strategyproof cake cutting algorithm
• Chen et al. 2010
• perfect partition: partitioning the cake into n pieces
1 …  such that each player i has value exactly 1/n
for each of these pieces (not just his own), that is,
( ) = 1/n for every j.
• Let’s suppose for a short while that we have a
magical method for perfect partitioning the cake.
Strategyproof cake cutting algorithm
• Chen et al. 2010
• Chen’s algorithm first computes a perfect partition,
and then gives each player a random piece.
• Clearly, the algorithm is strategyproof. Because for
any partition, the expected value of a random
piece is exactly 1/n, that’s
1
1
1
(1 )+…+  ( )= ( (1 )+…+

( ))=
1

∗1=
1

How to compute a perfect partition
• Chen et al. 2010 showed that perfect partitions can
be computed efficiently when valuations have a
piecewise constant structure.
• piecewise constant: each player only desires
certain pieces of cake, and values each of these
pieces uniformly.
• Additionally, if each player has a single desired
piece of cake that he values uniformly, fairness and
truthfulness can be guaranteed without resorting to
randomization.
Strategyproof cake cutting algorithm
• The design of strategyproof cake cutting algorithms
is still largely an open problem.
• First, because the above algorithms (especially the
deterministic one) can only handle restricted
valuations.
• Second, because these algorithms cannot be
simulated in the Robertson-Webb model.
Optimizing welfare
Chapter 4
Social welfare
• Utilitarian social welfare and egalitarian social
welfare
• We assume that all players have the same value for
the whole cake, say \$1.
• Price of fairness: the worst-case ratio between the
social welfare of the optimal allocation, and the
social welfare of the best fair allocation.
Price of fairness—an example
• Consider the following scenario. Suppose the cake
[0, 1] has  disjoint subintervals, each of length
1/ .
• Each of the first “large”  players only desires one
of these subintervals; no two “large” players desire
the same subinterval, and each large player values
his subinterval uniformly.
• The remaining n −  “small” players value the
whole cake uniformly.
Price of fairness—an example
Any proportional allocation
The welfare-max allocation
• The social welfare is
smaller than 2.
• Just divide the entire
cake between the
larger players.
• Secure social welfare
of .
Price of fairness—an example
• So in this example, the price of proportionality is at
least /2.
• The price of envy-freeness is at least as high
because envy-freeness implies proportionality.
• Aumann –Dombb 2010 studied the price of fairness
under the assumption that connected pieces must
be allocated.
• A interesting insight in this context is
by throwing away pieces of cake, one can increase
the social welfare of the best proportional (or envyfree) allocation!
Optimal fair cake divisions
• For piecewise constant valuations, welfare-maximizing
proportional or envy-free allocations can be computed
in polynomial time.
----------------------Cohler et al. 2011------------------------------• Computing optimal fair cake divisions with connected
pieces is significantly harder.
-----------------------X. Bei et al. 2012-------------------------------• Even if we abandon fairness completely and just focus
on optimizing welfare.
---------------------Aumann et al. 2012------------------------------
• Pareto-efficient:
in the sense that no other allocation is valued at
least as highly by all players, and is strictly better for at
least one player.
• there are examples where no welfare-maximizing
envy-free allocation is Pareto-efficient, even when
there are only three players with piecewise constant
valuations.
----------------------Brams et al. 2012-----------------------------
• Should we sacrifice social welfare to obtain Paretoefficiency? How much must be sacrificed?
• More generally, what would constitute an ideal
cake division?
• ??……….
• These conceptual questions may lead to significant
technical insights on the role of optimization in cake
cutting!
This field is fun, potentially
very significant, and gives rise
to great intellectual challenges!
THANK YOU!
ZHENG BO
```