Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Nash equiolibrium:
TR15-001 | 2nd January 2015
Nir Bitansky, Omer Paneth, Alon Rosen

On the Cryptographic Hardness of Finding a Nash Equilibrium

Revisions: 1

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 ... more >>>

ISSN 1433-8092 | Imprint