[+] PPAD Reductions (guest lecture by Constantinos Daskalakis). PPADcompleteness of Nash: graphical games, polymatrix games, 2player games. PPA (Handshaking Lemma), PLS (sinks exist), PPP (pigeonhole principle).  
This class is Costis Daskalakis's second of two guest lectures. We'll focus on examples of PPADcompleteness reductions, from Arithmetic Circuit SAT to Nash equilibria in a few different settings—ultimately twoplayer games. Not covered but in the slides are other examples of PPADhardness reductions. Finally we'll hear about other classes related to PPAD, based on other styles of proofs of existence of solutions. PPA is based on the fact that, if a graph has a node of odd degree, then it must have another (which follows from the Handshaking Lemma). PLS is based on the fact that every directed acyclic graph has a sink node. PPP is based on the Pigeonhole Principle: any mapping from a set to a set of a smaller size has a collision. 
Handwritten notes, page 1/6 •
[previous page] •
[next page] •
[PDF]
Handwritten notes, page 1/6 • [previous page] • [next page] • [PDF] 

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