Finding a Nash equilibrium is no easier than breaking Fiat-Shamir

DOI10.1145/3313276.3316400zbMath1434.94063OpenAlexW2952338482MaRDI QIDQ5212850

Guy N. Rothblum, Pavel Hubáček, Chethan Kamath, Krzysztof Pietrzak, Arka Rai Choudhuri, Alon Rosen

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3313276.3316400

zbMATH Keywords

Nash equilibriumTFNPPPADFiat-Shamir transformation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of game theory (91A80) Cryptography (94A60)

Related Items (14)

On the Complexity of Equilibrium Computation in First-Price Auctions ⋮ Non-interactive batch arguments for NP from standard assumptions ⋮ One-shot Fiat-Shamir-based NIZK arguments of composite residuosity and logarithmic-size ring signatures in the standard model ⋮ Permuted puzzles and cryptographic hardness ⋮ SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption ⋮ Practical statistically-sound proofs of exponentiation in any group ⋮ PPAD is as hard as LWE and iterated squaring ⋮ Correlation intractability and SNARGs from sub-exponential DDH ⋮ Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds ⋮ Unnamed Item ⋮ Continuous verifiable delay functions ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich ⋮ Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs ⋮ Delegation with updatable unambiguous proofs and PPAD-hardness

This page was built for publication: Finding a Nash equilibrium is no easier than breaking Fiat-Shamir