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

• URL: http://arxiv.org/abs/2506.22089v1
• Date: Fri, 27 Jun 2025 10:21:28 GMT
• Title: Pseudo-Equilibria, or: How to Stop Worrying About Crypto and Just Analyze the Game
• Authors: Alexandros Psomas, Athina Terzoglou, Yu Wei, Vassilis Zikas,
• Abstract summary: We consider the problem of a game theorist analyzing a game that uses cryptographic protocols.<n>We propose a new solution concept: the pseudo-Nash equilibrium.
• Score: 48.93355782581436
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We consider the problem of a game theorist analyzing a game that uses cryptographic protocols. Ideally, a theorist abstracts protocols as ideal, implementation-independent primitives, letting conclusions in the "ideal world" carry over to the "real world." This is crucial, since the game theorist cannot--and should not be expected to--handle full cryptographic complexity. In today's landscape, the rise of distributed ledgers makes a shared language between cryptography and game theory increasingly necessary. The security of cryptographic protocols hinges on two types of assumptions: state-of-the-world (e.g., "factoring is hard") and behavioral (e.g., "honest majority"). We observe that for protocols relying on behavioral assumptions (e.g., ledgers), our goal is unattainable in full generality. For state-of-the-world assumptions, we show that standard solution concepts, e.g., ($\epsilon$-)Nash equilibria, are not robust to transfer from the ideal to the real world. We propose a new solution concept: the pseudo-Nash equilibrium. Informally, a profile $s=(s_1,\dots,s_n)$ is a pseudo-Nash equilibrium if, for any player $i$ and deviation $s'_i$ with higher expected utility, $i$'s utility from $s_i$ is (computationally) indistinguishable from that of $s'_i$. Pseudo-Nash is simpler and more accessible to game theorists than prior notions addressing the mismatch between (asymptotic) cryptography and game theory. We prove that Nash equilibria in games with ideal, unbreakable cryptography correspond to pseudo-Nash equilibria when ideal cryptography is instantiated with real protocols (under state-of-the-world assumptions). Our translation is conceptually simpler and more general: it avoids tuning or restricting utility functions in the ideal game to fit quirks of cryptographic implementations. Thus, pseudo-Nash lets us study game-theoretic and cryptographic aspects separately and seamlessly.

Related papers

• Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback [60.610120215789976]
  We show that when a pure strategy Nash equilibrium exists, $c$ becomes zero, leading to an optimal instance-dependent regret bound.<n>Our algorithm also enjoys last-iterate convergence and can identify the pure strategy Nash equilibrium with near-optimal sample.
  arXiv  Detail & Related papers  (2025-02-24T20:20:06Z)
• Corrupted Learning Dynamics in Games [62.73758165845971]
  An equilibrium can be computed at a fast rate of $O(log T)$ when all players follow the optimistic follow-the-regularized-leader (OFTRL)<n>We present corrupted learning dynamics that adaptively find an equilibrium at a rate that depends on the extent to which each player deviates from the strategy suggested by the prescribed algorithm.
  arXiv  Detail & Related papers  (2024-12-10T02:23:44Z)
• Imperfect-Recall Games: Equilibrium Concepts and Their Complexity [74.01381499760288]
  We investigate optimal decision making under imperfect recall, that is, when an agent forgets information it once held before. In the framework of extensive-form games with imperfect recall, we analyze the computational complexities of finding equilibria in multiplayer settings.
  arXiv  Detail & Related papers  (2024-06-23T00:27:28Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  We show that Nash equilibrium (NE) is acceptable to all players in a multi-player game. We also show that no one can benefit unilaterally from the general theory step by step.
  arXiv  Detail & Related papers  (2023-01-19T11:36:50Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  We develop the concepts of Mean-Field correlated and coarse-correlated equilibria. We show that they can be efficiently learnt in emphall games, without requiring any additional assumption on the structure of the game.
  arXiv  Detail & Related papers  (2022-08-22T08:31:46Z)
• Safe Equilibrium [1.7132914341329848]
  The standard game-theoretic solution concept, Nash equilibrium, assumes that all players behave rationally. We propose a new solution concept called safe equilibrium that models opponents as behaving rationally with a specified probability. We prove that a safe equilibrium exists in all strategic-form games, and prove that its computation is PPAD-hard.
  arXiv  Detail & Related papers  (2022-01-12T01:45:51Z)
• Learning to Compute Approximate Nash Equilibrium for Normal-form Games [15.321036952379488]
  We propose a general meta learning approach to computing approximate Nash equilibrium for finite $n$-player normal-form games. Unlike existing solutions that approximate or learn a Nash equilibrium from scratch for each of the games, our meta solver directly constructs a mapping from a game utility matrix to a joint strategy profile.
  arXiv  Detail & Related papers  (2021-08-17T07:06:46Z)
• The Electromagnetic Balance Game: A Probabilistic Perspective [3.096615629099617]
  Finding a counterfeit coin with the different weight from a set of visually identical coin using a balance is an intersting and inspiring question. In this paper some variants of the balance game are dicussed, especially from a probabilistic perspective. We focus on the predetermined setting, where the player has to arrange the strategy without observing the outcome of the balancing.
  arXiv  Detail & Related papers  (2020-07-21T11:49:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.