Pseudo-Equilibria, Or: How to Stop Worrying About Crypto and Just Analyze the Game

We revisit the problem of a game theorist analyzing a game that uses cryptographic protocols. Ideally, the game theorist should be able to ignore all implementation details of the cryptographic protocols and abstract them as ideal, implementation-independent primitives, in a way that conclusions in the "ideal world" can be faithfully transferred to the "real world," where real protocols are implemented by cryptography. Achieving this goal is crucial, as the game theorist cannot -and should not be expected to -grapple with the full complexity of cryptographic implementations. This is particularly relevant in the era of Web3, where the widespread adoption of distributed ledgers has created a pressing need for a common language that bridges cryptography and game theory.

We propose a new solution concept: the pseudo-Nash equilibrium. Informally, a (poly-time) strategy profile is a pseudo-Nash equilibrium if no (poly-time) player observes a noticeable, i.e., non-negligible, (expected) utility gain by playing a different (poly-time) strategy. Pseudo-Nash is substantially simpler and more accessible to game theorists than any existing notion that attempted to address the mismatch in the (asymptotic) cryptographic method and game theory. We prove, in a very general sense, that Nash equilibria in games that use idealized, unbreakable cryptography correspond naturally to pseudo-Nash equilibria when idealized cryptography is instantiated with actual protocols (under state-of-the-world assumptions). Our translation is not only conceptually simpler than existing approaches, but also more general: it does not require tuning or restricting utility functions in the game with idealized cryptography to accommodate idiosyncrasies of cryptographic implementations. In other words, pseudo-Nash equilibria allow us to separately and seamlessly study game-theoretic and cryptographic aspects.