This content explores the mathematical concept of "fair division," specifically focusing on the problem of "cake cutting" where a divisible good (the cake) must be allocated among players with differing preferences. It delves into defining fairness mathematically, presenting algorithms for achieving fair allocations, and analyzing their computational complexity.
Mind Map
Click to expand
Click to explore the full interactive mind map • Zoom, pan, and navigate
so the
topic today is cake cutting it's a topic i'm
i'm
super excited about it's both kind of a
chance to tell you about an area
that i'm passionate about fair division
so we'll talk about
some of the basic principles in fair
division we'll talk about what fairness
means in mathematical terms
and i'll also have a chance to tell you
a bit about some practical applications
of this theoretical research
but uh you know the uh one of the main
reasons why we're talking about this at
this point
is that it gives us another opportunity
to think about running time and
time complexity in a different way so
we'll say that in order to think about
time complexity in this context
we'll need to adopt a different way of
thinking about
time complexity which will give us
another perspective on what time
complexity means
so there are these two big purposes for
the lecture one just to tell you about
for division
two to just give you a different
so you know we'll be talking about
k-cutting to be a bit more formal what
does k-cutting mean
the question is how to fairly divide the
heterogeneous the visible good
between players with different preferences
preferences
so what i mean by heterogeneous i mean that
that
different parts of the cake look you
know are
different so some of the cake might have
chocolate toppings some
might have strawberries and so on if you
take a piece of cake of
some size it might differ from a
different piece of cake of the same size
so that's what i mean by heterogeneous
and will make this more formal
the picture here is from an article that
i wrote about k-cutting
i know six years ago it's cute but it's
misleading in two ways
one is that this cake is homogeneous
it's not heterogeneous it all looks the same
same
the second is that this cake is circular
and we're going to think of a cake as an
interval so think about rectangular
cakes so let's make this a bit more formal
formal
the cake is going to be the interval 0 1
so we want to divide the interval 0 1 between
between
uh there's different you know hungry
kids that want to eat the cake
and we're going to have a set of players
or the ones who are getting the cake
which we'll denote by capital n and the
players themselves will be
now a piece of cake is a finite union
of disjoint intervals okay so this is
kind of a very formal way of thinking
about it
and i don't want you to worry about you
know topological issues we
you know we uh won't uh need to worry
about subtleties for the stuff that
we'll talk about
but to be a bit formal at this stage a
piece of cake is a finite union
of disjoint intervals so for example you
might take
this interval and this interval together
they form a piece of cake
and the crucial thing is the the piece
doesn't have to be connected
so in this example the intervals come
from two different parts of the cake
they're not connected they still form a
okay so again being pretty formal uh you
know just to
make things clear but we won't need this
level formality later on
we're thinking about players with
different valuation functions
where every player has its own value for
pieces of cake so different players
value the cake differently we denote the
evaluation function of player i
by vi and we're going to assume that
this valuation function v
high vi satisfies a couple of properties
the first property is additivity that
means that if you take two disjoint
pieces of cake
the value i has for the union is just
the sum of values
so in this example if
this piece of cake is worth alpha to
player i and this piece of cake this
interval is worth beta
when you put them together and give them
to player i they're worth alpha plus beta
beta
okay so just uh you know value is
additive across disjoint pieces
that's assumption number one assumption
number two is actually completely
without without loss of generality for
the purposes of this uh lecture
so we're going to assume that evaluation
functions are normalized
in the sense that the value of each
player for the entire cake
is one it's just going to be for ease of
notation and exposition
and finally sorry
our last assumption is divisibility so
this one is slightly more subtle it says
that you can cut the cake
as finely as you want informally okay
when we said that we're going to talk
about a divisible good this cake
this is where the visibility comes in
you can cut it as finely as you want
more formally what does that mean that
for any lambda that you give me between
0 and 1
i can take an interval i and cut from it
a sub interval i prime such that the value
value
a player as has for i prime is lambda
times the value
i has for the entire interval so for
example here
if the value of player i for this entire
interval is alpha
and you give me some lambda i can cut out
out
a sub interval that is worth lambda
times alpha
okay so i can kind of move a knife and
keep going until i hit exactly the point
where that interval is worth the desired fraction
fraction
of the value of the of the entire interval
interval
okay so again you know like i said this
is slightly more formal what we'll need
uh things i think will be pretty
intuitive but that's kind of the formal
okay so now that we uh kind of define
the setting we can start thinking about
how to allocate the cake and what's a
fair way to do it
so we'll be thinking about allocations
of the cake a1 to a
n where ai is the piece of cake
given to player i and formally a1 to a n
forms a partition of the cake so these
pieces are disjoint
and their union is the entire cake so we
just decide to divide the cake in some way
way
into end pieces and we give each piece
to one of the players
now let's define what we mean by
fairly allocating right so this is the
location we want to think about what a
fairer location is
and really the beauty of fair division
and specifically when we think about k-cutting
k-cutting
the beauty is that we can take pretty
abstract notions of fairness
and capture them in a mathematically
rigorous way as we'll see
so the first notion we'll talk about is proportionality
proportionality
uh so this says that that for every
player i
the value i have for his piece of cake ai
ai
is at least one over n so remember that
the value i has for the entire cake is one
one
and the number of players is n so this
is saying i gets at least his
proportional share if we have n players
i gets a value for his piece
that is just one over n right so that
seems like a very intuitive way of
thinking about fairness
you get at least your proportional share
we're kind of evenly at least evenly
the second notion which i like even
better is called envy freeness
and we'll see this notion plays a big
role in fair division in general
what this says is that for every two
players i and j
the value i have for his piece of kki is
at least the value i has
for jay's piece of cake aj
okay in other words this says no player
i would want to swap his piece
with a piece of cake allocated to any
other player j
okay i like my piece at least as much as
i like the piece allocated
to any other player right and the
intuition here is i don't envy any other player
player
if it was the case that i had higher
value for the piece of cake
allocated to somebody else i would envy
them this says that the allocation is
envy free there is no envy
between the players and this is true for
any two players i and j so no player envies
envies
okay so these are the the formal notions
of fairness that we'll talk about i want
to spend a couple of minutes kind of
digesting these notions
so here's the first poll for today this
poll just thinks about the case where
there are only two players so n equals two
two
and the question is which of the two
properties is stronger they strongly
remain that it implies the other
so uh one would say proportionality
implies envy freeness if an allocation
is proportional
it must also be envy free 2 says that
envy freeness implies proportionality if
an allocation is only free it must be proportional
proportional
3 says that they're equivalent one
implies the other and
four is incomparable neither one implies
proportionality implies that the
freeness and envy freeness implies
proportionality when there are two players
players
so let's think about this uh you know
why does proportionality
sean if the player values his piece like
at most
one half then that means like he values
the other piece at
says that the player values his piece at
least at one half
and therefore he values the other piece
that posted one half
because remember that we assume that the
values of the players for the entire
cake are one
and the valuations are additive so the
value for the two pieces sum up to one
so if you value your piece at least at
one half you value
the other one at most at one half and
therefore you have envy freeness your
value for your piece
is at least as high as your value for
the uh for the other
player's piece what about the other directions
directions
why does envy freeness imply proportionality
proportionality
yeah since we have that there's only two pieces
pieces
if we are if we're and we free them our
piece is more valuable than the other
piece and if there's only two pieces
that makes we have
a similar argument we're saying there
are only two pieces
and you value your piece at least as
much as the other piece
and the two values sum up to one and
that directly means that your value for
your own piece
must be at least one half which is the
definition of proportionality for two players
players
okay so we get that mv frequency implies
proportionality proportionality implies
any freeness for the case of two players
what about the general case so the next
poll is the same thing
but for the case of three players or more
great okay so there's a really nice
majority for envy freeness implies proportionality
proportionality
but not the other way right so now with
three or more players things are a bit different
different
than they were before um there was
actually there was an excellent question
do you have to divide the whole cake and
notice that this is crucial for the
direction of envy freeness implies proportionality
proportionality
because if for example you didn't you
could uh not allocate any of the cake
that would be envy free everybody would
have value zero for every piece
everything is empty but it wouldn't be
proportional so the direction of envy
freeness implies proportionality relies
on dividing the entire cake so what's an
argument for why does envy freeness imply
imply proportionality
um if we assume what's the explanation
of and we doesn't have compliance or functionality
functionality
i mean sorry okay so basically if we have
have
at least less than one over n then we
know that
then we know that we would be envisioned
because there must be another one that's
bigger than one over n given that we
can't divide
they can't all be less than one right exactly
exactly
right so the the key point is exactly
this issue of like they can't
all be less than one over n right so
they're because there are n pieces and
they sum up to one
one of the pieces has to be of value at
least one over n
and envy freeness says that you don't
envy that piece
right you like your piece at least as
much as any other piece
we know that because they sum up to n
there is a piece whose value is one over n
n
and that means that your value for your
own piece has to be at least one over n
which is the definition of
proportionality okay excellent um
so that's why proportionality implies
only freeness the other direction i gave
it away a bit on the slide
so this is a counter example for uh the
location that is proportional but not
envy free so what we have here is
uh the blue player has value one for his piece
piece
the yellow player has value one for his
piece the red player has value one third
for his piece
one half for the blue piece and one over
six for the yellow piece
so this is proportional because every
player has value at least one third
for his own piece but it's not envy free
because the red player
envy is the blue player he would rather
have the blue piece
that is worth one half instead of the pc
is getting that is worth only one third
okay so there was something special
about this case of n equals two
where if proportionality says i have the
majority of value in the cake one half
out of one
which implies nd freeness but for three
players i could already have this
situation where i satisfy proportionality
proportionality
but that gives me only value one-third
there's enough value remaining in the cake
cake
good okay so now that uh things are hopefully
hopefully
somewhat intuitive with respect to what
these fairness notions are
i want to tell you about k-cutting
algorithms so what what are algorithms
for getting
fair divisions of the cake so the one
we'll start
with is an algorithm for the case of two
players just two players
uh it's called icat you choose so here
i'm taking i'm attributing this
algorithm to myself and my brother from
around 1995.
my brother is actually a math professor
at texas a m so we were pretty
mathematically inclined kids
and we came up with this algorithm kind
of independently but i'm sure it was
reinvented many many times over the millennia
millennia
the algorithm is very simple one player
cuts the cake into two pieces that are
identical from his viewpoint
and the other player chooses the piece
that he prefers
right so a bit more formally player one
divides the cake into two pieces
x and y such that the value
player one has for x is one half and the
value it has for y
is one half so two equal pieces and then
player two chooses the piece that he prefers
prefers
so for example here player one divided
the cake into two equal pieces
now player two looks at these pieces and
he's like well i i value the first
two thirds and i value the the second at
one third
uh so i'll pick the top piece and then
the other piece will go to
uh player one now this is obviously nv3
right because player one is indifferent
between the two pieces he doesn't care
which piece he'll get
player two gets to choose the piece that
he prefers so obviously he likes his piece
piece
at least as much as he likes the piece
of the other player
so this is nv3 and like we said for the
case of two players envy freeness also
implies proportionality
but of course it's easy to check
directly that the value of each player
is at least one half so for the case of
two players this is a fantastic solution
at least from the viewpoint of the
properties that we talked about it has
all kinds of shortcomings
but from this viewpoint it is both envy
free and proportional and kind of a very
simple algorithm
very intuitive
okay so now let's tie the discussion
back to time complexity
so what i want to ask is uh what is the
running time
of uh this icot you choose algorithm
um and this question is trickier than it
seems at first glance
because remember that we we talked and
we stressed the fact that running time
depends on the size of the input
but what is the input here every player
has this valuation function vi
and we made some assumptions about them
they're additive they're divisible and
so on
but their representation you know they
could be represented by
uh you know as the integrals of uh continuous
continuous
density functions or whatever like the
representation can be very large and it
can be continuous
so talking about the running time as a
function of the size
of these valuation functions doesn't
make sense
and we need a different way in order to
think about running time in this setting
okay something that will avoid this difficulty
difficulty
of these valuation functions being
possibly very
complicated objects that have a very
large representation
okay because we still want to say very
concretely this algorithm that we just
talked about
is very simple has very low running time
despite this uh
complication so what we'll do is we'll
adopt a model
due to robertson and webb from a book
that they wrote in 98
this model is what people call the call
a concrete complexity model
so what it does is it defines the
operations an algorithm is allowed to do
and then we're going to talk about
running time in terms of these operations
operations
that we allow the algorithm to do okay
so here's how it's defined
the input size is the number of players
in so when we talk about running time
we'll only talk about it as a function
and the algorithm is allowed to uh to
make two types of operations
both very intuitive the first operation
is an eval
sub i xy operation which asks player i
to evaluate the interval between point x
and point y
so just ask player i what's your value
for this interval between x and y
so in this example uh you know if we add if
if
this is the interval x y and we asked a player
player
and a val query it would output the
value of the player for this interval
which is alpha in this example
okay so i ask the player what's your
value for x y answer
alpha the second query is the cut
sub i x alpha query that asks the player
intuitively to cut an interval starting
from the point y
and so i started starting from point x
such that the interval is worth
alpha to the player so for example
if i ask the player cut from the point x
with value alpha it will return the
point y
as the answer to the query because the
interval between x and y is worth alpha
so you can think of it as kind of moving
a knife over the cake
starting from x until the interval
between x and the knife
is worth alpha and then we return that point
point
okay what would you return if you cannot
satisfy alpha yeah so if it's not
i mean there's also like the flip side
of this question is what happens if
there are many points where this is true
if the
uh if the density of a player is zero
over some part of the cake
so just return the first point where
this is true so we can kind of
deal with these corner cases in an
intuitive way sean
uh if we can satisfy cutting one pass
can we like move to the other end of the cake
cake
uh you may like cut from the right side
to the left yeah so
oh i see um i mean you could i don't
think it would give you more power because
because
like you could um you know you could
just evaluate what's the value from a
point up to the end of the cake
and then you know just remove that value
and cut from the beginning of the cake
so you know you could add these
additional operations uh asymptotically
they won't give you additional power so
you can kind of convert between these
okay uh good so
you know i want to again emphasize this
concrete complexity model is a great idea
idea
uh because you know it's one of those
things where it's not intuitive how we
would think about running time
uh with this complication of very
complicated valuation functions
this gives us a very intuitive way of
reasoning about running times i really think
think
this is kind of the right way of
thinking about time complexity
4k cutting and with that in mind
let's revisit the case of envy free
allocations for two players
and the question is how many operations
in the robertson web model these
valid cut operations would we need in
order to find an
envy free location in other words the
question is how many operations do you
need in order to simulate
the i-cut you choose algorithm
and this is especially cool because i
think i've often seen the answer 3 being
pretty popular
because 2 is kind of a more efficient
way of doing it then you know there's an
additional trick so how do you how do
you do this with only two operations
in the robertson web model yeah [Music]
[Music]
excellent what's your name leonard so they're
they're
saying you know we only need two
operations as follows the first operation
the first operation we'll ask player one
to cut a value of one half so we have
the operation
cut player one from the point zero
and i want the value one half okay
that's operation number one
and this returns some point y and then
operation number two will just
ask player two uh if l to player two
of the interval zero y now the crucial
point where
is this is only the only evaluation we
need because if this is smaller than one half
half
then we will give player two the other
piece the one between y and
one if it's greater equal to one half we
give player two the piece zero y
and we give the other piece to player
one okay so because the values add up to
one by asking one evaluation query
we also know the value for the other
piece and we can
let player two choose based on this one query
query
so we just did two queries in the
robertson web model
okay so let's spice things up and talk
about the case of more than two players
right so far we talked about two players we
we
talked about i cut you choose we talked
about you know complexity
robertson web now let's think about the
case of more than two players
which as we saw before is kind of
fundamentally different from the case of
two players
and what i want to show you next is an
algorithm that achieves a proportional allocation
allocation
not envy free but i want to achieve a
and in particular this algorithm will
also show the existence of a
proportional location it's not even
clear that one exists
so the fact that this algorithm works
will in particular prove the existence
of a proportional allocation
so the way the algorithm works is as
follows we have a referee
that continuously moves the life over
the cake
when the piece of cake to the left of
the knife is worth one over m to some player
player
that player shall stop we at that point
we make a cut
we remove the piece to the left of the
knife and we give it to the player who
shouted stop
and then we keep going from the point
where we made the cut
and the remaining players so the player
will shout at stop he is happy we remove him
him
and we keep going from the point where
we made the cut with the remaining
players again
we move the knife some players shout
stop we cut remove the piece and so on
so let me show you what this looks like
this slide is actually one of my
proudest powerpoint creations ever
so it's going to be an example with
three players
and uh let's see how it works so the
referee starts continuously moving the
knife over the cake
until the player shall stop the referee
makes the cut in the cake
and the player shouted stop is the
and we remove this piece and give it to
this yellow player
shouted stop and now again we continue
from the point where we made the cut
with the remaining two players
we continuously move the knife until the
player should stop
now it's getting old we make the cuts
and we remove the piece give it to the
player who shouted stock
now i want to argue informally that this
is a proportional location
so the two players will shout at stop
get at least get exactly their
proportional value which is one-third
what about the red player the one who
didn't shout stop at any point or maybe
shout it stop at the exact same time as
as one of the players before
so uh the red player's value for each of
the pieces that was allocated
is at most one-third right because they
didn't shout or shout it at the same time
time
and the values add up to one and this
means that his value for the remaining piece
piece
is at least one-third okay so that's the
intuition for why this
is proportional now notice that it may
not be envy free
because for example it could be the case
that the yellow player has value
two-thirds for the blue piece as far as
we know
the only thing we know is that the
yellow player has value one-third for
his piece
we don't know what his value is for the
other pieces it could be higher than
one-third so this would not generally be
envy free
but it will be proportional so let's do
the proportionality proof
slightly more formally even though the
whole idea was in what i just said
so at every step the allocated piece of cake
cake
is worth at most one over n to the
remaining players so this means that
after k steps
how much is the remaining cake worth to
the remaining players that weren't
allocated yet
you know we allocated k p says each
worth at most one over n
so the remaining cake is worth at least
one minus
k divided by n we removed kp so it's
worth one over n
um so this means two things
first of all you know we have to make
sure that in each step there
actually is a player that will shout
stop but because at every step all of
the players have value
at least one over n remaining some
player will eventually shout stop and
we'll allocate another piece
the the most the most subtle point is
the last player which is what we said before
before
so for the last player we remove the n
minus one pieces
each worth at most one over n and
therefore the value of the last player
for the last piece
is at least one minus n minus one over n
which is one over n okay so that's you
know the only thing that's going on here
is when you remove a piece
it's worth at most one over n to the
remaining players they have enough value
remaining and even the last player
will have enough value in the last piece
of cake
so really nice and simple argument
good so so this is great we have
yeah um so this is proportionality
argument depends on the fact that
um if you give a player
the king interval x to y or if you give
the player
the interval x plus a into y plus a that
they value them the same
this is not true so right so the
question was is it true that
does this depend on like the interval x
to y
being value the same as x plus a up to y
plus a
in general it's not true so you could
have uh the entire
your entire value could be focused on
the interval zero one half
if you shift it you know for example if
you shifted it by one half
you would end up in a part of the k that
has no value to you so in general we're
definitely not making that assumption
and this value this argument doesn't uh
depend on this
in every in any way um right because all
we're saying is when you shouted
you had value one over n we don't care
about your value for like the the
following intervals
uh right because we don't care about
proportionality
okay uh so the question i want to ask is
is what is the complexity
of the dozen spaniard protocol by the
way this dates back to around 1960 and
these two people dublins and spaniard
the question is what is the complexity
of this protocol
in this model that we talked about with
the valence cad queries
now i mean this is weird right because
it's not clear that this
protocol even works in that model we
have this continuously moving knife
how do we think about it in the context
of cut and eval queries
which are very discreet like this
robertson web model is a discrete model
here we have this continuously moving knife
knife
uh so it turns out that the moving knife
is not really needed
so we can capture the exact same idea
using a discrete protocol
this discrete protocol would work as
follows at every step
every player makes a mark at his one
over n point
so the point such that the the interval
from the left part of the cake
until that point is worth one over n the
player who made the leftmost mark
is the one who would have shouted stop
if we continuously move the knife over
the cake
so we can just cut the cake at that
point give it to this player
so in our example it looks like this
initially we ask each player
a cut query from the point zero with
value one-third
and they make marks at these points
right so they return these three points
the yellow player made the left most
mark so he he is the one who would have
shouted stop
we cut at that point we removed the
piece give it to the player
now we ask the remaining two players to make
make
to make a cut from the point
from this point again with value one third
third
they make two new marks in the cake the
the leftmost one was made by the blue
player so we cut at that point we give
it to the blue player and we give the
last piece
to the red player okay so what we've
done is we've simulated this continuous
moving knife protocol
using a discrete protocol that has the
exact same idea and does the same thing
and obviously this is also proportional
for the exact same reason as before
but my question to you is okay so what
is the complexity of this protocol
in the robertson web model
okay so the right answer is order of n
squared theta of n squared
um that was yeah
we don't actually need any evaluations
right because we're just making cuts
okay so we're saying like we'll make n
cuts one per player
uh at the start we'll have to
run it end times to see where each of
them would fall
excellent and then minus one perfectly
what's your name
michael michael that's so michael's
saying uh you know at the first step
uh we will have n cut queries right
because we're asking each player to cut
from the point zero
value one one over n and the second step
we'll have n
minus one cut queries because we've
we've gotten rid of a player
we asked the cat query of the remaining
players and the third step we'll have n
minus two n minus three up to two at the
uh the last step that we actually need
to cut anything
and the and the sum of these things is
roughly n squared over two its order of
n squared
okay so we're just using cut squares and overall
overall
if we sum over all of the steps we get
roughly n squared over 2 which is set of
n squared
excellent so uh
good so this is nice right so
what we know at this point is we have
this like very intuitive protocol
it's proportional which in particular
tells us a proportional location exists
and it's complexity in the robertson web
model is quadratic which is
kind of reasonable but still it's very
interesting to ask can we do better
is there a more efficient protocol for
finding a proportional location in the
robertson web model
and we'll see the answer is yes uh and
it's a protocol due to evan and paz
from 1984 and i think it's a very
elegant protocol it's a divide and conquer
conquer
kind of idea and will give us the
desired result i think in a very elegant
and clever way so how does this protocol work
work
given an interval this is a recursive
protocol which is always more confusing
when it's given an interval xy the first
thing is we're always going to assume
that the number of players
is the power of two uh this assumption
it's not hard to get rid of it in fact
in one of the years we had the homework problem
problem
uh asking to get rid of this assumption
maybe we'll give it again
um it's kind of a nice problem but
for the sake of for ease of exposition
this proof let's assume
that the uh the number of players is um
a power of two so we'll always be able
to divide
the players into two equal sized subsets
now if we have so again recursive
protocol if we call it with only one player
player
we just give the entire piece of cake
that we call the protocol on
uh to this one player okay so the input
of the protocol will be
a set of players a piece of cake if
there's only one player give the cake to
that player
otherwise every player is going to make
a mark in the cake
in the point where the value of the
player for the piece
up to that mark we're actually just
talking about intervals so i can say
the interval up to that mark is going to
be worth half of their value for the
entire interval
right so we call the procedure on the
interval x y i want to make a mark at
the point where
the sub interval will be worth one half
to me kind of like cotton shoes
now let's denote by z star the n over
two mark
from the left okay so remember we have
an even number of players so n number
two is fine
and uh what we'll do is now we're going
to call
the procedure on the interval between x
and z star together with the n over two
players that made
the left and over two marks up to this star
star
and including this star and we'll uh
also call the procedure on the interval
between this star
and the right side of the interval y
with the remaining players the the
players who made marks to the right
of this star okay so let's
see an example this is super confusing
okay so initially we call the procedure
with the entire cake
and four players in this example power
of two
and uh we ask each one of them to make a mark
mark
we ask them a cut query at the point one half
half
so they each make a mark at the point
one half now we ask
what's the four over two mark from the
left which is
what's the second mark from the left
that's the mark made by the blue player
so now we're going to call the procedure twice
twice
once on the left side of the cake up to
this blue mark
and the players who made the left two
marks which are the red player and the
blue player
and we'll call the procedure again on
the right side of the cake between the
blue mark and the right end
with the players who made the right two
marks which are the green player and the
yellow player
okay so now in the call on this on this
sub interval
we ask the blue player and the red
player to make marks at the point that
is worth
to them half of their value for this interval
interval
and we get these two marks and same for
the yellow and the green players we ask
them to make marks at the point
such that the interval between this
point and their mark is worth one half
to them of the right interval
and we get these two marks so now in
this call on the left we ask
what's the two over one right the the
first mark from the left that's the mark
made by
the blue player and in the right we ask
what's the
first mark from the left that's the
green player and now we recurse
so we call the procedure on this sub
interval and the blue only the blue player
player
this sub interval and only the red
player so these are the two recursive
calls from the call on the left
and the two records of calls from the
call on the right would go
with this sub interval in the green
player and this sub interval in the
yellow player
at this point every recursive call has
only one player and the protocol said if
you have only one player just give the
interval to that player
so we just allocate the intervals to
these players
now let's think informally about why
this is proportional
so for example think about the red player
player
okay so the red player
we know that his value for this
sub-interval is one-half
in particular his value for this entire
sub-interval which is bigger than the
interval that he marked at the first stage
stage
is at least one-half right
uh so we know that for red the value of
this is at least one half
and now uh we gave him right and we
asked him to make a mark at
the place where this piece is worth one
half to m of the value of this interval
now he got he ended up getting this piece
piece
which includes this piece
as a sub interval now notice that this
piece is worth to the red player at
least one half of all of this
which is worth at least one half right
so that means that the pc ended up getting
getting
is worth at least one quarter which is
the proportionality guarantee
right similarly if you think about the
green player uh the green player so his
value for
this piece is at least one half
right because even like the piece to the
left of the green mark is worth one half
and then his value for this piece is at
least half of that which is at least one quarter
quarter
and he ends up getting this piece
okay so that's kind of the informal intuition
intuition
let's do this a bit more formally
so at stage 0 every player values the
whole cake at 1.
now at every stage the players will
share a piece when we call
when we make a recursive call to the
protocol we call it on a sub-piece
in a subset of the players all of the
players in the skull
value the piece that they're sharing now
at least at half of their value for the
previous piece
okay because again you know if we we
said for the play we made a mark at the
one half point of some player
all of the players who made marks to the
left of that point value this piece at
least at one half
all of the players who made marks to the
right of that point
value the other piece at least at one half
half
so everybody values their piece at least
at one half as the previous piece
that means that after k steps after k
recursive calls
every remaining player values the piece
that they're sharing at at least one
over two to the k
of the value of the entire cake right
which is one
however the number of steps is login
because at every step we're having the
number of players
and the number of times that the number
steps it takes you to have the number of
players to reach only a single player
is exactly log n when n is the power of two
so you know so at the end after k steps
after log n steps
we get that the value of a player for
the remaining piece that is getting
is at least one over two to the log n
okay excellent
okay so so this tells us that this
divide and choose type protocol
is proportional let's analyze its
running time in the robertson web model
so this is a recursive protocol we need
to solve the recursion it's a very easy recursion
recursion
so the recursion is as follows the uh
value for uh if you have only so this is
a function of n
right the the input to this is the
number of players
if you have one player then the running
time is zero you don't need to ask any
queries you just give the piece to that player
player
for the general case of n players you
need to ask and i'm being kind of
generous here so we need to ask two end
queries because we need to ask
each player what's your value for the
current piece
and then we need to ask them please cut
a piece worth half of that value
so we ask each player and an eval query
and the cut query
and therefore we get two n queries
overall and then we recurse on the two
on two halves of the players so we pay
to n
and then we have to pay twice our cost
for n over two players
and okay so how much work do we do overall
overall
in the first step we ask two n queries
and then we recurse on two subsets of
size n over two
on each of these subsets the amount of
work we do is 2
times n over 2 which is n right so
that's again 2n overall
and then we recurse on four subsets of
size uh n over four
on each one of them we do n over two
work i mean in general what's going on
here is every player gets exactly two
queries at every step
so whatever the depth of the recursion
tree we have
two n operations that we're doing overall
overall
okay so we keep going until we get pairs
right pairs of two
on each one of them we have four
operations again this uh sums up to 2n
so we have 2n work at every level of
this recursion tree
and the height of the recursion tree is logan
logan
so overall we get 2n log n work which is
in each step why do we need to call you
bell because i saw
that like uh so the
the way we defined the protocol is the
cut was defined to be
uh the cut was defined to be half of
your value for this interval
uh so you know for some of the players
we don't actually know their value for
example for
like in this example for the blue player
we know that the value is exactly one half
half
but for the red player we don't know
what the value is now a subtle point is
it would have been enough to just
do cut with 1 over 2 to the k you know
we could just save a bit here
but asymptotically it would be the same
so let's just do it this way
so to recap what we showed is there's
this really nice recursive protocol even puzz
puzz
it gives you a proportional location and
the running time is set off and login
which is significantly better than the n
square that we saw before
now you can ask can we do better is this
the best we can do or is there a better protocol
protocol
that maybe only has n operations in the
robertson web model
so now the answer is no there's a really
beautiful paper from
2006 by edmonds and prus
kirk froze is actually a professor at
the university of pittsburgh in the
computer science department
a really cool paper and what they showed
is that any
proportional protocol requires at least
omega of n log n queries
in the robertson web model okay so this
is a really nice proof
uh you know it's um so in my
in my phd level course i actually do it
in one of the lectures it takes an
entire lecture like 80 minutes but it's a
a
really really clever proof and um
what this says in particular is that the
evan pause protocol is provably optimal
it has running time and logan and this
theorem says no protocol can do better
and therefore it is the optimal protocol
for uh
cutting a cake in a proportional way
so that question is completely resolved
the complexity of proportional k-cutting
so let's go back to envy freeness right
we almost forgot about it when we talked
about two players we said
icat you choose is nv3 but then we kind
of forgot about it went to
proportionality the dublin spaniard evan fuzz
fuzz
what about envy freeness so every
fritness is a much more complicated story
story
it's been known for a long time that an
envy free allocation exists
and moreover an nv3 location exists even
with connected pieces
which is a property that we had for um
you know for the double spanner actually
for both protocols that we talked about
you just get an interval
so this is also possible this exists for
envy freeness however uh
it's been incredibly difficult to come
up with k-cutting algorithms that
actually achieve
an nv free allocation so there was a big breakthrough
breakthrough
in 1995
a protocol due to branson taylor that
worked for any number of players
and was um you know was uh
did the job right so it did compute an
mvp location
however subtlety is that it wasn't
bounded as in
a function of the number of players what
does that mean that for
any k that you give me i can come up
with valuation functions for the players
that would make the algorithm make more
than k steps
so i can make the algorithm work as hard
as i want
by configuring the valuation functions
of the players
adversarially right and we said like
what we want is an algorithm that the
running time should be bounded as a
function of the number of players
so that algorithm did not have that property
property
and it was kind of a huge open problem
for a long time is there even
a k-cutting algorithm that is envy free
whose running time is bounded as a
function of the number of players
so this question was resolved in 2016 by
uh harry stazes and simon mckenzie
simon was actually a postdoc here for a
couple of years
until last year and they showed the
answer is yes
they gave an incredibly complicated protocol
protocol
that gives an envy free solution and is
bounded in as a function of the number
of players
but the running time of this protocol is
so the running time is
and to the end to the end to the end to
[Music]
that's a running time it is a function
of the number of players that's bounded
but it's an incredibly large function of
so they're still you know so this
answers formally answers the question is
there a bonded protocol
but of course opens the question is
there a reasonable protocol
for example is there a polynomial time
protocol in the robertson web model
that would uh give you an nv3 allocation
the best known lower bound is
embarrassing it's only n
squared okay so we know that you can do
better than n squared
the one thing that's nice about this is
that it says that there is a separation
between envy freeness and proportionality
proportionality
because we know that proportionality can
be achieved with n log n
we know that and we finish you need at
least n squared but the
the lower bound is n squared the upper
bound is n to the n to the n to the n to
the n to the n
so still a big open problem
okay so i want to spend the last part of
the lecture uh telling you about some
practical applications of fair division
from my very biased viewpoint it's
so the first application i want to talk
about is
a website called split it it's a
not-for-profit website
that we launched in 2014 so it's been
around for roughly five years now
and actually the main person behind this
in terms of like holding it up
uh is a person who was an undergraduate
at the time jonathan goldman
he started working on this in his
sophomore year and he worked on it for
three years it was like an incredibly
uh large and impr i mean he was amazing
like it just did an amazing job on this website
website
um and uh the idea behind the website is
to give provably fair solutions so there
are different applications
and in each one the idea is that the
algorithm would give you a provably fair solution
solution
in the sense that we can explain what
the fairness guarantee is
and we can you know when you get a
solution we can explain to you why it satisfies
satisfies
that rigorous fairness guarantee
so right now there are five applications
on the website for dividing
rent fare like taxi fare or uber fare
credits goods and tasks
so let me just mention a couple of them
to give you an idea of how this connects
to what we talked about
the rendervision application is a pretty
popular application so last time i
looked there were like 60 000 instances
that were solved by splitted
the way it works is a couple of people
want to share an apartment or a house
and there's a you know you have to to do
two things you have to assign the rooms
to the players
and you have to divide the rent between
the players the housemates
by assigning a price to each room
now the assumption here is that each
player has a value for each room
and if you get a room that you value at
x for the price of y
your utility would be x minus y
okay so let's say your value minus the price
price
now uh the goal is to find the fair solution
solution
and the notion of fairness is envy
freeness the same notion that we talked
about for k-cutting
what it means here is that for each
player my utility for my room at my price
price
is at least as high as my utility for
any other room for the price of that room
room
so again intuitively it means no player
wants to swap rooms
with any other player for the price that
we're all paying
so it turns out that there's always an
envy free solution
uh and you can compute it pretty easily
uh you know using a linear program for
those of you who know what that is
uh there are other very interesting
questions about how to choose among
envy free solutions or many individual
solutions so the
solution implemented and split it
chooses a particular and refreshed
solution in a way that is kind of well motivated
motivated
so that's one example another example i
wanted to mention
is this problem of dividing goods or
indivisible goods
so this is something that arises in
cases like you have an inheritance and
maybe there's
a jewelry collection or an art
collection and you want to divide it
between family members
so this is typically a situation where
you don't want people to pay each other
you just want to divide those goods
now a complication that comes up here
is that um envy freeness is not feasible
right because these goods are
indivisible in the sense that you can
only give
one good to each player can split them
up so you know if you think about the
situation where there's one very
valuable good like a diamond and
everybody wants a diamond
if we give it to one player everybody
else would be envious
so envy freeness is not something that
you can probably satisfy here
the notion of fairness that is possible
to prove or be satisfied
is called envy freeness up to one good
which means that
uh it's possible that player i would
envy player j
but it's always possible to eliminate
that envy by removing a single good from
the bundle of player j
okay so there could be envy but the envy
is bounded by a single good
so in some sense that's the most that
you can hope for and that is feasible
and you know the algorithm implemented
split it which is very computationally intense
intense
finds a solution that satisfies this
guarantee in a specific way
that has some other nice properties okay
so that's kind of the high level idea
you know
asking what is a fairness notion that we
can guarantee
in each one of these settings and coming
up with algorithms that would actually
compute solutions
so the other example i want to talk
about briefly is a political redistricting
redistricting
so to give you some context for this uh
in the u.s every 10 years there's a u.s census
census
and then you know there's a new count of
the population in every state
now the way the representatives and the
house of representatives 435 people
are allocated between the different
states depends on the population
which means that every 10 years after
the census you have to recalculate how
many representatives every
state gets and then you have to redraw
the map
that kind of says what are the districts
that should that elect each representative
representative
now there are various rules on how these
districts can be drawn
uh so for example you know federal rules
say that the districts have to have
roughly equal population
but then there's all kinds of other
rules regarding you know that are
usually the state level regarding
compactness you know
the districts have to have a reasonably
nice shape which is usually not really
well defined
there are different things with
community of interest majority minority
districts and so on so there are
different rules
about how to draw these districts
now what's happening today is pretty
messy so in most states the state
legislature decides on the map so
usually the majority party gets to
unilaterally decide on the map when the
governor is from the same party
the governor has to approve it and
what's happening is that in many states
there are
maps that are blatantly partisan that
are engineered to give one party
a blatant advantage in terms of you know
protecting incumbents and getting
as many seats as possible and that's
this is something that's been going on
since the
19th century so it's not a new phenomenon
so uh you know what's been going on
recently is there were several cases
that reached the supreme court the
supreme court actually
declined to make a ruling in validating maps
maps
but a couple of different maps were
invalidated at the state level so for
example in pennsylvania
the supreme court of the state threw out
the map and instructed
the politicians to come up with a new
map that is less
you know biased same thing happened in
north carolina pretty recently like a
month ago
so these maps are being invalidated and
people have to come up with new maps
and the question is how do you come up
with a fair map right so what is you
know what's a fair procedure
for coming up with the map in this
situation so there are you know there's
quite a bit of discussion about this one
proposal is something from
our work so this is work with wes
peggden who's a math professor here at cmu
cmu
and dingley you was a visitor here at
the time
and what we proposed is a protocol that
we call i-cut you freeze
it's directly inspired by icat you
choose okay so here's how it works
i guess the naive interpretation of i
cut you you choose for a state
would be one party cuts the state into
two pieces that they value equally
the others the other party chooses a
piece and then each one of them
districts their piece any way that they want
want
so this uh is a pretty bad idea right
because that means that every party
would kind of gerrymander the hell out of
of
their part of the state so the protocol
works a bit differently although it's
inspired by this idea
the way it works let's think about
pennsylvania it has 18
congressional districts let's say that
the republican party starts
so it starts by dividing the state into
18 districts any way that they want
then they take this map and pass it to
the democratic party
the democratic party chooses one of the districts
districts
drawn by the republican party freezes it
and redraws the other 17 districts any
way that they want
and then they pass the map back to the
republicans the republicans
freeze one of the districts drawn by the
democratic party
and then redraw the other 16 districts
in any way that they want pass it back
freeze we draw the other pass it back
and so on so you keep
uh handing the map back and forth until
all of the districts have been frozen
in this iterative protocol okay so this
is nice because it means no party has
unilateral power
to draw any district if you drew a
district that was really bad the other
party would not freeze it yep
this algorithm lead to incredibly
homogeneous districts because
the the democratic party would
try to freeze an entirely republican
district get it out of the way
yeah actually adversarially this leads
to yeah
so that's a that's a really nice point
so if you think about uh
um i mean in general there's this notion
and gerrymandering called
packing and cracking where you kind of
if your opponent
wins the district you want to pack as
many of their voters into the districts
as possible
and cracking means that you kind of
split the uh the support of your
opponent between two districts in a way
that you win majority in both
so that's something that's relevant for
you know any kind of optimal
redistricting strategy from partisan
viewpoint it's also true for the optimal
strategy for this
algorithm so you are right this is one
shortcoming of this algorithm
uh there are other approaches that we're
working on now that don't suffer from
this problem but you're absolutely right um
um
okay so this would lead to under optimal
strategies for this protocol this would
lead to packing and cracking
um okay so uh anyway so that's how the
protocol works but uh
you know despite some shortcomings like
this one at least there are some nice
properties so for example you can prove
in a in an abstract mathematical model
there's a connection between the total
support of a state in
uh of a party in a state in the number
of districts they win under an optimal strategy
strategy
in this protocol you can also prove some
guarantees about you know your ability
to freeze any particular districts to
your advantage
so this gives some nice mathematical guarantees
guarantees
um okay that's it for today
Click on any text or timestamp to jump to that moment in the video
Share:
Most transcripts ready in under 5 seconds
One-Click Copy125+ LanguagesSearch ContentJump to Timestamps
Paste YouTube URL
Enter any YouTube video link to get the full transcript
Transcript Extraction Form
Most transcripts ready in under 5 seconds
Get Our Chrome Extension
Get transcripts instantly without leaving YouTube. Install our Chrome extension for one-click access to any video's transcript directly on the watch page.
