|
PART II
|
COMMUNICATION COMPLEXITY
|
|
Chapter 3
|
Communication Complexity of Approximate Nash Equilibrium
|
|
|
Our Results
|
|
|
3.1 Uncoupled Dynamics
|
|
|
3.2 Techniques
|
|
|
3.3 Additional Related Literature
|
|
|
3.4 Proof Overview
|
|
|
3.5 Proofs
|
|
|
3.6 An Open Problem: Correlated Equilibria in 2-Player Games
|
|
Chapter 4
|
Brouwer’s Fixed Point
|
|
|
4.1 BROUWER with ℓ∞
|
|
|
4.2 Euclidean BROUWER
|
|
PART III
|
PPAD
|
|
Chapter 5
|
PPAD-Hardness of Approximation
|
|
Chapter 6
|
The Generalized Circuit Problem
|
|
|
Our Results
|
|
|
6.1 Proof Overview
|
|
|
6.2 From Brouwer to ϵ-GCIRCUIT
|
|
|
6.3 GCIRCUIT with Fan-out 2
|
|
Chapter 7
|
Many-Player Games
|
|
|
Related Works: Tractable Special Cases
|
|
|
7.1 Graphical, Polymatrix Games
|
|
|
7.2 Succinct Games
|
|
Chapter 8
|
Bayesian Nash Equilibrium
|
|
Chapter 9
|
Market Equilibrium
|
|
|
9.1 Why Are Non-Monotone Markets Hard?
|
|
|
9.2 High-Level Structure of the Proof
|
|
|
9.3 Adaptations for Constant Factor Inapproximability
|
|
|
9.4 Non-Monotone Markets: Proof of Inapproximability
|
|
Chapter 10
|
CourseMatch
|
|
|
10.1 The Course Allocation Problem
|
|
|
10.2 A-CEEI Is PPAD-Hard
|
|
|
10.3 A-CEEI ∊ PPAD
|
|
PART IV
|
QUASI-POLYNOMIAL TIME
|
|
Chapter 11
|
Birthday Repetition
|
|
|
11.1 Warm-Up: Best ϵ-Nash
|
|
Chapter 12
|
Densest k-Subgraph
|
|
|
12.1 Construction (and Completeness)
|
