MIT 6.S890 — Topics in Multiagent Learning Thu, Nov 21st 2024
Lecture 18
PPAD-completeness of Nash equilibria (Part II)
Instructor: Prof. Gabriele Farina ( gfarina@mit.edu)★
We conclude the journey we started in Lecture 17 by giving a glimpse of how the PPAD-hardness of
finding 𝜖-approximate Nash equilibria was shown by Daskalakis, C., Goldberg, P. W., & Papadim-
itriou, C. H. [DGP09].
The proof can be broken down into two main steps:
• Reduction from the End-of-the-line problem to (approximate) Brouwer.
• Reduction from (approximate) Brouwer to (approximate) Nash equilibria.
The first step is relatively easy, and we will not cover it here. The second step is more involved and
requires a careful construction of a reduction from Brouwer to Nash equilibria. This is the part we
will focus on in this lecture.
The key idea is the following: in the reduction from End-of-the-line to Brouwer, we have defined
somewhere a function continuous 𝑓 for which we need to find an approximate fixed point. We now
need that we can construct a game such that a Nash equilibrium of the game is the same as a fixed
point of 𝑓 (up to approximations). The issue is that it is not clear how we can have games “compute”
functions. Can we construct games in such a way that their behavior at Nash equilibria can be seen
as “computing something”? The answer is positive, as we see next.
1 Arithmetic Circuit SAT
We show that given a function represented as an arithmetic circuit, it is possible to construct a game
whose Nash equilibria correspond to computing a fixed point of the function. This is the key idea
behind the reduction from Brouwer to Nash equilibria.
In particular, we will restrict our attention to functions constructed through circuits that are
composed of the following:
• Variable nodes 𝑣1, ..., 𝑣𝑛;
• Gate nodes 𝑔1, ..., 𝑔𝑚 of six possible types:
Gate Symbol Input-output relationship
Assignment ≔ 𝑦𝑥1 𝑦 = 𝑥1
Constant 𝑎 𝑦 𝑦 = 𝑎
Addition + 𝑦
𝑥1
𝑥2
𝑦 = min{1, 𝑥1 + 𝑥2}
Subtraction − 𝑦
𝑥1
𝑥2
𝑦 = max{0, 𝑥1 − 𝑥2}
Multiplication ×𝑎 𝑦𝑥1 𝑦 = max{0, min{1, 𝑎 ⋅ 𝑥1}}
Comparison > 𝑦
𝑥1
𝑥2
𝑦 =
{
{
{
{
{1, if 𝑥1 > 𝑥2
0, if 𝑥1 < 𝑥2
any, if 𝑥1 = 𝑥2.
This gate does not restrict the output when
𝑥1 = 𝑥2.
• Directed edges connecting variables to gates and gates to variables (loops are allowed);
• Variable nodes have in-degree 1; gates have 0, 1, or 2 inputs depending on type as above; gates
& nodes have arbitrary fanout.
Definition 1.1 (Arithmetic Circuit SAT problem). Given an arithmetic circuit satisfying the
description above, output an assignment of values 𝑣1, ..., 𝑣𝑛 ∈ [0, 1] that satisfies all the gates.
Example 1.1. Consider the following diagram.
1
2 > ≔
𝑎𝑐
𝑏
The only satisfying assignment is 𝑎 = 𝑏 = 𝑐 = 1/2.
It is easy to see that this problem has the flavor of a Brouwer fixed point.
Theorem 1.1 ([DGP09]). The Arithmetic Circuit SAT problem always admits a solution, and
it is PPAD-complete to find it.
2 From gates to games
It is possible to convert an Arithmetic Circuit SAT instance into a Nash equilibrium computation
problem in a multiplayer game. (The game can also be converted into a two-player [CDT09] or three-
player game [DGP09], but we do not show how in this lecture).
The idea is to use gadgets: constructions that simulate the behavior of the gates in the circuit.
2.1 Addition gate
Consider any game that contains the following interaction between four players 𝑥, 𝑦, 𝑧, 𝑤, each of
which has two actions, denoted {0, 1}. With a slight abuse of notation, we will call 𝑥, 𝑦, 𝑧, 𝑤 the
probability of playing action 1; hence, 𝑥, 𝑦, 𝑧, 𝑤 ∈ [0, 1].
Example 2.1 (Addition gadget game). Consider any game that contains as a substructure the
gadget shown in the diagram below, and payoffs set as follows.
▶ Payoffs of player 𝑤. The payoff of player 𝑤 is defined
as follows. If 𝑤 plays 0, her payoff does not depend on 𝑧’s
strategy, but only on 𝑥 and 𝑦, according to the payoff table
𝑦 = 0 𝑦 = 1
𝑥 = 0 0 1
𝑥 = 1 1 2
If 𝑤 plays 1, her payoff does not depend on 𝑥 and 𝑦’s
strategy and depends on 𝑧’s according to the table
𝑧 = 0 𝑧 = 1
0 1
▶ Payoffs of player 𝑧. The payoff of player 𝑧 is defined
according to the table
𝑧 = 0 𝑧 = 1
𝑤 = 0 1/2 1
𝑤 = 1 1/2 0
𝑥 𝑦
𝑤
𝑧
Figure 2: Addition gadget game.
The dashed blue edges denote pos-
sible edges in the games, which do
not affect the result in Theorem 2.1.
▶ Other payoffs and considerations. Players 𝑥 and 𝑦 utilities are independent on the strategies
of 𝑤 and 𝑧. Player 𝑤 does not affect other players in the game.
Theorem 2.1. In all Nash equilibria of the game, 𝑧 = min{𝑥 + 𝑦, 1}.
Proof . Suppose that 𝑧 < min{𝑥 + 𝑦, 1}. Then, 𝑧 < 𝑥 + 𝑦. But then 𝑤 will deterministicaly play
𝑤 = 0, which will force 𝑧 to play 𝑧 = 1. This is a contradiction, since by hypothesis 𝑧 < min{𝑥 +
𝑦, 1}, which implies 𝑧 < 1.
Suppose now that 𝑧 > min{𝑥 + 𝑦, 1}. In this case, min{𝑥 + 𝑦, 1} ≠ 1, as otherwise this would
imply 𝑧 > 1 which is impossible. Thus, 𝑧 > 𝑥 + 𝑦. This implies 𝑤 = 1 and hence 𝑧 = 0, which is
again impossible since 𝑧 > 𝑥 + 𝑦, which implies 𝑧 > 0.
The only remaining possibility is therefore 𝑧 = min{𝑥 + 𝑦, 1}, as we wanted to show. □
Bibliography
[DGP09] C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou, “The Complexity of Computing
a Nash Equilibrium,” SIAM Journal on Computing, vol. 39, no. 1, pp. 195–259, 2009,
doi: 10.1137/070699652.
[CDT09] X. Chen, X. Deng, and S.-H. Teng, “Settling the complexity of computing two-player Nash
equilibria,” Journal of the ACM (JACM), vol. 56, no. 3, pp. 1–57, 2009.
★These notes are class material that has not undergone formal peer review. The TA and I are grateful for any
reports of typos. Some of the content of the lecture was adapted from material from Costis Daskalakis.
Lecture 18
PPAD-completeness of Nash equilibria (Part II)
Instructor: Prof. Gabriele Farina ( gfarina@mit.edu)★
We conclude the journey we started in Lecture 17 by giving a glimpse of how the PPAD-hardness of
finding 𝜖-approximate Nash equilibria was shown by Daskalakis, C., Goldberg, P. W., & Papadim-
itriou, C. H. [DGP09].
The proof can be broken down into two main steps:
• Reduction from the End-of-the-line problem to (approximate) Brouwer.
• Reduction from (approximate) Brouwer to (approximate) Nash equilibria.
The first step is relatively easy, and we will not cover it here. The second step is more involved and
requires a careful construction of a reduction from Brouwer to Nash equilibria. This is the part we
will focus on in this lecture.
The key idea is the following: in the reduction from End-of-the-line to Brouwer, we have defined
somewhere a function continuous 𝑓 for which we need to find an approximate fixed point. We now
need that we can construct a game such that a Nash equilibrium of the game is the same as a fixed
point of 𝑓 (up to approximations). The issue is that it is not clear how we can have games “compute”
functions. Can we construct games in such a way that their behavior at Nash equilibria can be seen
as “computing something”? The answer is positive, as we see next.
1 Arithmetic Circuit SAT
We show that given a function represented as an arithmetic circuit, it is possible to construct a game
whose Nash equilibria correspond to computing a fixed point of the function. This is the key idea
behind the reduction from Brouwer to Nash equilibria.
In particular, we will restrict our attention to functions constructed through circuits that are
composed of the following:
• Variable nodes 𝑣1, ..., 𝑣𝑛;
• Gate nodes 𝑔1, ..., 𝑔𝑚 of six possible types:
Gate Symbol Input-output relationship
Assignment ≔ 𝑦𝑥1 𝑦 = 𝑥1
Constant 𝑎 𝑦 𝑦 = 𝑎
Addition + 𝑦
𝑥1
𝑥2
𝑦 = min{1, 𝑥1 + 𝑥2}
Subtraction − 𝑦
𝑥1
𝑥2
𝑦 = max{0, 𝑥1 − 𝑥2}
Multiplication ×𝑎 𝑦𝑥1 𝑦 = max{0, min{1, 𝑎 ⋅ 𝑥1}}
Comparison > 𝑦
𝑥1
𝑥2
𝑦 =
{
{
{
{
{1, if 𝑥1 > 𝑥2
0, if 𝑥1 < 𝑥2
any, if 𝑥1 = 𝑥2.
This gate does not restrict the output when
𝑥1 = 𝑥2.
• Directed edges connecting variables to gates and gates to variables (loops are allowed);
• Variable nodes have in-degree 1; gates have 0, 1, or 2 inputs depending on type as above; gates
& nodes have arbitrary fanout.
Definition 1.1 (Arithmetic Circuit SAT problem). Given an arithmetic circuit satisfying the
description above, output an assignment of values 𝑣1, ..., 𝑣𝑛 ∈ [0, 1] that satisfies all the gates.
Example 1.1. Consider the following diagram.
1
2 > ≔
𝑎𝑐
𝑏
The only satisfying assignment is 𝑎 = 𝑏 = 𝑐 = 1/2.
It is easy to see that this problem has the flavor of a Brouwer fixed point.
Theorem 1.1 ([DGP09]). The Arithmetic Circuit SAT problem always admits a solution, and
it is PPAD-complete to find it.
2 From gates to games
It is possible to convert an Arithmetic Circuit SAT instance into a Nash equilibrium computation
problem in a multiplayer game. (The game can also be converted into a two-player [CDT09] or three-
player game [DGP09], but we do not show how in this lecture).
The idea is to use gadgets: constructions that simulate the behavior of the gates in the circuit.
2.1 Addition gate
Consider any game that contains the following interaction between four players 𝑥, 𝑦, 𝑧, 𝑤, each of
which has two actions, denoted {0, 1}. With a slight abuse of notation, we will call 𝑥, 𝑦, 𝑧, 𝑤 the
probability of playing action 1; hence, 𝑥, 𝑦, 𝑧, 𝑤 ∈ [0, 1].
Example 2.1 (Addition gadget game). Consider any game that contains as a substructure the
gadget shown in the diagram below, and payoffs set as follows.
▶ Payoffs of player 𝑤. The payoff of player 𝑤 is defined
as follows. If 𝑤 plays 0, her payoff does not depend on 𝑧’s
strategy, but only on 𝑥 and 𝑦, according to the payoff table
𝑦 = 0 𝑦 = 1
𝑥 = 0 0 1
𝑥 = 1 1 2
If 𝑤 plays 1, her payoff does not depend on 𝑥 and 𝑦’s
strategy and depends on 𝑧’s according to the table
𝑧 = 0 𝑧 = 1
0 1
▶ Payoffs of player 𝑧. The payoff of player 𝑧 is defined
according to the table
𝑧 = 0 𝑧 = 1
𝑤 = 0 1/2 1
𝑤 = 1 1/2 0
𝑥 𝑦
𝑤
𝑧
Figure 2: Addition gadget game.
The dashed blue edges denote pos-
sible edges in the games, which do
not affect the result in Theorem 2.1.
▶ Other payoffs and considerations. Players 𝑥 and 𝑦 utilities are independent on the strategies
of 𝑤 and 𝑧. Player 𝑤 does not affect other players in the game.
Theorem 2.1. In all Nash equilibria of the game, 𝑧 = min{𝑥 + 𝑦, 1}.
Proof . Suppose that 𝑧 < min{𝑥 + 𝑦, 1}. Then, 𝑧 < 𝑥 + 𝑦. But then 𝑤 will deterministicaly play
𝑤 = 0, which will force 𝑧 to play 𝑧 = 1. This is a contradiction, since by hypothesis 𝑧 < min{𝑥 +
𝑦, 1}, which implies 𝑧 < 1.
Suppose now that 𝑧 > min{𝑥 + 𝑦, 1}. In this case, min{𝑥 + 𝑦, 1} ≠ 1, as otherwise this would
imply 𝑧 > 1 which is impossible. Thus, 𝑧 > 𝑥 + 𝑦. This implies 𝑤 = 1 and hence 𝑧 = 0, which is
again impossible since 𝑧 > 𝑥 + 𝑦, which implies 𝑧 > 0.
The only remaining possibility is therefore 𝑧 = min{𝑥 + 𝑦, 1}, as we wanted to show. □
Bibliography
[DGP09] C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou, “The Complexity of Computing
a Nash Equilibrium,” SIAM Journal on Computing, vol. 39, no. 1, pp. 195–259, 2009,
doi: 10.1137/070699652.
[CDT09] X. Chen, X. Deng, and S.-H. Teng, “Settling the complexity of computing two-player Nash
equilibria,” Journal of the ACM (JACM), vol. 56, no. 3, pp. 1–57, 2009.
★These notes are class material that has not undergone formal peer review. The TA and I are grateful for any
reports of typos. Some of the content of the lecture was adapted from material from Costis Daskalakis.