![](https://csdnimg.cn/release/download_crawler_static/15145411/bg4.jpg)
Deng, Qi, and Saberi: Algorithmic Solutions for Envy-Free Cake Cutting
1464 Operations Research 60(6), pp. 1461–1476, © 2012 INFORMS
steps recursively, we can find one fully colored triangle in
time O4N 5 + O4N /25 + · · · + O415 = O4N 5. The above
method can be generalized to high-dimensional problems.
By using the same argument, we only need to examine the
edges on the boundary, which reduces the complexity on
the exponent from d to d − 1.
For the lower bound, the results are obtained by a reduc-
tion from BROUWER (Deng et al. 2011).
1.4.3. FPTAS for Three Players with Monotone Util-
ity Functions. For the special case of monotone utility
functions, we are able to utilize the monotonicity to con-
struct an -approximate envy-free solution in time polyno-
mial in log4N 5 for three players.
We rely on the general approach of binary search on the
parity but exploit the monotonicity of the best choice along
certain lines in the simplex. We will sketch the main idea
of the approach in the next two paragraphs and leave the
details to the last section.
Any player with a monotone utility function would prefer
A to B for B ⊆ A. Therefore, when one cut is fixed, one
of the three pieces is fixed. Any player’s preference on
the other two pieces will change monotonically as another
cut changes from left to right. We use the coordinate X =
4X
0
1 X
1
1 X
2
5, along the line of fixed X
0
, and let X
1
increase
from 0 to N − X
0
. The preference of a player’s choice
will start with the last piece, to the first piece, and to the
middle piece (one or two of them may be missing). Similar
monotonicity holds when X
2
is fixed. For each player, we
can find the break point of the choices by binary search in
O4log N 5 time.
Because of the monotonicity along those two direc-
tions, we can calculate the indices of cut edges efficiently.
Therefore, the indices of the two regions split by the cut
can be decided quickly. We will stay on the region with
an odd index so that we should terminate with one that is
a diamond-shaped polygon consisting of at most two base
cells. By parity, one of the two cells is a fully colored base
triangle. The overall query complexity and running time
will be of O4log
2
N 5.
1.5. Organization
The rest of the paper is organized as follows. We first intro-
duce the relevant concepts, the mathematical and computa-
tional models in §2.
In §3, we present the complexity results for finding an
envy-free cake-cutting solution, with a matching algorith-
mic bound under the oracle-function model, as well as
a PPAD-completeness proof for the polynomial function
model.
In §4, we show that for three players there is an algo-
rithm for finding an -approximate envy-free solution in
time polynomial in log4N 5 under certain conditions. In
comparison, we prove that Stromquist’s solution demands
an exponential number of queries.
Finally, we conclude our work with discussion and open
problems in §5.
2. Definitions and Basic Concepts
In this section, we will briefly review the basic definitions
and results in combinatorial topology and computational
complexity that will be used in the proof.
2.1. Sperner’s Lemma
In general, a d-simplex ã
d
4X
0
1 X
1
1 0 0 0 1 X
d
5 is the con-
vex hull of d + 1 independent vectors X
0
1 X
1
1 0 0 0 1 X
d
,
i.e., ã
d
= 8v v =
P
d
i=0
i
X
i
1
i
¾ 01
P
d
i=0
i
= 19, where
4
0
1
1
1 0 0 0 1
d
5 are the barycentric coordinates of v. For
v ∈ ã
d
, define 4v5 = 8i
i
> 09.
A face of a simplex ã
d
4X
0
1 X
1
1 0 0 0 1 X
d
5 is any simplex
ã
k
4X
i
1
1 X
i
2
1 0 0 0 1 X
i
k
5 where 0 ¶ i
1
< i
2
< · · · < i
k
¶ d.
Triangulation of a simplex is a procedure that partitions
the original d-simplex ã
d
into several small d-simplices
ã
1
1 0 0 0 1 ã
m
such that for ∀ i1 j, ã
i
∩ ã
j
is either empty or a
common face.
Let V be the union of the vertices of all ã
i
s. Sperner’s
lemma is defined on V , the vertices of a triangulated sim-
plex with Sperner coloring.
Definition 1 (Sperner Coloring). For a triangulated
simplex ã with vertex set V , a coloring
2 v → 801 11 0 0 0 1 d9 is called Sperner coloring
if ∀ v ∈ V 2 4v5 ∈ 4v50
A Sperner colored triangulated simplex has a special
property that is best explained by the concept of index.
Definition 2. For a d-dimensional simplex with vertices
assigned all colors 801 11 0 0 0 1 d9, we define its index as 1.
Otherwise, it is defined to be zero. For a triangulated poly-
gon in d-space, its index is defined to be the sum of the
indices of its base simplices modulo two.
For a polygon P , denote by ¡P the boundaries of P .
Note that the triangulation of P induces a triangulation of
¡P into 4d −15-dimensional simplices. Naturally, we define
index
d−1
4¡P 1 5 =
P
d−1
∈¡P
index
d−1
4
d−1
1 5. Note that a
4d − 15 dimension cell has index 1 if its vertices have
all colors in 801 11 0 0 0 1 d − 19, 0 otherwise. The following
result is useful (see, e.g., Todd 1976).
Proposition 1. index4P1 5 ≡ index
d−1
4¡P 1 5 mod 2.
With the restriction of Sperner coloring, we immediately
obtain the following:
Theorem 1 (Sperner’s Lemma, 1928 (Sperner 1928)).
For a simplex that is triangulated and colored by Sperner
coloring, the number of simplices in the subdivision with
index 1, i.e., its vertices all colored differently, is odd.
Sperner’s lemma states that a triangulated simplex with
a Sperner coloring has a base cell such that all its vertices
have different colors. Such a simplex is commonly referred
to as a Sperner Simplex.