# 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] [Accessibility]

## 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). 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.
 No support for video detected. Please use an HTML5 browser. 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]