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.

Video Player is loading.
Current Time 0:00
Duration -:-
Loaded: 0%
Stream Type LIVE
Remaining Time -:-
 
1x
  • Chapters
  • descriptions off, selected

    Download Video: 360p, 720p

    Handwritten notes, page 1/6[previous page][next page][PDF]
    Video times: • 0:00–14:56

    Handwritten notes, page 1/6[previous page][next page][PDF]

    Slides, page 1/42[previous page][next page][PDF]
    Video times: • 0:00–0:16

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