Transcript kirk - York University

Cake Cutting is
and is not a Piece
of Cake
Jeff Edmonds, York University
Kirk Pruhs, University of Pittsburgh
Informal Problem Statement



n self interested players wish to divide items
of value such that each player believes that
they received at least 1/n of the value
Players may not agree on the values of items
Players may be deceitful, cunning, dishonest,
etc.
An Instance of Cake Cutting From
History
A Politically Incorrect Reference to
Cake Cutting
Classic Problem Definition


n players wish to divide a cake = [0, 1]
Each player p has an unknown value function Vp


Vp[x, y] = how much player p values piece/interval [x, y]
The protocol’s goal is Fairness: Each honest player p
is guaranteed a piece of cake of value at least
Vp[0,1]/n = 1/n
History




Originated in 1940’s school of Polish
mathematics
Picked up by social scientists interested in
fair allocation of resources
Texts by Brams and Taylor, and Robertson
and Webb
A quick Google search reveals cake cutting is
used as a teaching example in many algorithms
courses
Classic Two Person Discrete
Algorithm (n=2): Cut and Choose


Person A cuts the cake into two pieces
Person B selects one of the two pieces, and
person A gets the other piece
Two Person Continuous Algorithm
(n=2): Moving Knife



Protocol moves the knife continuously across
the cake until the first player say stop
This player gets this piece, and the rest of
the players continue
Moving knife algorithms are considered
cheating by discrete algorithmic researchers
and we do not consider them here
Formalizing Allowed Operations

Queries the protocol can make to each player:



Eval[p, x, y]: returns Vp[x, y]
Cut[p, x, v]: returns a y such Vp[x, y] = v
All know algorithms can be implemented with
these operations
Two Person Algorithm (n=2):
Cut and Choose


y = cut(A, 0, ½)
If eval(B, 0, y) ≤ ½ then


Player A gets [0, y] and player B gets [y, 1]
Else

Player B gets [0, y] and player A gets [y, 1]
Three Person Algorithm (n=3):
Steinhaus





YA = cut(A, 0, 1/3)
YB = cut(B, 0, 1/3)
YC = cut(C, 0, 1/3)
Assume wlog YA ≤ YB ≤ YC
Player A gets [0, yA], and players B and C “cut
and choose” on [yA, 1]
O(n log n) Divide and Conquer
Algorithm: Evan and Paz




Yi = cut(i, 0, 1/2) for i = 1 … n
m = median(y1, … , yn)
Recurse on [0, m] with those n/2 players i for
which yi < m
Recurse on [m, 1] with those n/2 players i for
which yi > m
Problem Variations



Contiguousness: Assigned pieces must be
subintervals
Approximate fairness: A protocol is c-fair if
each player is a assured a piece that he gives
a value of at least c/n
Approximate queries (introduced by us?):


AEval[p, ε, x, y]: returns a value v such that
Vp[x, y]/(1+ε) ≤ v ≤ (1+ ε) Vp[x, y]
ACut[p, ε, x, v]: returns a y such
Vp[x, y]/(1+ε) ≤ v ≤ (1+ ε) Vp[x, y]
Problem Variations
Deterministic
vs.
Randomized
Exact vs.
Approximate
Queries
Exact vs. O(1)
Fairness
Contiguous vs.
General Pieces
Complexity =
number of
queries
Reference
*
Exact
*
*
O(n log n)
Even and Paz
1984
*
*
Exact
Contiguous
Ω(n log n)
Sgall and
Woeginger
2003
Deterministic
*
*
*
Ω(n log n)
Edmonds and
Pruhs
*
Approximate
*
*
Ω(n log n)
Edmonds and
Pruhs
Randomized
Exact
Approximate
General
O(n)
Edmonds and
Pruhs*
* The proof is currently only roughly written up at this point
Outline

Deterministic Ω(n log n) Lower Bound






Definition of Thin-Rich game
Sufficiency to lower bound Thin-Rich
Definition of value tree cakes
Lower bound for Thin-Rich
Hint at Randomized Ω(n log n) Lower Bound
with Approximate Cuts
Randomized O(n) Upper Bound
Thin-Rich Game

Game Definition: Find a thin rich piece for a
particular player



A piece is thin if it has width ≤ 2/n
A piece is rich if it has value ≥ 1/2n
Theorem: The complexity of cake cutting is at
least n/2 times the complexity of thin-rich

Proof: In cake cutting, at least n/2 players have to
end up with a thin rich piece
Value Tree
1/4
1/2
1/4
1/4
1/4
1/4
1/4
1/2
1/2
1/4
1/4
1/2
½*¼ ½*¼ ½*½ ¼*¼ ¼*½ ¼*¼ ¼*¼ ¼*½ ¼*¼
0
1/9
2/9
3/9
Value = Product of edge labels
4/9
5/9
6/9
7/9
8/9
1
Deterministic Ω(log n) Lower Bound
for Thin-Rich



Theorem: To win at Thin-Rich, when the input is
derived from a value tree, the protocol has to find a
leaf where at least 40% of the edge labels on root to
leaf path are ½
Theorem: From each query, the protocol learns the
edge labels on at most two root to leaf paths
Theorem: The deterministic complexity of Thin-Rich
is Ω(log n)

Proof: Reveal edges with label ¼ on the two paths learned
by the protocol
Randomized Lower Bound


Theorem: From each approximate query, the protocol
learns the edge labels on at most two root to leaf
paths, and at most one constant depth triangle
Theorem: The randomized complexity of thin-rich
with approximate queries is Ω(log n)

Proof: Use Yao’s technique. For each vertex in the value
tree, uniformly at random pick the edge to label ½. The
expected number of labels of ½ on all known labeled
paths after k queries is O( (log3 n)/3 + k)
Outline



Deterministic Ω(n log n) Lower Bound
Hint at Randomized Ω(n log n) Lower Bound
with Approximate Cuts
Randomized O(n) Upper Bound




O(1) complexity randomized protocol for Thin-Rich
Cake cutting algorithm
Generalized offline power of two choices lemma
Non-independent random graph model
O(1) Complexity Randomized Protocol
for for Thin-Rich
1.
2.
3.
4.
5.
Pick an i uniformly at random from 0 … n-1
x = Cut[0, i/n]
y = Cut[ 0, (i+1)/n]
If (y-x) ≤ 2/n then return piece [x, y]
Else goto step 1
Randomized Protocol for Cake
Cutting

Protocol Description:




Each player repeatedly applies randomized thin-rich
protocol to get 2d pieces
For each player, pick one of the two tentative pieces in
such a way that every point of cake is covered by at most
O(1) pieces. If this is not possible, then start over again.
Theorem: This protocol is approximately fair
We need to show that the second step of the
protocol is successful with probability Ω(1)
Digression(1)



Power of Two Choices Setting: n balls, each
of which can be put into two of n bins that
are selected independently uniformly at
random
Online Theorem: The online greedy
assignment guarantees maximum load of
O(log log n) whp
Offline Theorem: There is an assignment
with maximum load O(1) whp
Digression(2): Proof of Offline
Power of Two Choices Theorem

Consider a graph G





Vertices = bins
One edge for each ball connecting the corresponding
vertices
Important: Edges are independent
Lemma: If G is acyclic then the maximum load is 1
Classic Theorem: If a graph G has n/3 independent
edges, then G is acyclic whp


Proof: Union Bound.
Prob[G contains a cycle C] ≤ ΣC Prob[C is in the graph] ~
Σi (n choose i) * (1/3n)i
Key Theorem for O(n) Bound: Generalized
Offline Balls and Bins




Each of n players arbitrarily partition [0, 1] into n
pieces
Each player picks uniformly at random 2*d pieces
Then with probability Ω(1), we can assign to each
player one of its 2*d pieces so that every point is
covered by at most O(1) pieces
This is equivalent to offline balls and bins if the
partition is into equal sized pieces, except that:


We may need d > 1, and
We don’t get high probability bound
Why a High Probability result is Not
Achievable
.
.
.
Probability of overlap of k ~ (n choose k) / nk
Problem Case: Forks


Theorem: With probability Ω(1) there is no
fork of depth ω(1)
Therefore we throw out forked paths, and
proceed
Fork of depth 3
Directed Graph for Cake Cutting (d=1)
picked
picked
Vertex
Vertex
picked
picked
Vertex
Vertex
Sufficiency Condition

Theorem: The maximum load is at most 1 if
there is not directed path between the two
pieces of the same person
One Difficulty: Edges May Not be
Independent
Dealing with Dependent Edges



Lemma: There are not many dependent edges
Lemma: Each possible path, between two
pieces of the same player, can have at most
two dependent edges
Lemma: With probability Ω(1) there is no
path between two pieces of the same player
Conclusions


Generalized offline balls and bins theorem
may be useful elsewhere
The model of random graphs, where there
are some dependencies on the edges, and our
analysis may be useful elsewhere

Is dependent random graph model novel ?