[+] PPAD (guest lecture by Constantinos Daskalakis). Economic games, Nash equilibrium, Nash's Theorem, Brouwer's FixedPoint Theorem, Sperner's Lemma, proofs and computational versions. Total search problems (TFNP), directed parity argument, End of the Line, PPAD, Arithmetic Circuit SAT.  
This lecture is the first of two guest lectures by Prof. Constantinos Daskalakis about the class PPAD which is intricately related to economic game theory (and a cool idea more generally). Costis is the expert in this area — his PhD thesis, for example, proved that finding Nash equilibria is PPADcomplete. Specifically, this lecture illustrates beautiful connections (reductions) between Nash's Theorem in economic game theory, Brouwer's FixedPoint Theorem in topology, and Sperner's Lemma in graph theory. These problems are all PPADcomplete, meaning that they are the hardest search problems that have guaranteed solutions via “directed parity arguments” (formally, a problem called End of the Line). To prove PPADhardness (in the next lecture), we introduce an analog of Circuit SAT called Arithmetic Circuit SAT. 
Handwritten notes, page 1/7 •
[previous page] •
[next page] •
[PDF]
Handwritten notes, page 1/7 • [previous page] • [next page] • [PDF] 

Slides, page 1/59 •
[previous page] •
[next page] •
[PDF]
Slides, page 1/59 • [previous page] • [next page] • [PDF] 