[+] 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).  [Scribe Notes] [src]  
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] 
The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The handwritten notes and slides should advance automatically. If you have any trouble with playback, email Erik.