WEBVTT
0-1:59:36,500 --> 0-1:59:36,580
0-1:59:36,580 --> 0-1:59:38,930
The following content is
provided under a Creative
0-1:59:38,930 --> 0-1:59:40,320
Commons license.
0-1:59:40,320 --> 0-1:59:42,560
Your support will help
MIT OpenCourseWare
0-1:59:42,560 --> 0-1:59:46,650
continue to offer high quality
educational resources for free.
0-1:59:46,650 --> 0-1:59:49,190
To make a donation or to
view additional materials
0-1:59:49,190 --> 0-1:59:53,100
from hundreds of MIT courses,
visit MIT OpenCourseWare
0-1:59:53,100 --> 0-1:59:53,755
at ocw.mit.edu.
0-1:59:53,755 --> 00:00:03,070
00:00:03.070 --> 00:00:04.570
PROFESSOR: So welcome
back to 6.890.
00:00:04.570 --> 00:00:06.740
Today we have the
first of two guest
00:00:06.740 --> 00:00:11.355
lectures by Costis Daskalakis
about PPAD completeness.
00:00:11.355 --> 00:00:12.230
Take it away, Costis.
00:00:12.230 --> 00:00:13.396
CONSTANTINOS DASKALAKIS: OK.
00:00:13.396 --> 00:00:16.800
Thanks for the invitation
to talk about PPAD.
00:00:16.800 --> 00:00:20.910
This is sort of an unusual class
if you haven't seen it before.
00:00:20.910 --> 00:00:23.110
So part of the
lecture is to describe
00:00:23.110 --> 00:00:26.340
the class and the motivation
behind this definition.
00:00:26.340 --> 00:00:31.330
If I start with the definition
itself, it may seem weird.
00:00:31.330 --> 00:00:34.360
So instead, I want to
provide some motivation
00:00:34.360 --> 00:00:35.290
about the definition.
00:00:35.290 --> 00:00:37.290
And then sort of towards
the end of the lecture,
00:00:37.290 --> 00:00:39.170
we're going to see
the definition.
00:00:39.170 --> 00:00:42.880
We're also going to see our
first PPAD complete problem
00:00:42.880 --> 00:00:44.410
in the end of this lecture.
00:00:44.410 --> 00:00:49.800
And the next lecture, I'm
going to describe more natural,
00:00:49.800 --> 00:00:52.721
if you want, problems
about PPAD complete.
00:00:52.721 --> 00:00:53.220
OK.
00:00:53.220 --> 00:00:58.170
So the motivation for
me looking at this class
00:00:58.170 --> 00:01:05.060
is some beautiful theorems
in game theory, economics,
00:01:05.060 --> 00:01:10.220
and topology, namely Nash's
theorem, Brouwer's theorem,
00:01:10.220 --> 00:01:12.700
and Sperner's theorem.
00:01:12.700 --> 00:01:15.170
And I want to describe
those theorems
00:01:15.170 --> 00:01:17.380
before I get into the
computational complexity
00:01:17.380 --> 00:01:19.870
of the resulting problems.
00:01:19.870 --> 00:01:22.130
So let me start
with Nash's theorem.
00:01:22.130 --> 00:01:26.460
So this table represents a
game between two players.
00:01:26.460 --> 00:01:28.170
The rows correspond
to the strategies
00:01:28.170 --> 00:01:30.080
available to the blue player.
00:01:30.080 --> 00:01:32.360
And the columns correspond
to the strategies
00:01:32.360 --> 00:01:34.250
available to the column player.
00:01:34.250 --> 00:01:38.770
And then every box in this
table writes down the playoffs
00:01:38.770 --> 00:01:41.680
that the two players
get if they chose
00:01:41.680 --> 00:01:42.890
the corresponding strategies.
00:01:42.890 --> 00:01:45.720
In particular-- so this
is a penalty shot game.
00:01:45.720 --> 00:01:51.090
If the goalie dives left,
and the kicker shoots right,
00:01:51.090 --> 00:01:53.706
then the goalie loses a point.
00:01:53.706 --> 00:01:57.360
The kicker gets a point.
00:01:57.360 --> 00:02:01.650
More generally, in
a game, you have
00:02:01.650 --> 00:02:05.550
to specify the players n,
the number of players n,
00:02:05.550 --> 00:02:07.860
the set of players n.
00:02:07.860 --> 00:02:11.410
Then for every
player p, you have
00:02:11.410 --> 00:02:16.200
to specify the set of strategies
available to this player.
00:02:16.200 --> 00:02:18.230
And also for every
player p, you have
00:02:18.230 --> 00:02:24.280
to describe a payoff function
Up that maps the strategies
00:02:24.280 --> 00:02:28.520
of everybody to the reals.
00:02:28.520 --> 00:02:31.180
00:02:31.180 --> 00:02:40.870
So in particular, so Up of
a collection of strategies
00:02:40.870 --> 00:02:44.210
for all the players
corresponds to the payoff
00:02:44.210 --> 00:02:46.640
that player p gets if
the players chooses
00:02:46.640 --> 00:02:50.140
these strategies from
the corresponding sets.
00:02:50.140 --> 00:02:52.010
That's a general
definition of a game.
00:02:52.010 --> 00:02:54.520
But in that picture, I
have a two player game
00:02:54.520 --> 00:02:57.970
with two strategies per
player for simplicity.
00:02:57.970 --> 00:03:05.180
Now what game theory
studies and tries to predict
00:03:05.180 --> 00:03:11.660
is what happens when two
players interact in the way
00:03:11.660 --> 00:03:14.680
described by a payoff
table and have developed
00:03:14.680 --> 00:03:16.820
various notions of
equilibrium that
00:03:16.820 --> 00:03:19.910
may arise as a result
of this interaction.
00:03:19.910 --> 00:03:23.620
The one that is of particular
interest to us in this lecture
00:03:23.620 --> 00:03:26.550
is what is called the
Nash equilibrium, which
00:03:26.550 --> 00:03:29.130
is a pair of randomized
strategies for the two
00:03:29.130 --> 00:03:32.280
players of the game
such that none of them
00:03:32.280 --> 00:03:35.590
has incentive to change
their strategy given
00:03:35.590 --> 00:03:38.430
the strategy of
the other player.
00:03:38.430 --> 00:03:42.950
In this particular example,
the Nash equilibrium,
00:03:42.950 --> 00:03:44.500
which is actually
the unique one--
00:03:44.500 --> 00:03:46.860
a Nash equilibrium which is
the unique one of this game
00:03:46.860 --> 00:03:50.900
is for both players to
uniformly randomly play each
00:03:50.900 --> 00:03:53.180
of their available strategies.
00:03:53.180 --> 00:03:58.110
And it's quite easy to check
that this is a Nash equilibrium
00:03:58.110 --> 00:04:04.640
because given-- so for from
the kicker's perspective, given
00:04:04.640 --> 00:04:09.700
that the goalie uniformly
randomly dives left or right,
00:04:09.700 --> 00:04:12.870
the expected payoff from
shooting left or right
00:04:12.870 --> 00:04:14.730
is exactly 0.
00:04:14.730 --> 00:04:16.550
So in particular, any
complex combination
00:04:16.550 --> 00:04:19.820
of these two strategies
has an expected pay of 0.
00:04:19.820 --> 00:04:22.710
And he cannot improve it by
changing the mixing weights
00:04:22.710 --> 00:04:23.880
in any way.
00:04:23.880 --> 00:04:26.540
So given what the
goalie is doing,
00:04:26.540 --> 00:04:31.360
it's in the best interest of
the kicker to play half, half.
00:04:31.360 --> 00:04:33.170
And vice versa.
00:04:33.170 --> 00:04:36.400
You can do the same calculation
from the goalie's perspective.
00:04:36.400 --> 00:04:39.290
And given what the
kicker is doing,
00:04:39.290 --> 00:04:43.010
the goalie cannot improve
his expected payoff.
00:04:43.010 --> 00:04:48.150
So more generally,
in the general case,
00:04:48.150 --> 00:04:57.000
every player chooses
a randomized strategy.
00:04:57.000 --> 00:05:01.040
A randomized strategy is a
distribution over the strategy
00:05:01.040 --> 00:05:02.040
set of the players.
00:05:02.040 --> 00:05:05.820
So it's going to be--
with this symbol,
00:05:05.820 --> 00:05:09.290
I represent the collection of
distributions over the set.
00:05:09.290 --> 00:05:12.530
00:05:12.530 --> 00:05:18.370
And I can extend this
function to distributions.
00:05:18.370 --> 00:05:21.905
So let's call this the
extension of that function
00:05:21.905 --> 00:05:23.400
to distributions.
00:05:23.400 --> 00:05:27.860
When I get as input a collection
of mixed strategies, what
00:05:27.860 --> 00:05:30.450
I'm going to do is I'm going
to look at the expectation
00:05:30.450 --> 00:05:36.070
where every-- according to
these strategies, this s1
00:05:36.070 --> 00:05:41.370
drawn from x1, s2 drawn from
x2 and so on and so forth,
00:05:41.370 --> 00:05:43.390
sn drawn from xn.
00:05:43.390 --> 00:05:46.660
I'm going to look at
the expected utility
00:05:46.660 --> 00:05:49.530
under strategies, actions
that are chosen according
00:05:49.530 --> 00:05:51.080
to this randomization.
00:05:51.080 --> 00:05:55.100
So that's the expected
utility of player p
00:05:55.100 --> 00:05:58.520
if players choose
these mixed strategies.
00:05:58.520 --> 00:06:10.040
And Nash equilibrium in general
has a definition, a collection,
00:06:10.040 --> 00:06:15.610
x1, x2, et cetera,
of mixed strategies
00:06:15.610 --> 00:06:21.900
is a Nash equilibrium
if and only
00:06:21.900 --> 00:06:31.930
if for every player p, the
expected utility that p gets
00:06:31.930 --> 00:06:38.700
by playing this strategy is at
least as good as the expected
00:06:38.700 --> 00:06:47.100
utility he would get if he
switched to something else
00:06:47.100 --> 00:06:50.030
for any other mixed strategy
he could possibly play.
00:06:50.030 --> 00:06:54.280
00:06:54.280 --> 00:06:54.910
OK?
00:06:54.910 --> 00:06:59.570
So if none of the other players
change their strategies,
00:06:59.570 --> 00:07:02.880
there's no alternative
mixed strategy
00:07:02.880 --> 00:07:07.540
for this player that
may improve his payoff.
00:07:07.540 --> 00:07:10.950
So if that's simultaneously
true for all players,
00:07:10.950 --> 00:07:14.710
then that collection is
called the Nash equilibrium.
00:07:14.710 --> 00:07:16.920
And that example is
just a special case
00:07:16.920 --> 00:07:18.980
of this definition.
00:07:18.980 --> 00:07:22.822
Any questions about what
a Nash equilibrium is?
00:07:22.822 --> 00:07:24.600
OK.
00:07:24.600 --> 00:07:28.040
Now there are games
and games, right?
00:07:28.040 --> 00:07:30.210
And this game is a
particularly simple one.
00:07:30.210 --> 00:07:32.940
First of all, it has two
players and two strategies.
00:07:32.940 --> 00:07:34.930
But also it's very
symmetric in some sense.
00:07:34.930 --> 00:07:38.710
00:07:38.710 --> 00:07:40.770
If I look at every
square of this table,
00:07:40.770 --> 00:07:44.860
the sum of payoffs
in each square is 0.
00:07:44.860 --> 00:07:47.920
These types of games are called
two player zero-sum games.
00:07:47.920 --> 00:07:52.880
And the existence of
equilibrium in these games
00:07:52.880 --> 00:07:54.200
was shown by von Neumann.
00:07:54.200 --> 00:07:57.560
So von Neumann showed that
any two players zero-sum game
00:07:57.560 --> 00:08:01.110
has such an equilibrium.
00:08:01.110 --> 00:08:05.962
I mean, a priori, it's not
clear if in a given game
00:08:05.962 --> 00:08:07.420
there is a collection
of strategies
00:08:07.420 --> 00:08:09.830
that are a Nash equilibrium.
00:08:09.830 --> 00:08:12.240
The first one to
establish such a result
00:08:12.240 --> 00:08:16.169
was von Neumann in the '20s, who
showed that if a game has two
00:08:16.169 --> 00:08:17.730
players, and it's
a zero-sum game,
00:08:17.730 --> 00:08:21.590
then there is always an
equilibrium in that game.
00:08:21.590 --> 00:08:24.780
By the way, the equilibrium
wasn't called Nash equilibrium
00:08:24.780 --> 00:08:26.660
at the time, because
Nash wasn't around.
00:08:26.660 --> 00:08:32.500
It is known as the
minmax equilibrium.
00:08:32.500 --> 00:08:36.150
And in fact, later on when
Dantzig was developing
00:08:36.150 --> 00:08:40.120
linear programming duality
together with von Neumann,
00:08:40.120 --> 00:08:44.470
they realized that this
theorem is actually implied
00:08:44.470 --> 00:08:47.530
by the strong LP duality.
00:08:47.530 --> 00:08:49.820
They also noticed that
using linear programming,
00:08:49.820 --> 00:08:54.150
you can compute equilibria
in these types of games.
00:08:54.150 --> 00:08:58.210
In fact now-- but that
took many years more.
00:08:58.210 --> 00:09:00.730
We know that this statement
and strong LP duality
00:09:00.730 --> 00:09:03.720
are actually equivalent
mathematical statements.
00:09:03.720 --> 00:09:04.220
OK.
00:09:04.220 --> 00:09:07.020
So the existence of equilibrium
in two player zero-sum games
00:09:07.020 --> 00:09:10.530
is equivalent to linear
programming duality.
00:09:10.530 --> 00:09:11.750
All right?
00:09:11.750 --> 00:09:13.080
But how about general games?
00:09:13.080 --> 00:09:16.060
What happens if I go to
this table, and I change it?
00:09:16.060 --> 00:09:19.080
Or I consider a game with
more than two players?
00:09:19.080 --> 00:09:22.620
So what happens, for example, if
I change this game in this way?
00:09:22.620 --> 00:09:26.640
Now I gave a big
advantage to the goalie
00:09:26.640 --> 00:09:33.590
in the left, left
choice of strategies.
00:09:33.590 --> 00:09:38.950
Now before Nash was
around, it was unclear
00:09:38.950 --> 00:09:43.840
if a general game has
a Nash equilibrium.
00:09:43.840 --> 00:09:47.960
This is what Nash established
in his celebrated paper.
00:09:47.960 --> 00:09:50.910
Nash showed that any
game, any finite game
00:09:50.910 --> 00:09:53.190
has a mixed Nash equilibrium.
00:09:53.190 --> 00:09:55.290
So a Nash equilibrium
and equilibrium
00:09:55.290 --> 00:09:57.660
in randomized strategies.
00:09:57.660 --> 00:10:00.130
Unfortunately,
what is not known--
00:10:00.130 --> 00:10:04.300
in this particular example,
this is the Nash equilibrium.
00:10:04.300 --> 00:10:06.810
You can verify that this is
actually a Nash equilibrium,
00:10:06.810 --> 00:10:08.210
what I'm showing there.
00:10:08.210 --> 00:10:12.055
But the point of the
slide is that there
00:10:12.055 --> 00:10:14.560
is a qualitative difference
when you go from two players
00:10:14.560 --> 00:10:17.340
zero-sum games to general games.
00:10:17.340 --> 00:10:20.930
In 60 or so years of work
after Nash's theorem,
00:10:20.930 --> 00:10:24.210
we have no proof
using LP duality.
00:10:24.210 --> 00:10:26.610
And we have no polynomial
time algorithms
00:10:26.610 --> 00:10:30.370
for finding equilibria
in general games.
00:10:30.370 --> 00:10:32.720
So part of this
lecture is to try
00:10:32.720 --> 00:10:37.490
to understand the computational
complexity of this problem.
00:10:37.490 --> 00:10:42.230
Given a game, how hard is it
to find a Nash equilibrium?
00:10:42.230 --> 00:10:42.750
OK.
00:10:42.750 --> 00:10:46.750
So that's problem number
one that I want to consider.
00:10:46.750 --> 00:10:47.270
Question?
00:10:47.270 --> 00:10:51.546
AUDIENCE: So the thing that
Nash proved, every game
00:10:51.546 --> 00:10:54.879
refers to any number
of players and--
00:10:54.879 --> 00:10:56.170
CONSTANTINOS DASKALAKIS: Right.
00:10:56.170 --> 00:11:02.990
Any finite number of
players, any strategy set,
00:11:02.990 --> 00:11:04.970
any utility functions.
00:11:04.970 --> 00:11:06.470
No matter how it
looks like, there's
00:11:06.470 --> 00:11:07.832
always a Nash equilibrium.
00:11:07.832 --> 00:11:10.430
00:11:10.430 --> 00:11:12.350
OK?
00:11:12.350 --> 00:11:13.420
Other questions?
00:11:13.420 --> 00:11:17.310
This is, let's say, the actor
number one in this lecture.
00:11:17.310 --> 00:11:20.270
00:11:20.270 --> 00:11:23.380
So the second actor
is Brouwer's theorem,
00:11:23.380 --> 00:11:26.590
which I want to illustrate
in the next few slides.
00:11:26.590 --> 00:11:28.780
The statement of the
theorem is very simple.
00:11:28.780 --> 00:11:31.690
It says that given
a function that
00:11:31.690 --> 00:11:36.525
maps a convex and compact
subset of the Euclidean space
00:11:36.525 --> 00:11:41.390
to itself-- so I don't know.
00:11:41.390 --> 00:11:44.150
In this setting, compact means
basically closed and bounded.
00:11:44.150 --> 00:11:46.690
So if you have a function
that maps a convex,
00:11:46.690 --> 00:11:50.175
closed, and bounded subset
of Euclidean space to itself,
00:11:50.175 --> 00:11:53.310
it must have a
point that doesn't
00:11:53.310 --> 00:11:54.940
move under the function.
00:11:54.940 --> 00:11:58.016
00:11:58.016 --> 00:12:01.760
And I want to illustrate this
with a couple of examples.
00:12:01.760 --> 00:12:03.650
And for my examples,
I'm going to choose
00:12:03.650 --> 00:12:09.025
for D the disk, the unit disk.
00:12:09.025 --> 00:12:13.290
00:12:13.290 --> 00:12:17.156
I'm going to note that all
conditions are needed actually
00:12:17.156 --> 00:12:18.280
for the theorem to be true.
00:12:18.280 --> 00:12:25.850
If you remove any of these
things, closeness, convexity,
00:12:25.850 --> 00:12:29.275
or bondedness,
the theorem fails.
00:12:29.275 --> 00:12:30.900
So I'm going to do
a bunch of examples,
00:12:30.900 --> 00:12:33.080
and you can think about
what may happen if you
00:12:33.080 --> 00:12:35.680
remove one of these conditions.
00:12:35.680 --> 00:12:38.470
So my first example is
to map the disk to itself
00:12:38.470 --> 00:12:41.740
by just rotating the disk.
00:12:41.740 --> 00:12:44.160
Now there is an
obvious fixed point
00:12:44.160 --> 00:12:50.880
in this map, which is the
center, as you may imagine.
00:12:50.880 --> 00:12:53.460
There's actually no
other fixed point.
00:12:53.460 --> 00:12:55.980
What if I take this
disk, and I shrink it,
00:12:55.980 --> 00:12:59.519
and then I shift it
somewhere inside it?
00:12:59.519 --> 00:13:00.060
I don't know.
00:13:00.060 --> 00:13:02.220
Maybe it takes a
little thinking,
00:13:02.220 --> 00:13:05.115
but you should believe
me that there must be
00:13:05.115 --> 00:13:06.610
a fixed point somewhere there.
00:13:06.610 --> 00:13:09.470
00:13:09.470 --> 00:13:18.560
Or a fixed point still exists
if I kind of crumble the disk
00:13:18.560 --> 00:13:20.550
and move it.
00:13:20.550 --> 00:13:23.890
As long as I don't tear it
apart, that's a continuous map.
00:13:23.890 --> 00:13:26.034
And there's still a fixed point.
00:13:26.034 --> 00:13:27.450
And you probably
colloquially have
00:13:27.450 --> 00:13:30.850
heard that if I take
a map of Cambridge,
00:13:30.850 --> 00:13:33.260
and I throw it on
the ground, then
00:13:33.260 --> 00:13:35.240
there is a point on
the map that sits
00:13:35.240 --> 00:13:38.840
on top of the corresponding
point that it represents.
00:13:38.840 --> 00:13:41.290
This is a special
version of this theorem
00:13:41.290 --> 00:13:44.570
because effectively when
I'm throwing a Cambridge
00:13:44.570 --> 00:13:49.050
map to the ground, I define
a mapping from real points
00:13:49.050 --> 00:13:50.670
to points in the map.
00:13:50.670 --> 00:13:54.350
And by this theorem, there
is a point that doesn't move.
00:13:54.350 --> 00:13:55.600
OK?
00:13:55.600 --> 00:13:59.360
So that's what Brouwer's
theorem is saying.
00:13:59.360 --> 00:14:04.410
And the proof of Nash
actually uses this theorem.
00:14:04.410 --> 00:14:06.850
To show that the Nash
equilibrium exists,
00:14:06.850 --> 00:14:09.730
what Nash did is he
used Brouwer's theorem.
00:14:09.730 --> 00:14:12.420
And the next slide, I
want to illustrate the way
00:14:12.420 --> 00:14:18.760
Nash gets to prove the Nash
equilibrium's existence
00:14:18.760 --> 00:14:20.520
by using Brouwer's theorem.
00:14:20.520 --> 00:14:22.950
And I'm going to restrict
myself to the simple game we
00:14:22.950 --> 00:14:25.677
saw in the beginning,
the penalty shot game.
00:14:25.677 --> 00:14:27.260
And as I said, for
this specific game,
00:14:27.260 --> 00:14:28.968
you don't need Brouwer's
theorem to prove
00:14:28.968 --> 00:14:31.400
the existence of equilibrium,
because this is a two player
00:14:31.400 --> 00:14:33.970
zero-sum game, and you can even
do it with linear programming
00:14:33.970 --> 00:14:35.140
duality.
00:14:35.140 --> 00:14:38.570
But it's a simple
enough example that
00:14:38.570 --> 00:14:41.630
will help illustrate the
proof of Nash's theorem.
00:14:41.630 --> 00:14:43.250
So here's what Nash does.
00:14:43.250 --> 00:14:44.870
He starts with a game.
00:14:44.870 --> 00:14:49.740
And then he defines a continuous
function, in this case,
00:14:49.740 --> 00:14:56.100
from the square to itself,
from the unit square to itself
00:14:56.100 --> 00:14:58.400
in a way that the fixed
points of that function
00:14:58.400 --> 00:15:02.720
are actually exactly
Nash equilibria.
00:15:02.720 --> 00:15:05.220
The way the function
looks, where basically,
00:15:05.220 --> 00:15:06.110
what is the square?
00:15:06.110 --> 00:15:10.050
The square represents
the probability--
00:15:10.050 --> 00:15:12.420
the horizontal line is
the probability by which
00:15:12.420 --> 00:15:15.850
the kicker shoots right.
00:15:15.850 --> 00:15:18.150
The vertical axis is
the probability by which
00:15:18.150 --> 00:15:21.370
the goalie dives right.
00:15:21.370 --> 00:15:24.540
And then the
function is basically
00:15:24.540 --> 00:15:27.930
tracking which of
the two players
00:15:27.930 --> 00:15:32.110
has incentive to
change his strategy
00:15:32.110 --> 00:15:34.370
at every point in this quarter.
00:15:34.370 --> 00:15:36.960
So in particular, let's
consider this square over here.
00:15:36.960 --> 00:15:40.360
In this square, both
players play left.
00:15:40.360 --> 00:15:43.270
And the kicker is
actually unhappy.
00:15:43.270 --> 00:15:46.050
If both players play
left, the kicker
00:15:46.050 --> 00:15:47.430
wants to increase
the probability
00:15:47.430 --> 00:15:49.760
by which he is shooting right.
00:15:49.760 --> 00:15:52.490
So this is what this
arrow represents.
00:15:52.490 --> 00:15:55.460
So you want to increase
the probability over here.
00:15:55.460 --> 00:15:59.970
Similarly, if you're here,
they play opposite actions.
00:15:59.970 --> 00:16:04.160
Hence, the goalie wants to
change and so on and so forth.
00:16:04.160 --> 00:16:07.180
What Nash is-- I'm not going
to write down Nash's function,
00:16:07.180 --> 00:16:09.580
but intuitively, this
is what it tracks.
00:16:09.580 --> 00:16:13.720
It tracks at every combination
of mixed strategies,
00:16:13.720 --> 00:16:16.500
which players have
incentive to change
00:16:16.500 --> 00:16:19.860
their actions,
their randomizations
00:16:19.860 --> 00:16:21.030
and in which direction?
00:16:21.030 --> 00:16:24.815
This is what Nash's
function does.
00:16:24.815 --> 00:16:27.540
And in fact, to help
you a little bit,
00:16:27.540 --> 00:16:32.750
I'm going to even
color the unit square,
00:16:32.750 --> 00:16:37.130
depending on the direction
of the deviation.
00:16:37.130 --> 00:16:40.300
So this is the
picture that I get.
00:16:40.300 --> 00:16:43.760
It's very easy to locate
the fixed point as the point
00:16:43.760 --> 00:16:44.890
where all colors meet.
00:16:44.890 --> 00:16:49.050
And this is exactly half,
half, which is exactly
00:16:49.050 --> 00:16:51.290
the Nash equilibrium over here.
00:16:51.290 --> 00:16:55.940
This is a schematic
proof by picture.
00:16:55.940 --> 00:17:00.589
So this is an illustration
of Nash's proof.
00:17:00.589 --> 00:17:03.619
00:17:03.619 --> 00:17:08.002
Any questions about Brouwer's
theorem or the proof?
00:17:08.002 --> 00:17:10.470
OK.
00:17:10.470 --> 00:17:13.845
The last actor-- so the last
actor is Sperner's lemma.
00:17:13.845 --> 00:17:16.790
00:17:16.790 --> 00:17:19.330
It's a lemma in combinatorics,
but it's very related
00:17:19.330 --> 00:17:21.830
to topological statements.
00:17:21.830 --> 00:17:27.160
00:17:27.160 --> 00:17:32.980
So the lemma
considers-- there are
00:17:32.980 --> 00:17:34.680
multiple versions of the lemma.
00:17:34.680 --> 00:17:39.460
And I'm going to show it in
two dimensions on the square.
00:17:39.460 --> 00:17:42.700
There are multi-dimensional
versions of the lemma.
00:17:42.700 --> 00:17:44.940
But I'm going to restrict
myself to the plane.
00:17:44.940 --> 00:17:47.890
And the lemma is going to
start with a triangulation
00:17:47.890 --> 00:17:50.160
of the grid.
00:17:50.160 --> 00:17:52.400
And I'm going to color
this triangulation
00:17:52.400 --> 00:17:54.796
with three colors.
00:17:54.796 --> 00:17:56.420
More generally, if
I'm in n dimensions,
00:17:56.420 --> 00:17:58.760
I'm going to be coloring
things with n plus 1 colors.
00:17:58.760 --> 00:17:59.940
Here I'm in two dimensions.
00:17:59.940 --> 00:18:02.720
I'm coloring with three colors.
00:18:02.720 --> 00:18:06.390
So the way I'm going to color
this square is the following.
00:18:06.390 --> 00:18:10.620
First, I'm obliged to use
this coloring on the boundary.
00:18:10.620 --> 00:18:13.500
Notice that this boundary
has the property that there
00:18:13.500 --> 00:18:14.900
is no red color here.
00:18:14.900 --> 00:18:16.390
There is no blue color here.
00:18:16.390 --> 00:18:23.170
There is no yellow color here
on that edge of the grid.
00:18:23.170 --> 00:18:26.360
But otherwise, I'm allowing you
to color the internal vertices
00:18:26.360 --> 00:18:29.200
in whatever fashion you want.
00:18:29.200 --> 00:18:33.400
All I want is to respect
the boundary coloring.
00:18:33.400 --> 00:18:36.200
So Sperner's lemma
says that no matter how
00:18:36.200 --> 00:18:39.330
you color the inside
of the square,
00:18:39.330 --> 00:18:44.050
there is always a
tri-chromatic triangle.
00:18:44.050 --> 00:18:45.470
In fact, it says something more.
00:18:45.470 --> 00:18:48.480
It says that there is
always an odd number
00:18:48.480 --> 00:18:51.810
of tri-chromatic triangles.
00:18:51.810 --> 00:18:55.664
Can you see one in this picture?
00:18:55.664 --> 00:18:57.180
AUDIENCE: I hope so.
00:18:57.180 --> 00:18:59.263
CONSTANTINOS DASKALAKIS:
You would hope so, right?
00:18:59.263 --> 00:19:01.260
So there are five in this case.
00:19:01.260 --> 00:19:01.978
Here they are.
00:19:01.978 --> 00:19:04.485
00:19:04.485 --> 00:19:06.110
And later in the--
I mean, I'm actually
00:19:06.110 --> 00:19:08.140
going to show the proof
of Sperner's lemma
00:19:08.140 --> 00:19:12.330
because it's instructive for my
purposes later in this lecture.
00:19:12.330 --> 00:19:13.490
It's really remarkable.
00:19:13.490 --> 00:19:16.560
I mean, a priori, I
mean maybe you believe
00:19:16.560 --> 00:19:18.990
there's a tri-chromatic one.
00:19:18.990 --> 00:19:20.250
But it's not at all.
00:19:20.250 --> 00:19:23.850
Obviously, there should
be an odd number.
00:19:23.850 --> 00:19:26.130
And the proof is actually
going to easily give also
00:19:26.130 --> 00:19:30.070
the odd number as well.
00:19:30.070 --> 00:19:31.622
So that's the lemma.
00:19:31.622 --> 00:19:32.580
That's Sperner's lemma.
00:19:32.580 --> 00:19:33.500
Any questions?
00:19:33.500 --> 00:19:35.740
AUDIENCE: Can you repeat
where the legal coloring is?
00:19:35.740 --> 00:19:36.990
CONSTANTINOS DASKALAKIS: Yeah.
00:19:36.990 --> 00:19:40.710
So the legal coloring
says that either
00:19:40.710 --> 00:19:43.010
fix the color to be like this.
00:19:43.010 --> 00:19:48.880
Or more generally, as long
as you don't use red here,
00:19:48.880 --> 00:19:53.195
don't use yellow here, and not
use blue here, you're good.
00:19:53.195 --> 00:19:55.522
AUDIENCE: I don't understand
the general statement.
00:19:55.522 --> 00:19:57.480
CONSTANTINOS DASKALAKIS:
The general definition
00:19:57.480 --> 00:20:00.480
is that-- OK.
00:20:00.480 --> 00:20:04.020
So we have this square.
00:20:04.020 --> 00:20:07.670
There must be-- OK.
00:20:07.670 --> 00:20:09.970
So more general, no
yellow in these vertices.
00:20:09.970 --> 00:20:13.200
00:20:13.200 --> 00:20:18.830
There should be no
blue on these vertices.
00:20:18.830 --> 00:20:27.730
And there should be no red here.
00:20:27.730 --> 00:20:29.880
That's the general statement.
00:20:29.880 --> 00:20:31.440
As long as you
respect that, then
00:20:31.440 --> 00:20:33.885
no matter what you
do inside, there
00:20:33.885 --> 00:20:36.244
is a tri-chromatic triangle.
00:20:36.244 --> 00:20:38.160
Or you could just fix
the coloring to be that.
00:20:38.160 --> 00:20:39.850
It doesn't really matter.
00:20:39.850 --> 00:20:43.430
In fact, if you have
such a coloring,
00:20:43.430 --> 00:20:46.060
respecting these
three properties,
00:20:46.060 --> 00:20:48.660
you can enlarge the
square by adding
00:20:48.660 --> 00:20:53.190
an extra layer that has exactly
the coloring I'm showing here.
00:20:53.190 --> 00:20:57.190
And you can notice that if
your original coloring respects
00:20:57.190 --> 00:21:00.385
these properties, if I
add this specific coloring
00:21:00.385 --> 00:21:03.120
in this extra layer, I'm
not going to be creating
00:21:03.120 --> 00:21:05.090
any triangles in this layer.
00:21:05.090 --> 00:21:07.800
So in fact, I can reduce
one instance to the other.
00:21:07.800 --> 00:21:10.671
00:21:10.671 --> 00:21:11.170
All right.
00:21:11.170 --> 00:21:14.370
So this is the statement
of Sperner's lemma.
00:21:14.370 --> 00:21:17.400
There is a multi-dimensional
version in n dimensions.
00:21:17.400 --> 00:21:18.800
I'm using n plus 1 colors.
00:21:18.800 --> 00:21:20.258
But I'm not going
to state it here.
00:21:20.258 --> 00:21:23.420
00:21:23.420 --> 00:21:26.060
Now again, I'm
going to hand wave
00:21:26.060 --> 00:21:30.050
to actually show you how
Brouwer's theorem is actually
00:21:30.050 --> 00:21:31.770
implied by Sperner's lemma.
00:21:31.770 --> 00:21:34.650
00:21:34.650 --> 00:21:37.110
So in fact, one proof
of Brouwer is actually
00:21:37.110 --> 00:21:39.260
going through Sperner.
00:21:39.260 --> 00:21:41.170
Here's the high level
proof of the argument.
00:21:41.170 --> 00:21:44.160
00:21:44.160 --> 00:21:47.080
Given a function-- I'm going
to do it on the square,
00:21:47.080 --> 00:21:50.810
on the unit square
in two dimensions.
00:21:50.810 --> 00:21:52.640
So suppose I'm given
a continuous function
00:21:52.640 --> 00:21:57.720
from the square to itself,
what I'm going to do
00:21:57.720 --> 00:22:02.480
is I'm going to prove for all
epsilons-- for all epsilons,
00:22:02.480 --> 00:22:05.840
I'm going to show that there
exists an approximate fixed
00:22:05.840 --> 00:22:09.230
point with
approximation epsilon.
00:22:09.230 --> 00:22:10.490
using Sperner's lemma.
00:22:10.490 --> 00:22:13.010
That's what I'm going to
do with Sperner's lemma.
00:22:13.010 --> 00:22:16.020
And then I'm going to use
a compactness argument
00:22:16.020 --> 00:22:17.720
to get this down to 0.
00:22:17.720 --> 00:22:21.775
So I'm going to create in fact
a sequence of approximate fixed
00:22:21.775 --> 00:22:24.550
points with smaller
and smaller epsilons.
00:22:24.550 --> 00:22:27.200
And I'm going to use
compactness-- remember,
00:22:27.200 --> 00:22:30.210
this is a compact set--
to argue that there
00:22:30.210 --> 00:22:32.250
is an exact fixed point.
00:22:32.250 --> 00:22:35.370
So Sperner's lemma can be
used for this first part
00:22:35.370 --> 00:22:36.500
of the proof.
00:22:36.500 --> 00:22:40.050
And roughly speaking, the way
it's used is the following.
00:22:40.050 --> 00:22:44.090
What you do is you first
triangulate the square.
00:22:44.090 --> 00:22:48.530
And the diameter
of your triangles,
00:22:48.530 --> 00:22:52.440
which is very rough in this
picture-- the diameter of this
00:22:52.440 --> 00:22:57.410
will depend on the constant
of absolute continuity
00:22:57.410 --> 00:22:58.420
of your function.
00:22:58.420 --> 00:23:01.900
So if the function is
ellipsis, it's just
00:23:01.900 --> 00:23:05.620
going to depend on epsilon
and the ellipsis constant.
00:23:05.620 --> 00:23:09.320
So depending on the
ellipsisness of the function,
00:23:09.320 --> 00:23:12.910
there's going to be a
finer triangulation.
00:23:12.910 --> 00:23:17.310
Now having
triangulated the square
00:23:17.310 --> 00:23:20.260
and adding this
extra layer outside,
00:23:20.260 --> 00:23:23.130
you're going to color the
vertices that are inside
00:23:23.130 --> 00:23:26.230
depending on the direction
of the displacements
00:23:26.230 --> 00:23:29.170
f of x minus x, using
exactly the same coloring
00:23:29.170 --> 00:23:33.070
schema I showed you earlier
for the illustration of how
00:23:33.070 --> 00:23:39.010
Nash showed the existence
of equilibria using Brouwer.
00:23:39.010 --> 00:23:43.170
So I'm going to color
those internal vertices
00:23:43.170 --> 00:23:48.900
using this coloring scheme,
depending on the directions.
00:23:48.900 --> 00:23:52.380
And then for the extra layer
that I added on the outside,
00:23:52.380 --> 00:23:54.745
I will just use my
standard coloring.
00:23:54.745 --> 00:23:57.280
00:23:57.280 --> 00:24:00.419
Now what's cool with the
way I chose my colors here--
00:24:00.419 --> 00:24:01.960
I mean, this is my
standard coloring,
00:24:01.960 --> 00:24:04.110
except I have permuted
the names of colors.
00:24:04.110 --> 00:24:05.900
Sorry about that.
00:24:05.900 --> 00:24:12.040
I think, you know, red took
the role of blue and stuff
00:24:12.040 --> 00:24:12.540
like that.
00:24:12.540 --> 00:24:15.660
But it doesn't really matter.
00:24:15.660 --> 00:24:17.170
What is cool about
the way I chose
00:24:17.170 --> 00:24:20.510
my colors is that
if a point is here,
00:24:20.510 --> 00:24:31.145
I know that is not going
to be using-- essentially,
00:24:31.145 --> 00:24:33.440
it can only be in the boundary
between red and yellow.
00:24:33.440 --> 00:24:38.790
But if you're here, and
the displacement is yellow,
00:24:38.790 --> 00:24:40.700
you're going to
be going outside.
00:24:40.700 --> 00:24:43.270
That's a bad thing.
00:24:43.270 --> 00:24:45.280
So the way I chose
my colors, I know
00:24:45.280 --> 00:24:50.820
that some property like
this is going to happen.
00:24:50.820 --> 00:24:52.365
Some of the edges
of this cube are
00:24:52.365 --> 00:24:53.990
going to be missing
some of the colors.
00:24:53.990 --> 00:24:56.910
For example, here, there is no
red, because if there were red,
00:24:56.910 --> 00:25:00.800
then I would have to be
going down outside my square.
00:25:00.800 --> 00:25:02.800
And my function is mapping
the square to itself.
00:25:02.800 --> 00:25:04.260
So that can't happen.
00:25:04.260 --> 00:25:11.250
Similarly, over here
I cannot have a yellow
00:25:11.250 --> 00:25:12.710
and so on and so forth.
00:25:12.710 --> 00:25:18.090
So that's going to be a valid
instance of Sperner's lemma.
00:25:18.090 --> 00:25:20.710
And by Sperner, there is
a tri-chromatic triangle
00:25:20.710 --> 00:25:21.445
in this scenario.
00:25:21.445 --> 00:25:23.580
Here it is.
00:25:23.580 --> 00:25:27.790
You could see the fixed
point at the back.
00:25:27.790 --> 00:25:29.790
That's a coincidence
actually because I'm going
00:25:29.790 --> 00:25:31.040
to do the compactness after.
00:25:31.040 --> 00:25:35.430
But I'm going to
do Sperner's lemma.
00:25:35.430 --> 00:25:37.110
Now a tri-chromatic
triangle is actually
00:25:37.110 --> 00:25:40.790
going to-- one of the corners of
the tri-chromatic triangle will
00:25:40.790 --> 00:25:44.210
have this property if you choose
the diameter of your triangles
00:25:44.210 --> 00:25:48.230
to be-- it's correctly chosen.
00:25:48.230 --> 00:25:52.090
So that's, roughly speaking,
how the proof works.
00:25:52.090 --> 00:25:52.890
Yeah?
00:25:52.890 --> 00:25:54.950
AUDIENCE: The fact that
Sperner's lemma shows
00:25:54.950 --> 00:25:57.610
that there's an odd
number of such triangles
00:25:57.610 --> 00:26:01.809
means there's an odd number
of [INAUDIBLE] not carry over?
00:26:01.809 --> 00:26:03.600
CONSTANTINOS DASKALAKIS:
This carries over,
00:26:03.600 --> 00:26:07.930
except in degenerate games
where it doesn't hold.
00:26:07.930 --> 00:26:13.450
But in a non-degenerate
case, it will hold,
00:26:13.450 --> 00:26:17.185
not by direct use of Sperner's.
00:26:17.185 --> 00:26:20.680
Because Sperner is always going
to go through approximations.
00:26:20.680 --> 00:26:22.930
So there is another way to
prove the existence of Nash
00:26:22.930 --> 00:26:25.910
equilibria in two player
games using what is called
00:26:25.910 --> 00:26:27.880
the Lemke-Howson algorithm.
00:26:27.880 --> 00:26:30.570
and this Lemke-Howson
algorithm has a similar flavor
00:26:30.570 --> 00:26:31.329
as Sperner.
00:26:31.329 --> 00:26:33.120
And it also has an odd
number of solutions.
00:26:33.120 --> 00:26:35.810
And this is still true.
00:26:35.810 --> 00:26:37.644
So for two player
games, it is still true
00:26:37.644 --> 00:26:39.310
that there is an odd
number of solutions
00:26:39.310 --> 00:26:41.210
if the game is non-degenerate.
00:26:41.210 --> 00:26:45.170
I'm not sure what's the
status of multiplayer games,
00:26:45.170 --> 00:26:48.830
because then there are
irrational solutions.
00:26:48.830 --> 00:26:54.070
So combinatorics give you
approximations but not
00:26:54.070 --> 00:26:56.760
exact fixed points.
00:26:56.760 --> 00:26:58.490
Yeah?
00:26:58.490 --> 00:26:58.990
So yeah.
00:26:58.990 --> 00:27:01.360
So the fact that there is
an odd number of solutions
00:27:01.360 --> 00:27:04.480
calls for this combinatorial
problem, Sperner.
00:27:04.480 --> 00:27:08.090
But after you do compactness,
then I don't know what happens.
00:27:08.090 --> 00:27:09.980
So all bets are off.
00:27:09.980 --> 00:27:12.940
But for the specific
case of two player games,
00:27:12.940 --> 00:27:17.380
there is an alternative
proof that carries over.
00:27:17.380 --> 00:27:18.020
OK?
00:27:18.020 --> 00:27:18.700
Cool.
00:27:18.700 --> 00:27:19.200
OK.
00:27:19.200 --> 00:27:22.820
So these are the three problems
that I'm interested in.
00:27:22.820 --> 00:27:24.920
And now it's the
time where I'm going
00:27:24.920 --> 00:27:29.620
to get into a bit of
complex theory discussion.
00:27:29.620 --> 00:27:31.570
And in fact, this
complex theory discussion
00:27:31.570 --> 00:27:36.220
will lead to the fact that NP,
the standard concept that we
00:27:36.220 --> 00:27:39.110
use for understanding
complexity,
00:27:39.110 --> 00:27:41.834
is not sufficient to
address these problems.
00:27:41.834 --> 00:27:43.000
And that will motivate PPAD.
00:27:43.000 --> 00:27:48.310
00:27:48.310 --> 00:27:51.910
But first of all, let me give
intuition about why Sperner
00:27:51.910 --> 00:27:53.950
hard.
00:27:53.950 --> 00:27:58.290
And here's the situation
I want to be looking at.
00:27:58.290 --> 00:28:03.195
So I want to be looking at
the grid of size 2 to the n.
00:28:03.195 --> 00:28:05.070
So in particular, I'm
not going to be drawing
00:28:05.070 --> 00:28:07.040
the grid explicitly for you.
00:28:07.040 --> 00:28:09.060
And I'm not going to
be listing the colors
00:28:09.060 --> 00:28:13.810
of the internal
vertices as a list.
00:28:13.810 --> 00:28:16.770
So what I want to do
is I want to create
00:28:16.770 --> 00:28:22.500
a succinct description of a
coloring of an exponentially
00:28:22.500 --> 00:28:24.740
large instance in
the following way.
00:28:24.740 --> 00:28:27.990
So I'm going to be imagining
the existence of this grid
00:28:27.990 --> 00:28:31.199
with its boundary colored
in this specific way.
00:28:31.199 --> 00:28:32.740
And what I'm going
to give you is I'm
00:28:32.740 --> 00:28:36.260
going to give you a
circuit that takes
00:28:36.260 --> 00:28:43.020
as input the coordinates of
points inside this square
00:28:43.020 --> 00:28:43.950
and outputs a color.
00:28:43.950 --> 00:28:48.120
00:28:48.120 --> 00:28:52.530
Now so this circuit
only decides the colors
00:28:52.530 --> 00:28:55.320
of the vertices inside.
00:28:55.320 --> 00:29:00.100
And I fix the colors
of those vertices
00:29:00.100 --> 00:29:04.090
to be what is shown
in the picture.
00:29:04.090 --> 00:29:08.590
Thus, that's a succinct
description of a coloring of 2
00:29:08.590 --> 00:29:09.585
to the 2n vertices.
00:29:09.585 --> 00:29:12.150
00:29:12.150 --> 00:29:15.310
And this coloring satisfies the
conditions of Sperner's lemma.
00:29:15.310 --> 00:29:18.160
00:29:18.160 --> 00:29:22.064
In particular, there is
a tri-chromatic triangle.
00:29:22.064 --> 00:29:23.730
And what the problem
is asking you to do
00:29:23.730 --> 00:29:25.290
is to find such a triangle.
00:29:25.290 --> 00:29:29.070
00:29:29.070 --> 00:29:32.000
Describing this
triangle can be done
00:29:32.000 --> 00:29:35.140
with polynomials complexity
because all you need to do
00:29:35.140 --> 00:29:38.780
is to output the coordinates
of the three points
00:29:38.780 --> 00:29:40.050
participating in the triangle.
00:29:40.050 --> 00:29:42.134
So the output
description-- I'm not
00:29:42.134 --> 00:29:43.800
asking you to do
something crazy, right?
00:29:43.800 --> 00:29:50.930
So the output can be
described in polynomial size.
00:29:50.930 --> 00:29:55.960
The input-- and
what's problematic
00:29:55.960 --> 00:29:58.470
with this problem
is that the size
00:29:58.470 --> 00:30:00.470
of the graph we're
working with is
00:30:00.470 --> 00:30:03.590
exponential in the input size.
00:30:03.590 --> 00:30:07.310
So this circuit
has n input bits.
00:30:07.310 --> 00:30:10.880
So this graph is in
principle exponentially
00:30:10.880 --> 00:30:13.710
large in the description
of the problem.
00:30:13.710 --> 00:30:17.790
So in particular, I cannot just
go and check every triangle
00:30:17.790 --> 00:30:20.210
about whether it is
tri-chromatic or not.
00:30:20.210 --> 00:30:24.210
I have to do something
smarter to solve this problem.
00:30:24.210 --> 00:30:28.750
And in fact, we have no other--
essentially, no smart solutions
00:30:28.750 --> 00:30:31.321
to this problem.
00:30:31.321 --> 00:30:31.820
OK.
00:30:31.820 --> 00:30:33.480
So that Sperner's lemma.
00:30:33.480 --> 00:30:36.290
That's a way to define
the computational version
00:30:36.290 --> 00:30:38.420
of Sperner's lemma.
00:30:38.420 --> 00:30:40.880
Similarly, you can
define Nash and Brouwer.
00:30:40.880 --> 00:30:42.260
I'm only going to define Nash.
00:30:42.260 --> 00:30:44.490
Brouwer is a bit
more complicated.
00:30:44.490 --> 00:30:46.430
So in the Nash
problem, I'm giving
00:30:46.430 --> 00:30:49.090
a game which is described
by the number of players,
00:30:49.090 --> 00:30:53.030
the strategy sets,
which I enumerate,
00:30:53.030 --> 00:30:55.350
and the utility
functions of all players.
00:30:55.350 --> 00:30:57.060
This is the product
of all the sets.
00:30:57.060 --> 00:30:59.764
00:30:59.764 --> 00:31:01.930
And I'm also giving you an
approximation requirement
00:31:01.930 --> 00:31:02.830
epsilon.
00:31:02.830 --> 00:31:05.560
And I'm going to comment
on that in a second.
00:31:05.560 --> 00:31:07.840
What I want you to do is
to find an epsilon Nash
00:31:07.840 --> 00:31:10.970
equilibrium of this game.
00:31:10.970 --> 00:31:13.990
Now what's an epsilon Nash
equilibrium of the game?
00:31:13.990 --> 00:31:17.310
An epsilon Nash equilibrium is
a collection of mixed strategies
00:31:17.310 --> 00:31:20.320
such that no player has more
than an epsilon incentive
00:31:20.320 --> 00:31:23.370
to change his strategy.
00:31:23.370 --> 00:31:33.836
So in this definition here, I
would add a minus epsilon here
00:31:33.836 --> 00:31:35.824
to make it an epsilon
Nash equilibrium.
00:31:35.824 --> 00:31:39.810
00:31:39.810 --> 00:31:42.470
So I have not more than
an epsilon incentive
00:31:42.470 --> 00:31:43.920
to change my mixed strategy.
00:31:43.920 --> 00:31:46.130
That's what an epsilon
Nash equilibrium is.
00:31:46.130 --> 00:31:49.200
Now why did I have to define
the problem in this way?
00:31:49.200 --> 00:31:51.340
There's a specific
complex theoretic reason
00:31:51.340 --> 00:31:54.980
why I'm defining my problem
as an epsilon Nash instead
00:31:54.980 --> 00:31:58.467
of an exact Nash equilibrium.
00:31:58.467 --> 00:31:59.300
What is that reason?
00:31:59.300 --> 00:32:03.200
00:32:03.200 --> 00:32:03.887
Yeah
00:32:03.887 --> 00:32:06.569
AUDIENCE: Maybe the exact Nash
equilibrium makes [INAUDIBLE].
00:32:06.569 --> 00:32:09.119
00:32:09.119 --> 00:32:10.410
CONSTANTINOS DASKALAKIS: Right.
00:32:10.410 --> 00:32:13.090
So Nash's proof is via
Brouwer's theorem, which
00:32:13.090 --> 00:32:15.760
is a topological statement.
00:32:15.760 --> 00:32:19.720
And there's no guarantee
that the output-- if I
00:32:19.720 --> 00:32:22.430
were to omit this epsilon
from this definition,
00:32:22.430 --> 00:32:25.410
there's no guarantee that the
output has polynomial size
00:32:25.410 --> 00:32:26.550
complexity.
00:32:26.550 --> 00:32:29.430
Maybe a Nash equilibrium
is comprised of irrational
00:32:29.430 --> 00:32:34.310
numbers, which I cannot specify.
00:32:34.310 --> 00:32:35.560
Maybe it's not even algebraic.
00:32:35.560 --> 00:32:36.477
Who knows?
00:32:36.477 --> 00:32:37.310
But it is algebraic.
00:32:37.310 --> 00:32:39.860
00:32:39.860 --> 00:32:41.850
So approximations
are in fact-- Nash,
00:32:41.850 --> 00:32:45.950
his paper in '51, not the
original one but the one that
00:32:45.950 --> 00:32:47.750
appeared a year later.
00:32:47.750 --> 00:32:51.160
He actually provides an
example of a three player game
00:32:51.160 --> 00:32:55.100
that only has
irrational equilibria.
00:32:55.100 --> 00:32:59.990
So I'm working with epsilons
to avoid this issue.
00:32:59.990 --> 00:33:02.870
00:33:02.870 --> 00:33:07.510
Coming back to two
player games, you
00:33:07.510 --> 00:33:09.230
can actually show
that any two player
00:33:09.230 --> 00:33:14.850
game has a rational equilibrium
whose probabilities are
00:33:14.850 --> 00:33:18.510
of polynomial complexity in
the description of the game.
00:33:18.510 --> 00:33:20.770
So in this specific case
of two player games,
00:33:20.770 --> 00:33:22.470
you can actually
omit the epsilon
00:33:22.470 --> 00:33:25.290
if you want from the
description of this problem.
00:33:25.290 --> 00:33:27.000
But for general
games, you add a third
00:33:27.000 --> 00:33:30.500
to make this question
computationally meaningful.
00:33:30.500 --> 00:33:31.110
Yeah?
00:33:31.110 --> 00:33:32.943
AUDIENCE: Is it always
the case that there's
00:33:32.943 --> 00:33:37.220
an equilibrium that's a root
of the polynomial bounded
00:33:37.220 --> 00:33:39.250
complexity in the
description of the problem?
00:33:39.250 --> 00:33:41.500
CONSTANTINOS DASKALAKIS: I
believe this is true, yeah.
00:33:41.500 --> 00:33:43.810
00:33:43.810 --> 00:33:45.310
AUDIENCE: Can you
do the same thing?
00:33:45.310 --> 00:33:47.018
CONSTANTINOS DASKALAKIS:
You could, yeah.
00:33:47.018 --> 00:33:49.027
You could in principle do that.
00:33:49.027 --> 00:33:50.360
I'm not going to define Brouwer.
00:33:50.360 --> 00:33:53.324
But you can imagine in
Brouwer similar things.
00:33:53.324 --> 00:33:54.949
You have to take care
of similar things
00:33:54.949 --> 00:33:59.659
and define epsilon approximate
fixed points, et cetera.
00:33:59.659 --> 00:34:01.929
Now let's look at NP.
00:34:01.929 --> 00:34:04.420
The variant of NP
that I'm interested in
00:34:04.420 --> 00:34:09.630
is that of search problems
in NP, so function NP.
00:34:09.630 --> 00:34:11.010
I don't want to
bore you, but I'm
00:34:11.010 --> 00:34:12.989
going to go through
the definitions.
00:34:12.989 --> 00:34:16.280
So a search problem is
defined by a relation
00:34:16.280 --> 00:34:20.310
of inputs and solutions
such that a pair x and y
00:34:20.310 --> 00:34:23.690
is in this language
defined by this problem
00:34:23.690 --> 00:34:26.449
if y is a solution to x.
00:34:26.449 --> 00:34:28.920
So I expect you
to know all this.
00:34:28.920 --> 00:34:32.100
And I'm going to go fast
through these definitions.
00:34:32.100 --> 00:34:35.590
But what's important
here is this definition.
00:34:35.590 --> 00:34:38.160
When do we say that
the problem is total?
00:34:38.160 --> 00:34:40.580
We say the problem is
total if for every input
00:34:40.580 --> 00:34:43.150
there is a y that is a
solution to the problem.
00:34:43.150 --> 00:34:45.710
00:34:45.710 --> 00:34:48.700
For example, Sperner's
problem is total
00:34:48.700 --> 00:34:54.790
because for any instance
of Sperner's problem,
00:34:54.790 --> 00:34:56.090
there is actually a solution.
00:34:56.090 --> 00:35:01.220
00:35:01.220 --> 00:35:06.750
For any input of this form,
you know by Sperner's lemma
00:35:06.750 --> 00:35:09.290
that there is a solution.
00:35:09.290 --> 00:35:12.190
So that problem is
a total problem.
00:35:12.190 --> 00:35:18.020
Similarly, for every input
to Nash, there is a solution.
00:35:18.020 --> 00:35:19.640
So these problems
are total problems.
00:35:19.640 --> 00:35:23.165
00:35:23.165 --> 00:35:25.895
Let's see.
00:35:25.895 --> 00:35:27.260
OK.
00:35:27.260 --> 00:35:35.980
Now a search problem is
an FNP, function of NP,
00:35:35.980 --> 00:35:39.530
if there is a polynomial
time algorithm
00:35:39.530 --> 00:35:45.630
and a polynomial function
so that two conditions are
00:35:45.630 --> 00:35:48.140
satisfied.
00:35:48.140 --> 00:35:55.360
First, if the algorithm
on input x and y is 1,
00:35:55.360 --> 00:36:01.080
then and only then y
is a solution to x.
00:36:01.080 --> 00:36:04.930
And also for every
input to the problem,
00:36:04.930 --> 00:36:09.220
if there is a solution
to that instance,
00:36:09.220 --> 00:36:13.990
then there is one whose size
is polynomial in the input
00:36:13.990 --> 00:36:15.230
of the problem.
00:36:15.230 --> 00:36:19.450
So you have solutions that
are polynomially large.
00:36:19.450 --> 00:36:23.050
00:36:23.050 --> 00:36:24.970
And so this is FNP.
00:36:24.970 --> 00:36:27.395
And TFNP is the
class of problems
00:36:27.395 --> 00:36:30.660
that contains all problems
in NP that are total.
00:36:30.660 --> 00:36:33.340
And based on the previous
discussion, all the problems
00:36:33.340 --> 00:36:38.810
we're interested in, Sperner,
Nash, and Brouwer, are TFNP.
00:36:38.810 --> 00:36:39.310
Sorry.
00:36:39.310 --> 00:36:39.809
TFNP.
00:36:39.809 --> 00:36:45.265
Both in FNP but also in TFNP.
00:36:45.265 --> 00:36:47.130
OK.
00:36:47.130 --> 00:36:51.510
And I guess let me remind
you about FNP completeness.
00:36:51.510 --> 00:36:55.280
A problem in FNP associated
with an algorithm
00:36:55.280 --> 00:36:58.896
and a polynomial function
is poly-time reducible
00:36:58.896 --> 00:37:02.150
to another one associated
with an algorithm
00:37:02.150 --> 00:37:03.630
and a different bound.
00:37:03.630 --> 00:37:07.480
If there exist two functions,
f and g, one of them
00:37:07.480 --> 00:37:13.260
is mapping inputs to l
to inputs to l prime.
00:37:13.260 --> 00:37:14.910
And also, you have
two properties.
00:37:14.910 --> 00:37:16.990
And it's important to
look at these properties
00:37:16.990 --> 00:37:21.220
carefully because they're
related to a point
00:37:21.220 --> 00:37:24.270
that I want to make.
00:37:24.270 --> 00:37:27.120
So for the reduction
to be valid,
00:37:27.120 --> 00:37:31.840
you also need this property,
that for every x and y,
00:37:31.840 --> 00:37:36.400
if the algorithm of problem l
prime on the transformed input
00:37:36.400 --> 00:37:40.890
and y says 1, then you
can take that solution
00:37:40.890 --> 00:37:44.640
and transform it into a
solution to the instance to l.
00:37:44.640 --> 00:37:47.770
This is what it says.
00:37:47.770 --> 00:37:52.000
Well, this one says that if
the transform instance has
00:37:52.000 --> 00:37:55.880
no solution, then the
original instance also
00:37:55.880 --> 00:37:59.440
shouldn't have any solution.
00:37:59.440 --> 00:38:02.690
And a search problem is FNP
complete if it's both in FNP,
00:38:02.690 --> 00:38:09.010
and every problem in FNP is
polynomial time reducible
00:38:09.010 --> 00:38:09.970
to it.
00:38:09.970 --> 00:38:12.750
And of course, finding
a satisfying assignment
00:38:12.750 --> 00:38:14.730
is FNP complete.
00:38:14.730 --> 00:38:17.800
But now we reached the
point that I want to make.
00:38:17.800 --> 00:38:23.030
What I want to claim is that
I cannot possibly reduce SAT
00:38:23.030 --> 00:38:25.980
to any of the problems
that I'm interested in.
00:38:25.980 --> 00:38:31.440
In particular, I cannot show
that there's no Karp reduction
00:38:31.440 --> 00:38:34.990
from SAT to any
of these problems.
00:38:34.990 --> 00:38:37.870
And the reason is this property.
00:38:37.870 --> 00:38:42.420
Recall, this property was saying
that for every input to problem
00:38:42.420 --> 00:38:52.500
l, if the y' is a solution
to the transformed instance,
00:38:52.500 --> 00:38:55.620
then I can convert that
solution to a solution
00:38:55.620 --> 00:38:58.400
to the original instance.
00:38:58.400 --> 00:39:03.590
But now if l is SAT, and
this is Sperner, then
00:39:03.590 --> 00:39:08.160
no matter how you transform
the SAT instance to a Sperner
00:39:08.160 --> 00:39:13.180
instance, there is going to be a
triangle that is tri-chromatic,
00:39:13.180 --> 00:39:15.610
setting this to 1.
00:39:15.610 --> 00:39:19.860
So I should be able to
then convert this triangle
00:39:19.860 --> 00:39:21.340
to a satisfying assignment.
00:39:21.340 --> 00:39:24.710
But what if those instances
are unsatisfiable?
00:39:24.710 --> 00:39:30.250
That possibly cannot hold
if your two problems are SAT
00:39:30.250 --> 00:39:31.270
and Sperner.
00:39:31.270 --> 00:39:32.970
So there's no reduction.
00:39:32.970 --> 00:39:36.690
There's no Karp reduction
from SAT to Sperner.
00:39:36.690 --> 00:39:40.780
So you can't show any of these
problems for that matter.
00:39:40.780 --> 00:39:43.550
So you cannot possibly argue
that these problems are FNP
00:39:43.550 --> 00:39:46.360
complete.
00:39:46.360 --> 00:39:51.170
Another thing you may try is to
get Turing reductions from SAT
00:39:51.170 --> 00:39:53.070
to these problems.
00:39:53.070 --> 00:39:54.630
But that has other issues.
00:39:54.630 --> 00:40:00.190
It basically would imply
that NP equals co-NP.
00:40:00.190 --> 00:40:04.830
So there's no way basically.
00:40:04.830 --> 00:40:07.940
These types of problems
don't-- if you want type check,
00:40:07.940 --> 00:40:08.880
they don't type check.
00:40:08.880 --> 00:40:10.800
These are problems
that are total,
00:40:10.800 --> 00:40:16.330
and these are problems who's
complexity really resides
00:40:16.330 --> 00:40:18.330
with the fact that it's
hard to distinguish
00:40:18.330 --> 00:40:23.890
satisfiable and
non-satisfiable instances.
00:40:23.890 --> 00:40:27.350
So LP completeness is not the
right language, if you want.
00:40:27.350 --> 00:40:30.740
It's not the right framework
to understand the complexity
00:40:30.740 --> 00:40:31.947
of these problems.
00:40:31.947 --> 00:40:34.030
And the exercise through
which we're going today--
00:40:34.030 --> 00:40:36.460
and I think it's
instructive-- is
00:40:36.460 --> 00:40:39.400
how to go about
characterizing problems
00:40:39.400 --> 00:40:44.490
that don't fit into traditional
complexity theoretic
00:40:44.490 --> 00:40:46.269
frameworks.
00:40:46.269 --> 00:40:48.060
So in particular, what
I want to understand
00:40:48.060 --> 00:40:51.310
is how to go about
defining a complexity
00:40:51.310 --> 00:40:56.560
theory of total search
problems inside FNP.
00:40:56.560 --> 00:40:58.750
Clearly, these problems
actually are inside FNP.
00:40:58.750 --> 00:41:00.570
These are FNP problems.
00:41:00.570 --> 00:41:02.170
They're TFNP problems.
00:41:02.170 --> 00:41:09.530
So how do you go about coming
up with a complexity theory
00:41:09.530 --> 00:41:12.930
of total search problems?
00:41:12.930 --> 00:41:17.540
And the way you go
about it is to look
00:41:17.540 --> 00:41:24.480
at the proof of existence of
solutions in these problems
00:41:24.480 --> 00:41:32.010
and understand the combinatorial
underpinnings of the existence
00:41:32.010 --> 00:41:33.740
argument.
00:41:33.740 --> 00:41:38.360
So if you want the 100 feet
overview of the methodology
00:41:38.360 --> 00:41:40.790
that I'm going to
follow, it's this.
00:41:40.790 --> 00:41:44.850
First, I want to identify
the combinatorial argument
00:41:44.850 --> 00:41:48.470
of existence responsible for
making all these problems
00:41:48.470 --> 00:41:51.380
total problems.
00:41:51.380 --> 00:41:54.770
And then I want to define
a complexity class inspired
00:41:54.770 --> 00:41:57.970
by this argument of existence.
00:41:57.970 --> 00:42:01.820
And the litmus
test of my approach
00:42:01.820 --> 00:42:06.890
is if the resulting
complexity class actually
00:42:06.890 --> 00:42:10.271
tidily characterizes the
complexity of these problems.
00:42:10.271 --> 00:42:11.770
So what I'm going
to do is I'm going
00:42:11.770 --> 00:42:14.340
to show you the proof
for Sperner's lemma,
00:42:14.340 --> 00:42:18.520
and that's going to inspire
the definition of PPAD.
00:42:18.520 --> 00:42:22.070
So this is what I'm going to
do in the next few slides.
00:42:22.070 --> 00:42:23.780
So here's the
statement of the lemma.
00:42:23.780 --> 00:42:25.890
If your boundary
is legally colored,
00:42:25.890 --> 00:42:27.650
then there is
always an odd number
00:42:27.650 --> 00:42:32.800
of tri-chromatic triangles,
in particular at least one.
00:42:32.800 --> 00:42:34.100
Let me try to prove it for you.
00:42:34.100 --> 00:42:37.110
00:42:37.110 --> 00:42:39.350
The first thing I'm
going to do says
00:42:39.350 --> 00:42:42.440
I'm going to introduce
an artificial vertex
00:42:42.440 --> 00:42:46.700
at the bottom left
of the square.
00:42:46.700 --> 00:42:47.520
Here it is.
00:42:47.520 --> 00:42:50.900
And I'm going to color it blue.
00:42:50.900 --> 00:42:54.530
Now no matter how you
color the internal vertices
00:42:54.530 --> 00:42:58.240
of this square,
because I have fixed
00:42:58.240 --> 00:43:00.960
by coloring on the boundary
to be the one you see here
00:43:00.960 --> 00:43:06.520
in this picture, I know that by
adding a blue vertex over here,
00:43:06.520 --> 00:43:11.140
I'm creating an artificial
tri-chromatic triangle.
00:43:11.140 --> 00:43:15.670
I'm going to call the triangle
the beginning of my walk.
00:43:15.670 --> 00:43:21.990
And now I'm going to basically
define a walk in this grid.
00:43:21.990 --> 00:43:24.070
Consider this is a big factory.
00:43:24.070 --> 00:43:28.970
The factory is partitioned
into triangular rooms.
00:43:28.970 --> 00:43:32.260
And I'm starting my walk in
this factory from this vertex
00:43:32.260 --> 00:43:36.160
here, from this triangle here.
00:43:36.160 --> 00:43:39.000
Now my walk is going to be
doing the following thing.
00:43:39.000 --> 00:43:41.470
It's going to be going from
triangle to neighbouring .
00:43:41.470 --> 00:43:46.000
Triangle and the transition
rule is the following.
00:43:46.000 --> 00:43:49.045
I'm going to look
in the room I'm in,
00:43:49.045 --> 00:43:54.220
and I'm going to try to
find a red-yellow door.
00:43:54.220 --> 00:43:59.210
If I find such a door, I want
to try to cross it having red
00:43:59.210 --> 00:44:00.760
on my left hand.
00:44:00.760 --> 00:44:03.790
That's the rule of my walk.
00:44:03.790 --> 00:44:05.620
Red-yellow doors.
00:44:05.620 --> 00:44:08.730
I want to cross them
with red on my left.
00:44:08.730 --> 00:44:10.640
That's important.
00:44:10.640 --> 00:44:12.330
I meant to say
yellow on your left.
00:44:12.330 --> 00:44:13.620
Sorry about that.
00:44:13.620 --> 00:44:15.370
So let's go back
to this picture.
00:44:15.370 --> 00:44:18.530
I created these artificial
triangle over here.
00:44:18.530 --> 00:44:20.160
I knew it's going
to be tri-chromatic
00:44:20.160 --> 00:44:23.530
because it only considers
vertices on the boundary.
00:44:23.530 --> 00:44:25.420
And I have fixed the
coloring of the boundary
00:44:25.420 --> 00:44:27.399
to be this specific one.
00:44:27.399 --> 00:44:29.690
I know it's going to have a
red-yellow door which I can
00:44:29.690 --> 00:44:32.970
cross having yellow on my left.
00:44:32.970 --> 00:44:36.220
So let me cross that door.
00:44:36.220 --> 00:44:39.840
Now I'm entering
into a new room.
00:44:39.840 --> 00:44:41.560
In this particular
case, there's nothing
00:44:41.560 --> 00:44:44.420
interesting about this
room because this still
00:44:44.420 --> 00:44:45.950
touches the boundary.
00:44:45.950 --> 00:44:48.340
So no matter how you color
the internal vertices,
00:44:48.340 --> 00:44:50.800
you couldn't affect the
coloring of this boundary.
00:44:50.800 --> 00:44:54.030
So it's also going to have a
red-yellow door, which I can
00:44:54.030 --> 00:44:55.420
cross having yellow on my left.
00:44:55.420 --> 00:44:58.320
And the interesting
business starts now.
00:44:58.320 --> 00:45:02.020
I entered into a new room, and
depending on your coloring,
00:45:02.020 --> 00:45:04.210
maybe it's already
tri-chromatic.
00:45:04.210 --> 00:45:07.030
So how do you color
this into blue?
00:45:07.030 --> 00:45:09.030
This would already be a
tri-chromatic triangle.
00:45:09.030 --> 00:45:09.530
why?
00:45:09.530 --> 00:45:12.330
Because you entered that room
through a red-yellow door,
00:45:12.330 --> 00:45:16.890
and you encountered
a blue color.
00:45:16.890 --> 00:45:20.300
What is cool about it though
is that if it's not blue,
00:45:20.300 --> 00:45:22.520
then there's going
to be for sure
00:45:22.520 --> 00:45:26.400
another door which you can cross
having yellow on your left.
00:45:26.400 --> 00:45:28.620
In this particular
scenario, this was a yellow.
00:45:28.620 --> 00:45:29.400
It wasn't a blue.
00:45:29.400 --> 00:45:32.030
So this was not a
tri-chromatic triangle.
00:45:32.030 --> 00:45:35.372
But because this was a
yellow, I enter a room
00:45:35.372 --> 00:45:37.330
through a red-yellow
door, and I find a yellow.
00:45:37.330 --> 00:45:39.340
There is for sure
another red-yellow
00:45:39.340 --> 00:45:43.280
door I can cross having
yellow on my left.
00:45:43.280 --> 00:45:44.910
So this is what I'm going to do.
00:45:44.910 --> 00:45:50.265
And I'm going to keep
doing this until-- what
00:45:50.265 --> 00:45:51.510
can go wrong, right?
00:45:51.510 --> 00:45:55.430
So the claim that I want to make
is that if I keep doing this
00:45:55.430 --> 00:46:00.360
procedure, I cannot
exit the factory.
00:46:00.360 --> 00:46:02.126
For me to exit
the factory, there
00:46:02.126 --> 00:46:06.050
has to be a door on the
boundary which I can
00:46:06.050 --> 00:46:09.080
cross having yellow on my left.
00:46:09.080 --> 00:46:12.220
Now because-- and that's where
the coloring of the boundary
00:46:12.220 --> 00:46:13.650
becomes important.
00:46:13.650 --> 00:46:15.700
Because I have fixed the
color of the boundary
00:46:15.700 --> 00:46:17.780
to be the one you
see in this picture,
00:46:17.780 --> 00:46:20.110
you can verify that there
is no red-yellow door
00:46:20.110 --> 00:46:21.600
you can cross to go outside.
00:46:21.600 --> 00:46:24.110
00:46:24.110 --> 00:46:27.200
The only red-yellow door
that exists is this one.
00:46:27.200 --> 00:46:29.870
But if you're inside, you cannot
cross it going to the outside
00:46:29.870 --> 00:46:31.290
having yellow on your left.
00:46:31.290 --> 00:46:33.520
And that's where having
left on your left hand side
00:46:33.520 --> 00:46:35.520
is important.
00:46:35.520 --> 00:46:37.360
This is the only
red-yellow door.
00:46:37.360 --> 00:46:39.450
But you cannot cross
it going outside.
00:46:39.450 --> 00:46:41.600
You can only cross
it going inside.
00:46:41.600 --> 00:46:44.910
So you cannot exit the factory.
00:46:44.910 --> 00:46:47.010
So your walk is
going to keep going.
00:46:47.010 --> 00:46:49.940
00:46:49.940 --> 00:46:52.260
And there are two
possibilities now.
00:46:52.260 --> 00:46:55.180
So one is that it's
going to keep going.
00:46:55.180 --> 00:46:57.775
And then it's going to
enter into a new room
00:46:57.775 --> 00:47:00.150
through a red-yellow door,
and it's going to find a blue.
00:47:00.150 --> 00:47:02.590
In that case, my
lemma is proven,
00:47:02.590 --> 00:47:05.459
not the odd number, but at
least I've proven to you
00:47:05.459 --> 00:47:08.000
there is at least one triangle
because I entered into a room.
00:47:08.000 --> 00:47:09.530
I found a blue.
00:47:09.530 --> 00:47:11.290
I entered through
a red-yellow door.
00:47:11.290 --> 00:47:13.240
That's a proof of existence.
00:47:13.240 --> 00:47:15.490
But there is one thing
that can go wrong, though.
00:47:15.490 --> 00:47:16.630
What is that?
00:47:16.630 --> 00:47:17.990
I can loop around.
00:47:17.990 --> 00:47:22.400
So what I can do is I can--
so this is my factory.
00:47:22.400 --> 00:47:23.630
I started over here.
00:47:23.630 --> 00:47:27.950
I start wandering
around this factory.
00:47:27.950 --> 00:47:30.435
And then I sort
of got into a room
00:47:30.435 --> 00:47:31.960
that I had already
visited before.
00:47:31.960 --> 00:47:36.380
And then I get into a
loop, and I go forever.
00:47:36.380 --> 00:47:40.050
That's the problem
that may happen.
00:47:40.050 --> 00:47:42.220
I claimed over there
that this cannot happen.
00:47:42.220 --> 00:47:44.362
Why can it not happen?
00:47:44.362 --> 00:47:45.655
AUDIENCE: Coloring.
00:47:45.655 --> 00:47:47.863
CONSTANTINOS DASKALAKIS:
Yeah, let's try to color it.
00:47:47.863 --> 00:47:49.640
Let's zoom into here.
00:47:49.640 --> 00:47:54.480
So this is a room that I
got into at the beginning
00:47:54.480 --> 00:47:56.930
through a red-yellow door
having yellow on my left.
00:47:56.930 --> 00:47:59.350
So originally, I
got into this room
00:47:59.350 --> 00:48:03.040
like this having
yellow on my left.
00:48:03.040 --> 00:48:07.940
Then I exited this room
through a red-yellow door
00:48:07.940 --> 00:48:09.030
having yellow my left.
00:48:09.030 --> 00:48:16.040
So this door, potentially
it was a red here.
00:48:16.040 --> 00:48:17.350
So I exited this way.
00:48:17.350 --> 00:48:20.350
But then I cannot possibly
enter through this door,
00:48:20.350 --> 00:48:22.200
because that's a red-red door.
00:48:22.200 --> 00:48:26.110
Or this could be a yellow, in
which case, I exited from here.
00:48:26.110 --> 00:48:28.220
But still now I cannot
get back from that door,
00:48:28.220 --> 00:48:30.060
because that's a
yellow-yellow door.
00:48:30.060 --> 00:48:32.560
So this cannot happen.
00:48:32.560 --> 00:48:39.910
So my walk cannot get back
into an already visited room,
00:48:39.910 --> 00:48:42.070
and it cannot exit the factory.
00:48:42.070 --> 00:48:44.430
So the only thing it
can do is just stop
00:48:44.430 --> 00:48:47.640
because there's a finite number
of rooms in this factory.
00:48:47.640 --> 00:48:52.030
But the only way it can stop
is if it finds a blue when
00:48:52.030 --> 00:48:53.680
it enters a new room.
00:48:53.680 --> 00:48:55.849
So that's the
proof of existence.
00:48:55.849 --> 00:48:57.390
If you follow my
walk, indeed, you're
00:48:57.390 --> 00:49:01.390
going to get into a
tri-chromatic triangle.
00:49:01.390 --> 00:49:05.390
And this way, I finished
the first part of the claim.
00:49:05.390 --> 00:49:08.870
Any questions about that?
00:49:08.870 --> 00:49:09.840
Yeah.
00:49:09.840 --> 00:49:11.800
AUDIENCE: The same argument
give you the odd number though?
00:49:11.800 --> 00:49:13.424
CONSTANTINOS DASKALAKIS:
It does, yeah.
00:49:13.424 --> 00:49:14.024
What is it?
00:49:14.024 --> 00:49:15.440
AUDIENCE: If you
find another one,
00:49:15.440 --> 00:49:17.209
then it has to [INAUDIBLE].
00:49:17.209 --> 00:49:18.500
CONSTANTINOS DASKALAKIS: Right.
00:49:18.500 --> 00:49:19.530
Let's try to do that.
00:49:19.530 --> 00:49:21.810
So let's start from
a different triangle.
00:49:21.810 --> 00:49:23.295
Let's start from here.
00:49:23.295 --> 00:49:24.670
But if I start
from here, there's
00:49:24.670 --> 00:49:26.780
no red-yellow door I can follow.
00:49:26.780 --> 00:49:28.291
So that doesn't
give me anything.
00:49:28.291 --> 00:49:29.790
But let's start
with somewhere where
00:49:29.790 --> 00:49:30.915
there are red-yellow doors.
00:49:30.915 --> 00:49:33.770
So let's start with here.
00:49:33.770 --> 00:49:36.130
Now I can follow the
same kind of business.
00:49:36.130 --> 00:49:40.810
I can get into doors.
00:49:40.810 --> 00:49:43.060
I can cross red-yellow doors
having yellow on my left.
00:49:43.060 --> 00:49:47.000
In this case, that got me
into a tri-chromatic triangle.
00:49:47.000 --> 00:49:50.650
Now let me go back here and
actually do the word backwards,
00:49:50.650 --> 00:49:53.890
so have it going backwards,
having yellow on my left.
00:49:53.890 --> 00:49:55.120
So this is what happens.
00:49:55.120 --> 00:49:58.020
So I found a
tri-chromatic triangle.
00:49:58.020 --> 00:49:59.730
And these actually
came in pairs.
00:49:59.730 --> 00:50:03.380
The fact that this gave me a
tri-chromatic triangle must
00:50:03.380 --> 00:50:07.360
mean that this has to give you
another one because by the same
00:50:07.360 --> 00:50:12.380
token, I cannot sort of get
into a loop while going back.
00:50:12.380 --> 00:50:14.240
On the other hand,
there are some triangles
00:50:14.240 --> 00:50:18.256
where that would give you-- so
you get another pair over here.
00:50:18.256 --> 00:50:20.630
These don't give you anything,
because if you start here,
00:50:20.630 --> 00:50:23.010
you don't move.
00:50:23.010 --> 00:50:26.670
But here you can get loops.
00:50:26.670 --> 00:50:29.240
If you start from the inside,
you can get into a loop.
00:50:29.240 --> 00:50:35.810
The point is that all
triangles come in pairs,
00:50:35.810 --> 00:50:38.980
except for this walk, which
started with an artificial one.
00:50:38.980 --> 00:50:41.700
00:50:41.700 --> 00:50:45.690
So all tri-chromatic
triangles come in pairs,
00:50:45.690 --> 00:50:49.020
except for the tri-chromatic
triangle that I
00:50:49.020 --> 00:50:52.607
found in my original walk.
00:50:52.607 --> 00:50:54.315
Thereby, there is an
odd number of those.
00:50:54.315 --> 00:50:58.200
00:50:58.200 --> 00:51:02.270
So it's kind of-- its
pretty cool, right?
00:51:02.270 --> 00:51:06.250
Let me actually try to abstract
this proof a little bit
00:51:06.250 --> 00:51:12.140
and sort of focus more onto the
core argument why this happens.
00:51:12.140 --> 00:51:13.370
So here's what I did, really.
00:51:13.370 --> 00:51:16.730
So this is my
space of triangles.
00:51:16.730 --> 00:51:19.550
This is my set of triangles.
00:51:19.550 --> 00:51:24.940
I want to define a graph where
the vertices are the triangles.
00:51:24.940 --> 00:51:31.450
And the adjacency of
triangles-- so two triangles
00:51:31.450 --> 00:51:34.820
are connected if
they share a door,
00:51:34.820 --> 00:51:39.990
and you can go from one
triangle into the other one
00:51:39.990 --> 00:51:43.670
through this door having
yellow on your left.
00:51:43.670 --> 00:51:49.395
So for this reason, all vertices
have out degree and in degree
00:51:49.395 --> 00:51:54.350
at most 1 because every
triangle-- no matter how it's
00:51:54.350 --> 00:51:56.580
colored-- has at most
one red-yellow door
00:51:56.580 --> 00:52:00.450
which you can cross having
yellow on your left to go out.
00:52:00.450 --> 00:52:02.130
And it has at most
one door which
00:52:02.130 --> 00:52:07.840
you can cross having yellow
on your left going in.
00:52:07.840 --> 00:52:11.970
So just the minute definition
of my transition rule,
00:52:11.970 --> 00:52:14.750
which was cross a red-yellow
door having yellow
00:52:14.750 --> 00:52:17.940
on your left, defined
a graph on the set
00:52:17.940 --> 00:52:24.700
of triangles that has in degree
and out degree at most 1.
00:52:24.700 --> 00:52:28.420
Now a graph with in degree
and out degree at most 1
00:52:28.420 --> 00:52:30.340
is a very simple type of graph.
00:52:30.340 --> 00:52:32.250
It looks like this.
00:52:32.250 --> 00:52:34.210
It's a bunch of
isolated vertices,
00:52:34.210 --> 00:52:37.430
a bunch of directed cycles,
and a bunch of directed paths.
00:52:37.430 --> 00:52:40.190
00:52:40.190 --> 00:52:46.840
And in fact, the way I
define my position rule,
00:52:46.840 --> 00:52:52.570
you could check that all degree
1 nodes must be tri-chromatic.
00:52:52.570 --> 00:52:55.760
If you're tri-chromatic,
there is either
00:52:55.760 --> 00:52:58.840
one door you can exit,
one red-yellow door
00:52:58.840 --> 00:53:01.000
you can exit having
yellow on your left.
00:53:01.000 --> 00:53:03.670
Or depending on how the
coloring is, one door
00:53:03.670 --> 00:53:06.860
you can use to enter
the triangle having
00:53:06.860 --> 00:53:08.420
yellow on your left.
00:53:08.420 --> 00:53:15.390
So only tri-chromatic triangles
can have total degree 1.
00:53:15.390 --> 00:53:19.860
00:53:19.860 --> 00:53:23.920
Isolated vertices are those who
don't have red-yellow doors.
00:53:23.920 --> 00:53:30.390
And degree 2 are those who
have two doors, one with which
00:53:30.390 --> 00:53:32.874
you can exit having yellow
on your left and one
00:53:32.874 --> 00:53:35.040
with which you can enter
having yellow on your left.
00:53:35.040 --> 00:53:39.550
So what I want to summarize
is that the mere definition
00:53:39.550 --> 00:53:43.480
of my transition rule
defines this graph in a way
00:53:43.480 --> 00:53:48.860
that all these unbalanced
vertices are solutions
00:53:48.860 --> 00:53:50.780
to the Sperner problem.
00:53:50.780 --> 00:53:55.170
All the vertices were solutions
to the Sperner problem.
00:53:55.170 --> 00:53:57.300
And in fact, one
solution was artificial
00:53:57.300 --> 00:54:00.080
because it was that triangle
that I created by adding
00:54:00.080 --> 00:54:02.290
the extra node outside.
00:54:02.290 --> 00:54:06.100
So all degree 1 vertices
are real solutions,
00:54:06.100 --> 00:54:08.778
except one of them.
00:54:08.778 --> 00:54:10.152
And by the structure
of the graph
00:54:10.152 --> 00:54:14.550
then, there has to be an
odd number of solutions.
00:54:14.550 --> 00:54:16.160
This is implied.
00:54:16.160 --> 00:54:18.630
So to summarize,
the mere description
00:54:18.630 --> 00:54:21.260
of my transition rule
defines this graph in a way
00:54:21.260 --> 00:54:25.340
that all unbalanced
vertices are solutions.
00:54:25.340 --> 00:54:29.570
And because these have to
come in pairs by parity,
00:54:29.570 --> 00:54:31.710
there is an even
number of solutions.
00:54:31.710 --> 00:54:32.919
Except one was artificial.
00:54:32.919 --> 00:54:34.835
So hence, there is an
odd number of solutions.
00:54:34.835 --> 00:54:37.630
00:54:37.630 --> 00:54:40.340
So in particular,
what I want to argue
00:54:40.340 --> 00:54:43.000
is that all these very
beautiful, very interesting
00:54:43.000 --> 00:54:45.420
theorems that I showed
in the beginning,
00:54:45.420 --> 00:54:51.260
Nash, Brouwer, and Sperner--
the real argument of existence,
00:54:51.260 --> 00:54:54.780
besides sort of
mathematical work,
00:54:54.780 --> 00:54:57.950
mathematical
obfuscation, if you want,
00:54:57.950 --> 00:55:01.980
is this trivial statement
in combinatorics.
00:55:01.980 --> 00:55:06.970
If you have a directed graph
with some unbalanced vertex,
00:55:06.970 --> 00:55:09.590
then there must be
another unbalanced vertex.
00:55:09.590 --> 00:55:13.250
00:55:13.250 --> 00:55:15.190
You obviously know this theorem.
00:55:15.190 --> 00:55:17.310
The proof of this
theorem is pretty clear.
00:55:17.310 --> 00:55:19.770
If you have a directed
graph where some node has
00:55:19.770 --> 00:55:24.540
a different number of
outgoing and ingoing edges,
00:55:24.540 --> 00:55:27.280
then there has to be
another such node.
00:55:27.280 --> 00:55:29.900
And effectively,
what I did over here
00:55:29.900 --> 00:55:33.380
is I described a
directed graph, and I
00:55:33.380 --> 00:55:37.680
identified this artificial
vertex, which was unbalanced.
00:55:37.680 --> 00:55:41.360
It only had an ongoing
edge but no incoming edge.
00:55:41.360 --> 00:55:45.490
And by parity, I knew there
must exist another one.
00:55:45.490 --> 00:55:49.540
So in fact, I didn't even
have to use my walk argument
00:55:49.540 --> 00:55:50.180
and stuff.
00:55:50.180 --> 00:55:53.450
All I had to claim is
that the mere definition
00:55:53.450 --> 00:55:56.360
of my transition rule
defined this directed graph.
00:55:56.360 --> 00:55:59.484
And this directed graph
had some unbalanced vertex.
00:55:59.484 --> 00:56:01.150
And I know that
somewhere in this graph,
00:56:01.150 --> 00:56:03.930
there has to be another
unbalanced vertex.
00:56:03.930 --> 00:56:05.784
But all I'm saying is
that the core of it
00:56:05.784 --> 00:56:06.700
is this trivial lemma.
00:56:06.700 --> 00:56:11.960
00:56:11.960 --> 00:56:14.680
And now your question will
be, well, what the heck?
00:56:14.680 --> 00:56:16.060
This lemma is trivial.
00:56:16.060 --> 00:56:19.550
So we took so many
algorithms, Karger's class
00:56:19.550 --> 00:56:20.760
and so on and so forth.
00:56:20.760 --> 00:56:21.960
We've worked with graphs.
00:56:21.960 --> 00:56:25.200
We know how to identify
these things, right?
00:56:25.200 --> 00:56:27.280
Given a directed graph,
it's trivial to find
00:56:27.280 --> 00:56:28.300
an unbalanced vertex.
00:56:28.300 --> 00:56:31.390
00:56:31.390 --> 00:56:34.500
But the point is that
you can sometimes
00:56:34.500 --> 00:56:39.510
define exponentially
large graphs succinctly.
00:56:39.510 --> 00:56:43.150
And you can ask people to
find your unbalanced vertices
00:56:43.150 --> 00:56:47.700
in exponentially large graphs.
00:56:47.700 --> 00:56:51.390
So that's what PPAD is about.
00:56:51.390 --> 00:56:55.090
In fact, if I give
you a Sperner instance
00:56:55.090 --> 00:56:58.220
by providing you a
circuit, we'd only
00:56:58.220 --> 00:57:01.770
be working with
exponentially many triangles
00:57:01.770 --> 00:57:04.270
in the description
of the circuit.
00:57:04.270 --> 00:57:07.020
So that's why the
problem is difficult.
00:57:07.020 --> 00:57:10.480
The problem is difficult because
the guy we're working with
00:57:10.480 --> 00:57:13.390
is exponentially large in the
description of the problem,
00:57:13.390 --> 00:57:15.680
of the instance.
00:57:15.680 --> 00:57:21.070
So the PPAD class is trying
to capture this structure.
00:57:21.070 --> 00:57:24.630
And we're right about
the point where I'm going
00:57:24.630 --> 00:57:28.360
to define the class formally.
00:57:28.360 --> 00:57:31.300
So you ready for this?
00:57:31.300 --> 00:57:32.780
Oops.
00:57:32.780 --> 00:57:33.280
OK.
00:57:33.280 --> 00:57:35.920
The PPAD class, defined
by Papadimitriou
00:57:35.920 --> 00:57:39.490
in the '90s-- actually,
this is the general version
00:57:39.490 --> 00:57:40.050
of the paper.
00:57:40.050 --> 00:57:43.930
00:57:43.930 --> 00:57:49.410
The PPAD class is giving you
an exponentially large graph.
00:57:49.410 --> 00:57:54.330
The vertex set of the
graph is 0, 1 to the n.
00:57:54.330 --> 00:57:57.290
The graph is specified
in a weird way.
00:57:57.290 --> 00:58:02.740
I'm going to give
you two circuits that
00:58:02.740 --> 00:58:08.450
get an n input bit, and n bit
input and have an n bit output.
00:58:08.450 --> 00:58:11.290
00:58:11.290 --> 00:58:14.570
And using these two
circuits, I define
00:58:14.570 --> 00:58:18.230
an edge between a string
and another string
00:58:18.230 --> 00:58:22.130
if a weird condition
is satisfied.
00:58:22.130 --> 00:58:24.720
So now we directed
that from v1 to v2
00:58:24.720 --> 00:58:27.660
if this condition is satisfied.
00:58:27.660 --> 00:58:32.790
Let me try to parse
these symbols there.
00:58:32.790 --> 00:58:34.690
But before that, let
me call this circuit
00:58:34.690 --> 00:58:37.200
the possible previous circuit.
00:58:37.200 --> 00:58:41.530
And let me call this circuit
the possible next circuit.
00:58:41.530 --> 00:58:45.410
Now this circuit
takes as input string,
00:58:45.410 --> 00:58:52.930
and it outputs a candidate
neighbor of that string.
00:58:52.930 --> 00:58:59.020
And similarly, this-- sorry, a
candidate father of the string.
00:58:59.020 --> 00:59:00.970
And takes as input
a string and outputs
00:59:00.970 --> 00:59:03.060
a possible child of the string.
00:59:03.060 --> 00:59:07.010
And I only established an edge,
a directed edge from string v1
00:59:07.010 --> 00:59:13.120
to string v2 if string v2
believes that its father is v1,
00:59:13.120 --> 00:59:18.640
and v1 believes that
its child is v2.
00:59:18.640 --> 00:59:22.760
If they agree on their sort
of parenthood relationship,
00:59:22.760 --> 00:59:25.720
I add this edge.
00:59:25.720 --> 00:59:27.710
OK?
00:59:27.710 --> 00:59:31.560
Now you may ask
me, what the heck?
00:59:31.560 --> 00:59:34.470
Why didn't you just define
this graph in a different way?
00:59:34.470 --> 00:59:36.450
Why did you have to
have this possible child
00:59:36.450 --> 00:59:39.700
and possible father
relationship and describe
00:59:39.700 --> 00:59:41.400
the graph in this way?
00:59:41.400 --> 00:59:42.890
And the answer to
this question is
00:59:42.890 --> 00:59:48.340
that no matter-- so the
answer to this question
00:59:48.340 --> 00:59:51.410
is, no matter what
circuit you give me,
00:59:51.410 --> 00:59:54.990
that always defines your graph
with a very specific property
00:59:54.990 --> 00:59:56.820
that we're going to
see in the next slide.
00:59:56.820 --> 01:00:02.030
01:00:02.030 --> 01:00:03.270
Back to the definition.
01:00:03.270 --> 01:00:05.353
So I'm going to explain
the intuition behind this.
01:00:05.353 --> 01:00:07.480
But back to the
definition, describe
01:00:07.480 --> 01:00:11.670
an exponentially large graph
by giving these two circuits.
01:00:11.670 --> 01:00:13.590
And I establish the
edges between nodes
01:00:13.590 --> 01:00:16.340
only if this condition is true.
01:00:16.340 --> 01:00:18.720
And what I'll ask you
to do is the following.
01:00:18.720 --> 01:00:24.670
Given these two circuits, if
the all 0 string is unbalanced
01:00:24.670 --> 01:00:28.616
and gives an exponentially
large graph that I defined,
01:00:28.616 --> 01:00:31.930
then I'll ask you to find
another unbalanced node, which
01:00:31.930 --> 01:00:36.400
by parity exists.
01:00:36.400 --> 01:00:41.970
If the 0 string is unbalanced in
this exponentially large graph,
01:00:41.970 --> 01:00:43.680
then by parity
argument, there must
01:00:43.680 --> 01:00:45.397
be another unbalanced node.
01:00:45.397 --> 01:00:46.480
I'm asking you to find it.
01:00:46.480 --> 01:00:50.190
That's the definition of
this end of the line problem.
01:00:50.190 --> 01:00:52.490
And PPAD is the
class of all problems
01:00:52.490 --> 01:00:55.770
that are in FNP
that are poly-time
01:00:55.770 --> 01:00:59.590
reducible to this problem.
01:00:59.590 --> 01:01:00.870
Now this sounds weird.
01:01:00.870 --> 01:01:05.320
So let me show you how the graph
defined by these two circuits
01:01:05.320 --> 01:01:05.964
looks like.
01:01:05.964 --> 01:01:09.510
01:01:09.510 --> 01:01:11.010
And this will be
hopefully familiar.
01:01:11.010 --> 01:01:13.860
01:01:13.860 --> 01:01:16.820
So I'm copying here the
condition for putting
01:01:16.820 --> 01:01:20.000
an edge between two strings.
01:01:20.000 --> 01:01:23.530
The set of things I'm
looking at is 0, 1 to the n.
01:01:23.530 --> 01:01:26.620
This is the condition for when
I put an edge from string v1
01:01:26.620 --> 01:01:29.590
to string v2.
01:01:29.590 --> 01:01:33.300
Now notice that by
definition, every string
01:01:33.300 --> 01:01:36.290
has at most one possible child.
01:01:36.290 --> 01:01:40.320
And every string has at
most one possible father.
01:01:40.320 --> 01:01:44.350
So the in degrees and
out degrees of this graph
01:01:44.350 --> 01:01:45.510
are at most 1.
01:01:45.510 --> 01:01:49.180
01:01:49.180 --> 01:01:53.160
So I'm implicitly describing
a graph that looks like this.
01:01:53.160 --> 01:01:55.510
And what I ask you to do
is to check the following.
01:01:55.510 --> 01:01:58.880
I ask you to check
if 0, the 0 string,
01:01:58.880 --> 01:02:03.500
is unbalanced, meaning it either
has a father but not a child.
01:02:03.500 --> 01:02:07.080
Or it has a child
but not a father.
01:02:07.080 --> 01:02:10.790
If it's balanced, you
don't need to do any work.
01:02:10.790 --> 01:02:13.630
But if it's unbalanced, which
is easy to check locally--
01:02:13.630 --> 01:02:17.270
you just query the candidate
next child and check
01:02:17.270 --> 01:02:23.190
if that child believes that 0
is its father or vice versa.
01:02:23.190 --> 01:02:26.950
If 0 to the n is
unbalanced, then by parity,
01:02:26.950 --> 01:02:28.400
because the graph
looks like this,
01:02:28.400 --> 01:02:31.430
there must be some other
unbalanced vertex, at least
01:02:31.430 --> 01:02:32.320
one.
01:02:32.320 --> 01:02:33.695
And I'm asking
you to find me any
01:02:33.695 --> 01:02:35.570
of these unbalanced vertices.
01:02:35.570 --> 01:02:38.890
So in particular, you don't need
to find the unbalanced vertex
01:02:38.890 --> 01:02:42.475
that's in the other end of the
path that starts at 0 to the n
01:02:42.475 --> 01:02:45.214
or finishes at 0 to the n.
01:02:45.214 --> 01:02:47.380
You can give me any of the
other unbalanced vertices
01:02:47.380 --> 01:02:48.730
if there are any.
01:02:48.730 --> 01:02:50.260
But by parity, I
know that there is
01:02:50.260 --> 01:02:54.000
at least one unbalanced vertex.
01:02:54.000 --> 01:02:56.150
So PPAD is this problem.
01:02:56.150 --> 01:02:59.230
I describe an
exponentially large graph
01:02:59.230 --> 01:03:02.330
by giving you two circuits.
01:03:02.330 --> 01:03:05.370
Now no matter what
circuits I gave you,
01:03:05.370 --> 01:03:06.802
I know the graph
looks like this.
01:03:06.802 --> 01:03:09.510
01:03:09.510 --> 01:03:12.930
Now in this graph, if 0
to the n is unbalanced--
01:03:12.930 --> 01:03:14.720
if a 0 string is
unbalanced, you know
01:03:14.720 --> 01:03:17.240
that there must be
another unbalanced vertex.
01:03:17.240 --> 01:03:20.330
Any of them is good as a
solution to the problem.
01:03:20.330 --> 01:03:21.490
Yeah?
01:03:21.490 --> 01:03:23.720
AUDIENCE: So how then do
we know that 0 to the n
01:03:23.720 --> 01:03:26.360
doesn't point to a
previous other string that
01:03:26.360 --> 01:03:28.660
points to 0 to the n?
01:03:28.660 --> 01:03:30.360
How do we know that 0 to the n--
01:03:30.360 --> 01:03:32.790
CONSTANTINOS DASKALAKIS: So
in that-- no, it can happen.
01:03:32.790 --> 01:03:36.560
It could be that
this is 0 to the n.
01:03:36.560 --> 01:03:44.230
It has a child that believes
that this is its father.
01:03:44.230 --> 01:03:48.610
And also, v believes that
0 to the n is its child.
01:03:48.610 --> 01:03:51.720
And 0 to the n believes
that this is the father.
01:03:51.720 --> 01:03:54.780
This creates a 0 to the
n which is balanced.
01:03:54.780 --> 01:03:58.104
In that case, you don't
need to do any work.
01:03:58.104 --> 01:03:59.520
So the statement
of the problem is
01:03:59.520 --> 01:04:04.570
asking you to do work only
if 0 to the n is unbalanced.
01:04:04.570 --> 01:04:07.950
So end of the line
tells you if 0 to the n
01:04:07.950 --> 01:04:10.840
is unbalanced, which you can
trivially check locally-- you
01:04:10.840 --> 01:04:13.020
don't need to look
at the whole graph
01:04:13.020 --> 01:04:17.480
to decide whether 0 to
the n is balanced or not.
01:04:17.480 --> 01:04:20.450
So to decide whether 0
to the n is balanced,
01:04:20.450 --> 01:04:21.670
you need four queries.
01:04:21.670 --> 01:04:24.807
AUDIENCE: Couldn't you have
an exponentially long segment?
01:04:24.807 --> 01:04:26.640
CONSTANTINOS DASKALAKIS:
Yeah, but the point
01:04:26.640 --> 01:04:28.090
is-- that's the whole point.
01:04:28.090 --> 01:04:33.336
So if I query-- if v--
01:04:33.336 --> 01:04:34.330
AUDIENCE: I see.
01:04:34.330 --> 01:04:37.380
CONSTANTINOS DASKALAKIS: is the
possible parent of 0 to the n,
01:04:37.380 --> 01:04:46.750
and u is the possible
child of 0 to the n,
01:04:46.750 --> 01:04:49.330
then the state of the
world could be this.
01:04:49.330 --> 01:04:54.500
01:04:54.500 --> 01:04:55.580
It could be this.
01:04:55.580 --> 01:05:00.290
Now if also this guy believes
that 0 to the n is his father,
01:05:00.290 --> 01:05:03.070
I'm going to make
this edge solid.
01:05:03.070 --> 01:05:05.940
That's the fourth query I'm
going to make to my circuits.
01:05:05.940 --> 01:05:09.720
If this guy believes that
0 to the n is his father,
01:05:09.720 --> 01:05:12.180
I'm going to also
make this edge solid.
01:05:12.180 --> 01:05:15.210
If both are solid, then
0 to the n is balanced.
01:05:15.210 --> 01:05:17.180
I don't need to do any work.
01:05:17.180 --> 01:05:19.650
If this is missing, then
0 to the n unbalanced.
01:05:19.650 --> 01:05:21.890
I need to do work and
so on and so forth.
01:05:21.890 --> 01:05:22.710
OK?
01:05:22.710 --> 01:05:24.835
But with four queries
to my circuits--
01:05:24.835 --> 01:05:26.730
so in polynomial
time in particular
01:05:26.730 --> 01:05:29.430
in the description of my input--
I can decide whether 0 to the n
01:05:29.430 --> 01:05:31.777
is balanced or not.
01:05:31.777 --> 01:05:34.110
And if it's unbalanced, then
I need to do a lot of work.
01:05:34.110 --> 01:05:37.820
And in fact, we have no
better than exponential
01:05:37.820 --> 01:05:40.430
bound for how long it
will take me to find
01:05:40.430 --> 01:05:43.632
the other unbalanced node.
01:05:43.632 --> 01:05:45.757
AUDIENCE: Can you make all
such graphs of this type
01:05:45.757 --> 01:05:49.110
with small circuits?
01:05:49.110 --> 01:05:50.550
CONSTANTINOS DASKALAKIS: Mm-mm.
01:05:50.550 --> 01:05:52.270
I mean, no.
01:05:52.270 --> 01:05:56.390
I mean, you're asking, if I pick
an arbitrary exponential graph,
01:05:56.390 --> 01:06:01.700
if it's always compressible
into polynomial size?
01:06:01.700 --> 01:06:04.170
I mean, it depends on
how phrase the question.
01:06:04.170 --> 01:06:10.260
So if you allow me to get a
huge p-- p is part of the input.
01:06:10.260 --> 01:06:11.630
p is a part of the input.
01:06:11.630 --> 01:06:14.890
So now if p is a
lookup table, that's
01:06:14.890 --> 01:06:17.510
a trivial instance, actually.
01:06:17.510 --> 01:06:20.770
So the instances that
are hard are those
01:06:20.770 --> 01:06:22.640
where p is a succinct thing.
01:06:22.640 --> 01:06:25.612
It's polynomially in n
size but still defines
01:06:25.612 --> 01:06:26.820
an exponentially large graph.
01:06:26.820 --> 01:06:29.310
If p is a huge thing,
a lookup table that
01:06:29.310 --> 01:06:32.140
keeps track of all
connectivities of all vertices
01:06:32.140 --> 01:06:35.310
with each other, we're getting
into algorithms territory,
01:06:35.310 --> 01:06:38.930
where I give you an adjacency
list for every node.
01:06:38.930 --> 01:06:42.470
So this is a purely
algorithmic problem
01:06:42.470 --> 01:06:44.550
that we can trivially solve.
01:06:44.550 --> 01:06:47.770
So if I get into the regime
where my p, my circuit
01:06:47.770 --> 01:06:52.320
description, is polynomial
in the size of the graph,
01:06:52.320 --> 01:06:55.470
that's an easy instance.
01:06:55.470 --> 01:06:57.567
But if you're
asking the question,
01:06:57.567 --> 01:06:59.650
can I always compress an
exponentially large graph
01:06:59.650 --> 01:07:04.180
into two circuits, p and n,
that are polynomial in size,
01:07:04.180 --> 01:07:06.450
then that's not the case.
01:07:06.450 --> 01:07:07.160
OK.
01:07:07.160 --> 01:07:11.130
So PPAD-- notice that this
end of the line problem
01:07:11.130 --> 01:07:15.430
is in FNP because I can just
guess the unbalanced vertex,
01:07:15.430 --> 01:07:17.200
different than the 0 string.
01:07:17.200 --> 01:07:19.930
And I can check
easily if it's also
01:07:19.930 --> 01:07:22.280
unbalanced with four queries.
01:07:22.280 --> 01:07:24.230
So it is in FNP.
01:07:24.230 --> 01:07:29.190
And I hope you believe me
that Sperner isn't PPAD,
01:07:29.190 --> 01:07:31.590
because just the
proof of Sperner
01:07:31.590 --> 01:07:33.690
was exactly the
same kind of thing.
01:07:33.690 --> 01:07:36.260
So I succinctly
described this graph that
01:07:36.260 --> 01:07:38.140
had exactly the same structure.
01:07:38.140 --> 01:07:40.820
So really, what inspired
the definition of this class
01:07:40.820 --> 01:07:44.480
is the proof of Sperner's lemma.
01:07:44.480 --> 01:07:49.820
Now I sort of argued that you
can prove Brouwer via Sperner.
01:07:49.820 --> 01:07:54.399
I gave this hand wave-y, high
level picture showing that.
01:07:54.399 --> 01:07:56.689
And also Nash through Brouwer.
01:07:56.689 --> 01:07:59.890
So in fact, PPAD definitely
contains the problems
01:07:59.890 --> 01:08:02.010
that I'm interested in.
01:08:02.010 --> 01:08:03.102
That was the litmus test.
01:08:03.102 --> 01:08:05.060
The litmus test is I went
through this exercise
01:08:05.060 --> 01:08:08.399
to define this class PPAD
based on the existence
01:08:08.399 --> 01:08:11.740
proof of Sperner's lemma.
01:08:11.740 --> 01:08:14.630
And I successful got all
these interesting problems
01:08:14.630 --> 01:08:16.399
inside PPAD.
01:08:16.399 --> 01:08:23.250
But the litmus test is--
the success of my exercise
01:08:23.250 --> 01:08:28.310
is whether I get also
tight reductions.
01:08:28.310 --> 01:08:31.270
So if I also get that
these problems are
01:08:31.270 --> 01:08:33.010
as hard as any other
problem in PPAD,
01:08:33.010 --> 01:08:36.010
now I can call my
thing successful.
01:08:36.010 --> 01:08:40.910
So in particular, as an
example, the definition of NP
01:08:40.910 --> 01:08:44.729
is that SAT is NP complete.
01:08:44.729 --> 01:08:48.350
So NP was defined
with SAT in mind.
01:08:48.350 --> 01:08:51.140
01:08:51.140 --> 01:08:53.930
But it also captured exactly
the complexity of SAT.
01:08:53.930 --> 01:08:55.520
So that was a
successful definition
01:08:55.520 --> 01:08:57.120
of a complexity class.
01:08:57.120 --> 01:09:00.490
So the litmus test for this
exercise that I went through
01:09:00.490 --> 01:09:03.445
with you is whether
actually those problems
01:09:03.445 --> 01:09:07.160
that I'm interested in
are also PPAD complete.
01:09:07.160 --> 01:09:11.779
So what we showed with
Goldberg and Papadimitriou
01:09:11.779 --> 01:09:14.340
a bunch of-- I guess
10 years ago almost--
01:09:14.340 --> 01:09:18.020
is that actually the opposite
reductions are also true,
01:09:18.020 --> 01:09:23.040
that all these problems are
computationally equivalent.
01:09:23.040 --> 01:09:27.330
In fact, I didn't show that
these are equivalent to PPAD.
01:09:27.330 --> 01:09:28.700
These were already known.
01:09:28.700 --> 01:09:31.200
These results were already
known since Papadimitriou's
01:09:31.200 --> 01:09:34.280
original paper,
that PPAD exactly
01:09:34.280 --> 01:09:37.610
is equivalent to
Sperner and Brouwer.
01:09:37.610 --> 01:09:39.360
What we show together
is that Nash also
01:09:39.360 --> 01:09:41.899
is equivalent, is in the
same league of problems,
01:09:41.899 --> 01:09:43.940
basically establishing
that all of these problems
01:09:43.940 --> 01:09:45.287
are computationally equivalent.
01:09:45.287 --> 01:09:47.620
Finding a Nash equilibrium
is a computational equivalent
01:09:47.620 --> 01:09:50.230
to Sperner's lemma,
computationally equivalent
01:09:50.230 --> 01:09:53.850
to any problem in PPAD
and so on and so forth.
01:09:53.850 --> 01:09:57.290
And the high level
of the reduction--
01:09:57.290 --> 01:09:59.300
I'm going to hand
wave about it--
01:09:59.300 --> 01:10:03.250
is that we started this
generic PPAD instance.
01:10:03.250 --> 01:10:07.430
And what we do is we envision
embedding this instance
01:10:07.430 --> 01:10:09.050
into some geometry.
01:10:09.050 --> 01:10:12.600
01:10:12.600 --> 01:10:14.570
Because this a
combinatorial problem,
01:10:14.570 --> 01:10:16.410
our goal eventually
is to reduce it
01:10:16.410 --> 01:10:22.450
to Brouwer and to Nash, which
are continuous problems.
01:10:22.450 --> 01:10:26.030
So the first thing we did is
we embed this graph into a cube
01:10:26.030 --> 01:10:29.570
in a way that's sort of like
every path or cycle corresponds
01:10:29.570 --> 01:10:36.450
to a path that moves
around this cube
01:10:36.450 --> 01:10:38.260
without intersecting itself.
01:10:38.260 --> 01:10:39.990
So this is the
first thing we do.
01:10:39.990 --> 01:10:46.660
Then we find a way to solve
the resulting embedded PPAD
01:10:46.660 --> 01:10:52.350
instance, reduce it to
a Sperner's instance.
01:10:52.350 --> 01:10:55.170
And then in fact, the
core of the proof--
01:10:55.170 --> 01:10:58.820
and I'm going to actually
talk about this more--
01:10:58.820 --> 01:11:04.870
is to reduce this problem
into a problem that
01:11:04.870 --> 01:11:09.580
asks you to evaluate
an arithmetic circuit.
01:11:09.580 --> 01:11:13.740
Now after you get that PPAD
reduces to this evaluation
01:11:13.740 --> 01:11:18.620
problem, it's really-- I call it
approximate arithmetic circuit
01:11:18.620 --> 01:11:19.630
SAT.
01:11:19.630 --> 01:11:21.760
So I'm going to get
into what this means.
01:11:21.760 --> 01:11:24.490
But it's really a
satisfiability problem
01:11:24.490 --> 01:11:25.970
for arithmetic circuits.
01:11:25.970 --> 01:11:29.630
But after you get PPAD to
reduce to this problem,
01:11:29.630 --> 01:11:34.380
it's easy to get to Nash and
all the other implications,
01:11:34.380 --> 01:11:38.320
all the other known PPAD
completeness reductions
01:11:38.320 --> 01:11:40.460
that people have established.
01:11:40.460 --> 01:11:43.560
So what I want to describe is
what this problem is about.
01:11:43.560 --> 01:11:46.590
01:11:46.590 --> 01:11:51.460
It's the equivalent of circuit
SAT, which is NP complete.
01:11:51.460 --> 01:11:54.350
This is called
arithmetic circuit SATs,
01:11:54.350 --> 01:11:56.720
and I'm going to show
you what it means.
01:11:56.720 --> 01:11:57.380
Question?
01:11:57.380 --> 01:12:00.270
AUDIENCE: So in the
course of this reduction,
01:12:00.270 --> 01:12:03.110
do we get to replay
our game for Nash,
01:12:03.110 --> 01:12:05.220
like does this three
carry through to the--
01:12:05.220 --> 01:12:05.680
CONSTANTINOS DASKALAKIS: Yes.
01:12:05.680 --> 01:12:07.013
So you get actually two players.
01:12:07.013 --> 01:12:08.784
You can get two player Nash.
01:12:08.784 --> 01:12:09.720
Yeah.
01:12:09.720 --> 01:12:12.810
So it establishes
that all games are--
01:12:12.810 --> 01:12:14.520
if they're not two
player zero-sum,
01:12:14.520 --> 01:12:16.620
they are PPAD complete.
01:12:16.620 --> 01:12:20.650
So the input to the
problem is a circuit.
01:12:20.650 --> 01:12:24.310
The circuit comprises two
kinds of nodes, viable nodes
01:12:24.310 --> 01:12:26.060
and gates.
01:12:26.060 --> 01:12:29.820
So gates are represented
with solid circles.
01:12:29.820 --> 01:12:35.730
Viable nodes are with-- I
don't know-- empty circles.
01:12:35.730 --> 01:12:37.790
So the viable nodes
are x1 through xn.
01:12:37.790 --> 01:12:40.550
The gate's nodes
are g1 through gm.
01:12:40.550 --> 01:12:44.730
Now the gates can--
I can choose gates
01:12:44.730 --> 01:12:49.090
from the following
set of possible gates.
01:12:49.090 --> 01:12:52.390
I'm going to explain what
these gates are meant to do.
01:12:52.390 --> 01:12:53.880
But this is an assignment gate.
01:12:53.880 --> 01:12:55.640
This is a plus addition gate.
01:12:55.640 --> 01:12:57.600
This is a subtraction gate.
01:12:57.600 --> 01:13:00.950
This is set equal
to a constant gate.
01:13:00.950 --> 01:13:04.930
This is times a constant gate,
and this is a comparison gate.
01:13:04.930 --> 01:13:07.610
The subtraction and
comparison gates
01:13:07.610 --> 01:13:09.100
are non-symmetric
in their inputs.
01:13:09.100 --> 01:13:12.660
So they have a special input
1 and a special input 2,
01:13:12.660 --> 01:13:16.600
similarly for the
comparison gate.
01:13:16.600 --> 01:13:19.520
And I also have directed
edges that connect variables
01:13:19.520 --> 01:13:21.250
to gates and vice versa.
01:13:21.250 --> 01:13:23.410
But there are no edges
between variables.
01:13:23.410 --> 01:13:26.130
So there are no edges
between the gates.
01:13:26.130 --> 01:13:27.990
And also, the loops are allowed.
01:13:27.990 --> 01:13:28.890
That's important.
01:13:28.890 --> 01:13:29.940
So you can have loops.
01:13:29.940 --> 01:13:31.315
For example, in
this picture, you
01:13:31.315 --> 01:13:33.520
have a loop between vertices.
01:13:33.520 --> 01:13:36.770
And actually, there are
no inputs to the circuit.
01:13:36.770 --> 01:13:39.410
In circuit SAT, you
want to set the input
01:13:39.410 --> 01:13:40.669
so that the output is 1.
01:13:40.669 --> 01:13:41.710
And you don't have loops.
01:13:41.710 --> 01:13:42.780
You have a DAG.
01:13:42.780 --> 01:13:45.380
And your gates are
just binary gates.
01:13:45.380 --> 01:13:47.440
Here we're in a
different situation.
01:13:47.440 --> 01:13:49.530
We don't have inputs.
01:13:49.530 --> 01:13:51.812
Our gates can have loops.
01:13:51.812 --> 01:13:52.770
And they're not binary.
01:13:52.770 --> 01:13:55.320
They're arithmetic gates.
01:13:55.320 --> 01:14:03.940
The goal is to assign 0,
1 values to the variables
01:14:03.940 --> 01:14:06.950
so that the gate
constraints are satisfied.
01:14:06.950 --> 01:14:09.510
So now what are the
gate constraints?
01:14:09.510 --> 01:14:11.810
So the output of
an assignment gate
01:14:11.810 --> 01:14:15.890
should equal the input
to the assignment gate.
01:14:15.890 --> 01:14:19.750
If we have an addition gate,
the output of the addition gate
01:14:19.750 --> 01:14:24.090
should be the sum of the
inputs, except everything
01:14:24.090 --> 01:14:25.110
should line 0, 1.
01:14:25.110 --> 01:14:29.140
So it's the minimum between
the sum of inputs and 1.
01:14:29.140 --> 01:14:32.020
01:14:32.020 --> 01:14:33.600
The subtraction gate is similar.
01:14:33.600 --> 01:14:35.600
So the output to
the subtraction gate
01:14:35.600 --> 01:14:38.140
is the difference of the inputs.
01:14:38.140 --> 01:14:41.730
But you can't go below 0.
01:14:41.730 --> 01:14:45.900
The set equal gate is-- set
equal to a constant gate
01:14:45.900 --> 01:14:48.580
is sets y to ba.
01:14:48.580 --> 01:14:53.500
But it doesn't allow
it to leave 0, 1.
01:14:53.500 --> 01:14:56.650
And then multiply by
constant gate multiplies
01:14:56.650 --> 01:14:58.650
the input with alpha, with a.
01:14:58.650 --> 01:15:04.230
But also it doesn't allow
it to go below 0 or above 1.
01:15:04.230 --> 01:15:08.780
And these are pretty
straightforward.
01:15:08.780 --> 01:15:10.830
What is slightly weird
is the comparison gate,
01:15:10.830 --> 01:15:13.300
which has a weird
behavior and actually must
01:15:13.300 --> 01:15:15.960
have this behavior for the
problem to be PPAD complete.
01:15:15.960 --> 01:15:17.710
You can show that.
01:15:17.710 --> 01:15:21.940
The comparison
gate has to be a 1.
01:15:21.940 --> 01:15:24.372
The output has to be a
1 if the first input is
01:15:24.372 --> 01:15:25.580
bigger than the second input.
01:15:25.580 --> 01:15:28.655
It has to be a 0 if this
first input is smaller.
01:15:28.655 --> 01:15:30.960
But if they're equal,
it can be anything.
01:15:30.960 --> 01:15:33.352
It's allowed to be anything.
01:15:33.352 --> 01:15:35.560
Actually, if you think about
it as a continuous gate,
01:15:35.560 --> 01:15:39.280
it cannot just jump from 0 to 1
without being able to take all
01:15:39.280 --> 01:15:43.010
the intermediate values.
01:15:43.010 --> 01:15:43.999
OK?
01:15:43.999 --> 01:15:44.790
It can be anything.
01:15:44.790 --> 01:15:46.664
Any value is allowed if
the inputs are equal.
01:15:46.664 --> 01:15:49.140
01:15:49.140 --> 01:15:54.670
So that's the
arithmetic circuit SAT
01:15:54.670 --> 01:15:58.250
problem that is PPAD complete.
01:15:58.250 --> 01:16:00.650
First of all, this
problem is total.
01:16:00.650 --> 01:16:03.080
No matter what circuit
you write down,
01:16:03.080 --> 01:16:04.850
I can prove to you
that there is always
01:16:04.850 --> 01:16:07.620
an evaluation that works.
01:16:07.620 --> 01:16:09.230
That's not a priori obvious.
01:16:09.230 --> 01:16:11.670
It's not a priori obvious
that no matter what
01:16:11.670 --> 01:16:14.770
circuit I describe
using these gates
01:16:14.770 --> 01:16:17.900
has a satisfying assignment.
01:16:17.900 --> 01:16:19.227
But I claim this is true.
01:16:19.227 --> 01:16:20.560
I'm not going to show it to you.
01:16:20.560 --> 01:16:22.100
It is true though.
01:16:22.100 --> 01:16:25.450
And it must be true because this
problem belongs in this family
01:16:25.450 --> 01:16:26.660
of PPAD complete problems.
01:16:26.660 --> 01:16:29.410
So it has to also inherit
all the properties
01:16:29.410 --> 01:16:32.500
that this class of
problems shares.
01:16:32.500 --> 01:16:34.590
Now let's try to
work out the details
01:16:34.590 --> 01:16:37.650
of what the computation is.
01:16:37.650 --> 01:16:38.150
OK.
01:16:38.150 --> 01:16:44.220
So I want to argue
that in this-- I
01:16:44.220 --> 01:16:47.390
want to claim that the only
satisfying assignment is
01:16:47.390 --> 01:16:51.610
that everything is
equal to 1/2 actually.
01:16:51.610 --> 01:16:54.220
And let's try to verify it.
01:16:54.220 --> 01:16:59.460
So suppose that a was
not-- actually, no.
01:16:59.460 --> 01:17:01.460
I take that back.
01:17:01.460 --> 01:17:07.630
So a must be 1/2, and b can be--
no, actually they're all 1/2.
01:17:07.630 --> 01:17:08.700
Sorry, sorry.
01:17:08.700 --> 01:17:10.046
They're all 1/2.
01:17:10.046 --> 01:17:11.040
I don't take it back.
01:17:11.040 --> 01:17:12.400
So let me try to argue that.
01:17:12.400 --> 01:17:16.350
So suppose that a
was bigger than 1/2.
01:17:16.350 --> 01:17:18.010
So c must be 1/2, right?
01:17:18.010 --> 01:17:20.760
That's by the
condition of the gate.
01:17:20.760 --> 01:17:22.550
This is set equal to 1/2.
01:17:22.550 --> 01:17:24.130
So this must be 1/2.
01:17:24.130 --> 01:17:26.260
That's obvious.
01:17:26.260 --> 01:17:30.840
Now I claim that a cannot
be bigger than 1/2.
01:17:30.840 --> 01:17:35.920
If a was bigger
than 1/2, then this
01:17:35.920 --> 01:17:38.360
is bigger than this input
of the comparison gate.
01:17:38.360 --> 01:17:41.390
So the comparison
gate would output a 0.
01:17:41.390 --> 01:17:43.330
But this set equal
operation would
01:17:43.330 --> 01:17:45.500
have to set this guy to be 0.
01:17:45.500 --> 01:17:47.280
So 0 can't be bigger than 1/2.
01:17:47.280 --> 01:17:49.850
01:17:49.850 --> 01:17:51.610
Let's do the other direction.
01:17:51.610 --> 01:17:54.200
Suppose a was smaller than 1/2.
01:17:54.200 --> 01:17:57.420
If a was smaller than 1/2,
then the comparison gate
01:17:57.420 --> 01:17:58.750
would [INAUDIBLE] 1.
01:17:58.750 --> 01:18:00.520
This would set it to 1.
01:18:00.520 --> 01:18:02.890
So how can 1 be
smaller than 1/2?
01:18:02.890 --> 01:18:06.100
So the only possibility
is that it's actually 1/2.
01:18:06.100 --> 01:18:11.274
And if it's 1/2 and 1/2,
then it's setting 1/2.
01:18:11.274 --> 01:18:13.440
Because the inputs are equal
to the comparison gate,
01:18:13.440 --> 01:18:15.420
you can set this to be anything.
01:18:15.420 --> 01:18:17.710
So everything being 1/2
satisfies all the conditions
01:18:17.710 --> 01:18:19.330
of the gates.
01:18:19.330 --> 01:18:22.340
So that's the problem
we're trying to solve.
01:18:22.340 --> 01:18:26.770
make The claim is that this
problem is PPAD complete.
01:18:26.770 --> 01:18:30.100
And this problem is going to
be the starting point for all
01:18:30.100 --> 01:18:34.050
our reduction next time, in
particular showing that Nash's
01:18:34.050 --> 01:18:38.910
theorem is PPAD complete.
01:18:38.910 --> 01:18:41.560
I want to add the last point.
01:18:41.560 --> 01:18:44.620
After we published our
paper, Chen, Deng, and Teng
01:18:44.620 --> 01:18:51.480
actually improved these
results to fuzzy gates.
01:18:51.480 --> 01:18:55.720
So they-- actually, we
allowed in our original paper
01:18:55.720 --> 01:18:58.780
exponential noise in
the outputs of the gate.
01:18:58.780 --> 01:19:01.730
So this is an
easier problem now.
01:19:01.730 --> 01:19:02.780
So I give you a circuit.
01:19:02.780 --> 01:19:05.690
And I want you to find me
an assignment that satisfies
01:19:05.690 --> 01:19:07.600
all gates approximately.
01:19:07.600 --> 01:19:09.750
So now in the original
paper, we could accommodate
01:19:09.750 --> 01:19:13.420
exponential noise in
the size of the input
01:19:13.420 --> 01:19:14.910
and the fuzziness of the gates.
01:19:14.910 --> 01:19:17.340
These guys showed
that you can even
01:19:17.340 --> 01:19:21.170
accommodate any polynomial
noise, inverse polynomial noise
01:19:21.170 --> 01:19:22.420
that you want.
01:19:22.420 --> 01:19:24.220
And it's still PPAD complete.
01:19:24.220 --> 01:19:27.981
That's an easier problem than
the exact problem obviously.
01:19:27.981 --> 01:19:29.480
But in fact, they're
computationally
01:19:29.480 --> 01:19:32.000
equivalent because they're
both PPAD complete.
01:19:32.000 --> 01:19:33.909
So now next time,
what I'm going to show
01:19:33.909 --> 01:19:36.450
is I'm going to use this problem
to show that Nash and market
01:19:36.450 --> 01:19:38.600
equilibrium are PPAD complete.
01:19:38.600 --> 01:19:41.640
I'm going to show that some
problems in combinatorics,
01:19:41.640 --> 01:19:45.725
such as fractional hypergraph
matching and Scarf's lemma
01:19:45.725 --> 01:19:47.170
are PPAD complete.
01:19:47.170 --> 01:19:49.090
And then if we have
time, I'm going
01:19:49.090 --> 01:19:52.000
to show you other
existence arguments that
01:19:52.000 --> 01:19:57.880
give rise to different
interesting complexity classes.
01:19:57.880 --> 01:19:59.810
AUDIENCE: Named
after Papadimitriou?
01:19:59.810 --> 01:19:59.880
CONSTANTINOS DASKALAKIS: Yeah.
01:19:59.880 --> 01:20:00.810
Many people ask that.
01:20:00.810 --> 01:20:03.660
So it means polynomial parity
argument of directed graphs.
01:20:03.660 --> 01:20:07.122
01:20:07.122 --> 01:20:08.080
That's a good question.
01:20:08.080 --> 01:20:08.580
Yeah.
01:20:08.580 --> 01:20:11.620
I should have said that.
01:20:11.620 --> 01:20:12.120
OK.
01:20:12.120 --> 01:20:14.220
Thanks a lot.
01:20:14.220 --> 01:20:17.270
[APPLAUSE]