Nir Bitansky: On the Cryptographic Hardness of Finding a Nash Equilibrium

Speaker: Nir Bitanksy

Date: Tuesday, April 14, 2015

Time: 4:15 PM to 5:15 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: G449 Patil/Kiva

Event Type:

Room Description:

Host: Costis Daskalakis, Ankur Moitra, Dana Moshkovitz and Vinod Vaikuntanathan

Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: Nir Bitansky: On the Cryptographic Hardness of Finding a Nash Equilibrium

Abstract:
We prove that finding a Nash equilibrium of a game is hard, assuming the
existence of indistinguishability obfuscation and injective one-way functions with sub-exponential hardness.
We do so by showing how these cryptographic primitives give rise to a hard computational problem that lies
in the complexity class PPAD, for which finding Nash equilibrium is known to be complete.

Previous proposals for basing PPAD-hardness on program obfuscation considered a strong "virtual black-box"
notion that is subject to severe limitations and is unlikely to be realizable for the programs in question. In contrast,
for indistinguishability obfuscation no such limitations are known, and recently, several candidate constructions of
indistinguishability obfuscation were suggested based on different hardness assumptions on multilinear maps.

Our result provides further evidence of the intractability of finding a Nash equilibrium, one that is extrinsic
to the evidence presented so far.

Joint work with Omer Paneth and Alon Rosen http://eccc.hpi-web.de/report/2015/001/

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation (TOC) Seminar Series 2015.

Created by Deborah Goodwin Email at Tuesday, April 07, 2015 at 9:46 AM.