TY - GEN
T1 - On the Cryptographic Hardness of Finding a Nash Equilibrium
AU - Bitansky, Nir
AU - Paneth, Omer
AU - Rosen, Alon
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2015/12/11
Y1 - 2015/12/11
N2 - We prove 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 the complexity class PPAD, for which finding Nash equilibrium is 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.
AB - We prove 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 the complexity class PPAD, for which finding Nash equilibrium is 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.
KW - nash equilibrium
KW - obfuscation
UR - http://www.scopus.com/inward/record.url?scp=84960400400&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84960400400&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2015.94
DO - 10.1109/FOCS.2015.94
M3 - Conference contribution
AN - SCOPUS:84960400400
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 1480
EP - 1498
BT - Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015
PB - IEEE Computer Society
T2 - 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015
Y2 - 17 October 2015 through 20 October 2015
ER -