6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall '14)

Prof. Erik Demaine     TAs: Sarah Eisenstat, Jayson Lynch


[Home] [Lectures] [Problem Sets] [Project] [Open Problems] [Piazza]

Lecture 23 Video     [previous]

[+] PPAD Reductions (guest lecture by Constantinos Daskalakis). PPAD-completeness of Nash: graphical games, polymatrix games, 2-player 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 PPAD-completeness reductions, from Arithmetic Circuit SAT to Nash equilibria in a few different settings—ultimately two-player games. Not covered but in the slides are other examples of PPAD-hardness 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.

Download Video: 360p, 720p

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.