The notion of Nash equilibrium (NE) is fundamental to game theory. While a mixed Nash equilibrium is guaranteed to exist in any game, there is no known polynomial-time algorithm for finding one. The tractability of the problem has received much attention in the past decade, in large part due to its theoretical and philosophical significance. Prominent evidence for the hardness of finding a NE emerges from a line of works, originating in Papadimitriou and ultimately showing that the problem is complete for the complexity class PPAD. The class PPAD contains several other search problems that are not known to be tractable, such as finding a fixed point of the kind guaranteed by Brouwer's Theorem. Akin to the phenomenon of NP-completeness, this could be interpreted as evidence to computational difficulty. However, unlike in the case of NP, currently known problems in PPAD appear to be of fairly restricted nature, and carry similar flavor to one another. In this talk I will show that finding a Nash equilibrium of a game is hard, assuming the existence of indistinguishability obfuscation and 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 PPAD. 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. Our result provides further evidence of the intractability of finding a Nash equilibrium, one that is extrinsic to the evidence presented so far. The talk is based on joint work with Nir Bitansky (MIT) and Omer Paneth (BU). It was presented in FOCS'15.
展开▼
