Algorithmic Game Theory, Summer 2019 Lecture 23 (4 pages)

Caking Cutting
Thomas Kesselheim Last Update: July 3, 2019

Today, we will consider a problem of fair division. Again our goal is to find a mechanism
that works without money and makes all involved agents happy. Indeed, we experience such
problems throughout our daily life. Suppose a group of employees have to assign their work
shifts. Maybe for someone it is more important to not work at night, whereas somebody else
would prefer to be off work during the World Cup final.
Our focus today will be on cake cutting. We are given a cake and have to divide it among
the agents. It is different from the above example because the good can be divided arbitrarily.
The cake is not the same everywhere and therefore the agents’ preferences differ.

1 Model
The cake is modeled by the interval [0, 1]. We can cut it into pieces; each piece X is a union of
subintervals of [0, 1].
There are n agents N and each agent i ∈ N has a valuation function Vi , which assigns to
each piece X non-negative value Vi (X). For simplicity, we assume that there is a valuation
density function vi : [0, 1] → R≥0 such that the valuation Vi of X is determined as the integral
of vi over X Z
Vi (X) = vi (x)dx .
x∈X

So, in particular, if X = [a, b], then Vi (X) = ab vi (x)dx.

R

If X is the union of disjoint intervals, then the valuation for X is the sum of the valuations
for the intervals. That is, if X = [a, b] ∪ [c, d] for b < c, then
Z b Z d
Vi (X) = vi (x)dx + vi (x)dx = Vi ([a, b]) + Vi ([c, d]) .
a c
Ra
Note that it does not actually matter if we assign open or closed intervals because a vi (x)dx =
0.
We assume that Vi ([0, 1]) = 01 vi (x)dx = 1 for all i. That is, each agent i values the entire
R

cake as 1 but the value will usually be distributed differently along the interval.

Example 23.1. We could have v1 (x) = 1 for all x ∈ [0, 1], v2 (x) = 32 for x ∈ [0, 12 ], v2 (x) = 12
for x ∈ ( 12 , 1]. A feasible allocation is A1 = [0, 12 ], A2 = ( 12 , 1]. Now V1 (A1 ) = V1 (A2 ) = 12 but
V2 (A2 ) = 14 , V2 (A1 ) = 34 . So, agent 2 would consider this an unfair allocation because agent 1
gets more value from his point of view.

2 Fairness Properties
We will find an allocation A = (A1 , . . . , An ), where the Ai are disjoint and their union is [0, 1].
Each Ai is a union of intervals.
What makes an allocation fair? There are three standard notions:

• Proportionality: For all i ∈ N , Vi (Ai ) ≥ n1 .

• Envy-Freeness: For all i, j ∈ N , Vi (Ai ) ≥ Vi (Aj ).

• Equitability: For all i, j ∈ N , Vi (Ai ) = Vi (Aj ).

Algorithmic Game Theory, Summer 2019 Lecture 23 (page 2 of 4)

If all valuations are identical, these notions coincide. Proportionality requires that each
agent values his own piece at least n1 . This, however, does not exclude that another agent
gets a piece that he values even higher. This is explicitly forbidden in envy-freeness. In an
envy-free allocation, no agent would like to get another agent’s piece instead. Envy-freeness
implies proportionality because there always has to be one j for which Vi (Aj ) ≥ n1 . Otherwise
Vi ([0, 1]) < 1.
Equitability is an even stronger requirement by asking that an agent would be equally happy
with another agent’s piece.

3 Two Agents: Cut and Choose

There is a world-famous
Rt
cake cutting
R1
protocol for two agents: cut and choose. Agent 1 cuts the
point t such that 0 v1 (x)dx = t v1 (x)dx = 12 . Then agent 2 chooses between [0, t) and [t, 1],
depending on which value is higher for him.
This allocation is proportional: Vi (Ai ) ≥ 21 for both i. For agent 1, this is clear because he
cuts the cake exactly such that both pieces have value 12 . For agent 2, one of the two pieces has
value at least 21 .
The allocation is also envy-free: V1 (A1 ) = V1 (A2 ) by definition. Furthermore, V2 (A2 ) ≥
V2 (A1 ) because agent 2 chooses the preferred piece.
However, the allocation is not necessarily equitable. Suppose that v1 (x) = 1 for all x and
v2 (x) = 2 for x ≤ 21 and 0 otherwise. In this case t = 21 and V2 (A2 ) = 1, V2 (A1 ) = 0.
In this example, there is also an equitable allocation: Set A1 = [ 14 , 34 ], A2 = [0, 1] \ A1 . In
this allocation, both agents value their piece exactly as 12 . In contrast, there is no contiguous
equitable allocation. It is impossible to assign to each agent only a single interval such that both
are equally valuable for both.

4 Proportionality for Any Number of Agents

There is a reasonably simple algorithm by Dubins-Spanier (1961) to determine a proportional
allocation for any number of agents n. The algorithm runs for n iterations. In each of them, one
agent is allocated and leaves. We determine cuts t1 , . . . , tn−1 such that in the first iteration, we
allocate [0, t1 ), in the second [t1 , t2 ) and so on.

• Initialize t0 = 0, N1 = N

• For k = 1 to n − 1

– For each agent i in Nk , let tk,i be the value such that Vi (tk−1 , tk,i ) = n1 .
– Let i∗ be the agent with the smallest (i.e. leftmost) tk,i and let tk = tk,i∗ , Ai∗ =
[tk−1 , tk ).
– Set Nk+1 = Nk \ {i∗ }.

• Assign the remainder to the remaining agent in Nn .

Theorem 23.2. The allocation computed by the algorithm fulfills proportionality.

The idea is that in every iteration we only remove an interval that no agent values more
than n1 . Therefore, at any point in time, there is enough cake left to make the respective cuts.

Proof. Note that there could, in principle, be two reasons why the allocation does not fulfill
proportionality. On the one hand, it could be that one of the tk is larger than 1, which would
make the algorithm ill-defined. On the other hand, it could be that the remaining agent values
the remainder less than n1 .
Algorithmic Game Theory, Summer 2019 Lecture 23 (page 3 of 4)

Both is ruled out by the following invariant: For any k and any i ∈ Nk , Vi (tk−1 , 1) ≥ n−k+1 n .
n−k+1
That is, at the beginning of every iteration, the agents value the remaining cake at least n .
We can show the invariant by induction on k. For k = 1, it is trivially true. So, let us now
consider some k + 1 > 1. For every i ∈ Nk+1 , we have tk,i ≥ tk because tk is the smallest value
that we saw in round k. Therefore, Vi (tk−1 , tk ) ≤ Vi (tk−1 , tk,i ) = n1 . By this inequality and by
induction hypothesis,

n−k+1 1 n − (k + 1) + 1
Vi (tk , 1) = Vi (tk−1 , 1) − Vi (tk−1 , tk ) ≥ − = .
n n n
This completes the induction.

It is easy to see that for three or more agents this allocation is not always envy-free. It can
easily happen that the agent who got the first piece envies one of the other agents because they
get a piece that he values more than n1 .

5 Envy-Freeness for Three Agents

Finding an envy-free allocation is significantly more involved. But it is possible. In the following,
we will consider the case of exactly three agents. There, it is sufficient to make five cuts, meaning
that we get six intervals. The algorithm has an interesting history. It is named after John
Selfridge and John Horton Conway, who both discovered it independently but unfortunately it
was never published by either of them.
The algorithm is as follows:

• Agent 1 cuts the cake into three pieces X1 , X2 , X3 such that V1 (X1 ) = V1 (X2 ) = V1 (X3 ).

• Rename the pieces such that V2 (X1 ) ≥ V2 (X2 ) ≥ V2 (X3 ).

• Agent 2 cuts off X 0 ⊆ X1 such that V2 (X1 \ X 0 ) = V2 (X2 ).

First assignment phase, assigning [0, 1] \ X 0 :

• Agent 3 chooses one of X1 \ X 0 , X2 , and X3 .

• If agent 3 chose X2 or X3 , agent 2 gets X1 \ X 0 , otherwise he gets X2 .

• Agent 1 gets X2 or X3 depending on what is left.

Second assignment phase, assigning X 0 : Let T ∈ {2, 3} be the agent who got X1 \ X 0 in the first
phase, T̄ ∈ {2, 3} the other one.

• Agent T̄ cuts X 0 into three pieces X10 , X20 , X30 such that VT̄ (X10 ) = VT̄ (X20 ) = VT̄ (X30 ).

• Agent T chooses one of X10 , X20 , X30 .

• Agent 1 chooses among the remaining two.

• Agent T̄ gets the remaining piece.

Theorem 23.3. The allocation is envy-free.

Proof. Without loss of generality, we can assume that in the second phase agent T chooses X10 ,
agent 1 chooses X20 and X30 is left over for agent T̄ .
We now have to argue that no agent envies the outcome of the other agent.
Consider agent T . He gets (X1 \ X 0 ) ∪ X10 . Regardless of whether this is agent 2 or agent 3, we
always have VT (X1 \ X 0 ) ≥ VT (X2 ) and VT (X1 \ X 0 ) ≥ VT (X3 ). Furthermore, VT (X10 ) ≥ VT (X20 )
Algorithmic Game Theory, Summer 2019 Lecture 23 (page 4 of 4)

First cuts by agent 1:

X1 X2 X3

Agent 2 makes the larger two pieces the same size:

X0

Agent 2 or 3 cuts X 0 into three equal parts:

X10 X20 X30

Figure 1: A potential outcome.

and VT (X10 ) ≥ VT (X30 ) because he chooses first. So, no matter how the remaining pieces are
allocated among the other agents, he never envies one of them.
Now, consider agent T̄ . If this is agent 2, then he left a piece of the exact same value as
X1 \ X 0 that he will select in the first phase and another one that might have a smaller value.
Agent 3, by definition, chooses his most preferred piece in the first phase. Therefore, agent T̄
does not consider any piece in the first assignment phase larger than his own. In the second
assignment phase, he considers all pieces identically valuable because he is the one to cut them.
Finally, let us consider agent 1. He does not envy agent T because agent T only gets a subset
of X1 , whereas agent 1 cut the original pieces so that V1 (X1 ) = V1 (X2 ) = V1 (X3 ). He does not
envy agent T̄ either. We have V1 (X2 ) = V1 (X3 ) because he cut these pieces and V1 (X20 ) ≥ V2 (X30 )
because he chooses first.

6 Outlook
The topic of fair division is an active research area. For example, how can one find an envy-free
allocation for any number of agents? Recently, there was a result that the number of steps
is always bounded in terms of a function that only depends on n, regardless of the valuation
functions. However, one is very far from “efficient” algorithms. This may not be surprising given
how complicated things become already for n = 3.
There is also the question of incentive compatibility. As a matter of fact, none of the
algorithms so far is robust against agents strategically misreporting their valuations.

Further Reading
• Chapter 13 by Ariel Procaccia in “Handbook of Computational Social Choice” edited by
Brandt, Conitzer, Endriss, Lang, and Procaccia.