Sink equilibria and the attractors of learning in games

• URL: http://arxiv.org/abs/2502.07975v3
• Date: Sun, 26 Oct 2025 21:18:47 GMT
• Title: Sink equilibria and the attractors of learning in games
• Authors: Oliver Biggar, Christos Papadimitriou,
• Abstract summary: We show that the one$one conjecture is false.<n>Characterizing the limit behavior is one of the most fundamental open questions in game theory.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Characterizing the limit behavior -- that is, the attractors -- of learning dynamics is one of the most fundamental open questions in game theory. In recent work on this front, it was conjectured that the attractors of the replicator dynamic are in one-to-one correspondence with the sink equilibria of the game -- the sink strongly connected components of a game's preference graph -- , and it was established that they do stand in at least one-to-many correspondence with them. Here, we show that the one-to-one conjecture is false. We disprove this conjecture over the course of three theorems: the first disproves a stronger form of the conjecture, while the weaker form is disproved separately in the two-player and $N$-player ($N>2$) cases. By showing how the conjecture fails, we lay out the obstacles that lie ahead for characterizing attractors of the replicator, and introduce new ideas with which to tackle them. All three counterexamples derive from an object called a local source -- a point lying within the sink equilibrium, and yet which is `locally repelling'; we prove that the absence of local sources is necessary, but not sufficient, for the one-to-one property to be true. We complement this with a sufficient condition: we introduce a local property of a sink equilibrium called pseudoconvexity, and establish that when the sink equilibria of a two-player game are pseudoconvex then they precisely define the attractors. Pseudoconvexity generalizes the previous cases -- such as zero-sum games and potential games -- where this conjecture was known to hold, and reformulates these cases in terms of a simple graph property.

Related papers

• Model as a Game: On Numerical and Spatial Consistency for Generative Games [117.36098212829766]
  We revisit the paradigm of generative games to explore what truly constitutes a Model as a Game (MaaG) with a well-developed mechanism. Based on the DiT architecture, we design two specialized modules: (1) a numerical module that integrates a LogicNet to determine event triggers, with calculations processed externally as conditions for image generation; and (2) a spatial module that maintains a map of explored areas, retrieving location-specific information during generation and linking new observations to ensure continuity.
  arXiv  Detail & Related papers  (2025-03-27T05:46:15Z)
• Braiding for the win: Harnessing braiding statistics in topological states to win quantum games [0.23301643766310368]
  Nonlocal quantum games provide proof of principle that quantum resources can confer advantage at certain tasks.<n>We show that a toric code resource state conferred advantage at a certain nonlocal game, which remained robust to small deformations of the resource state.<n>We show how several other states from paradigmatic topological and fracton ordered phases can function as resources for suitably defined nonlocal games.
  arXiv  Detail & Related papers  (2024-12-18T19:30:30Z)
• Swim till You Sink: Computing the Limit of a Game [26.785274326413585]
  We study the problem of computing the behavior of a class of natural dynamics called the noisy replicator dynamics. We show through experiments that the limit distribution of reasonably large games can be estimated quite accurately through sampling and simulation.
  arXiv  Detail & Related papers  (2024-08-20T19:09:21Z)
• A geometric decomposition of finite games: Convergence vs. recurrence under exponential weights [24.800126996235512]
  We decompose games into simpler components where the dynamics' long-run behavior is well understood. In particular, the dynamics of exponential / multiplicative weights (EW) schemes is not compatible with the Euclidean underpinnings of Helmholtz's theorem. We establish a deep connection with a well-known decomposition of games into a potential and harmonic component.
  arXiv  Detail & Related papers  (2024-05-12T08:58:35Z)
• The Möbius game and other Bell tests for relativity [0.0]
  We derive multiparty games that, if the winning chance exceeds a certain limit, prove the incompatibility of the parties' causal relations with any partial order.<n>We discuss these games as device-independent tests of spacetime's dynamical nature in general relativity.
  arXiv  Detail & Related papers  (2023-09-27T16:08:13Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  We characterize the convergence of optimistic gradient descent (OGD) in time-varying games. Our framework yields sharp convergence bounds for the equilibrium gap of OGD in zero-sum games. We also provide new insights on dynamic regret guarantees in static games.
  arXiv  Detail & Related papers  (2023-01-26T17:25:45Z)
• Reasoning about Causality in Games [63.930126666879396]
  Causal reasoning and game-theoretic reasoning are fundamental topics in artificial intelligence. We introduce mechanised games, which encode dependencies between agents' decision rules and the distributions governing the game. We describe correspondences between causal games and other formalisms, and explain how causal games can be used to answer queries that other causal or game-theoretic models do not support.
  arXiv  Detail & Related papers  (2023-01-05T22:47:28Z)
• Counterexamples in self-testing [0.0]
  We study self-testing in nonlocal games. In particular, could it be that every 2-party nonlocal game or Bell inequality with a quantum advantage certifies the presence of a specific quantum state? Our counterexamples are based on a class of games to be of independent interest.
  arXiv  Detail & Related papers  (2022-12-22T09:52:18Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  We study the problem of computing an approximate Nash equilibrium of continuous-action game without access to gradients. We model players' strategies using artificial neural networks. This paper is the first to solve general continuous-action games with unrestricted mixed strategies and without any gradient information.
  arXiv  Detail & Related papers  (2022-11-29T05:16:41Z)
• Connes implies Tsirelson: a simple proof [91.3755431537592]
  We show that the Connes embedding problem implies the synchronous Tsirelson conjecture. We also give a different construction of Connes' algebra $mathcalRomega$ appearing in the Connes embedding problem.
  arXiv  Detail & Related papers  (2022-09-16T13:59:42Z)
• 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)
• Evolutionary Game-Theoretical Analysis for General Multiplayer Asymmetric Games [22.753799819424785]
  We fill the gap between payoff table and dynamic analysis without any inaccuracy. We compare our method with the state-of-the-art in some classic games.
  arXiv  Detail & Related papers  (2022-06-22T14:06:23Z)
• Proofs of network quantum nonlocality aided by machine learning [68.8204255655161]
  We show that the family of quantum triangle distributions of [DOI40103/PhysRevLett.123.140] did not admit triangle-local models in a larger range than the original proof. We produce a large collection of network Bell inequalities for the triangle scenario with binary outcomes, which are of independent interest.
  arXiv  Detail & Related papers  (2022-03-30T18:00:00Z)
• Bounded rationality for relaxing best response and mutual consistency: An information-theoretic model of partial self-reference [0.0]
  This work focuses on some of the assumptions underlying rationality such as mutual consistency and best-response. We consider ways to relax these assumptions using concepts from level-$k$ reasoning and quantal response equilibrium (QRE) respectively.
  arXiv  Detail & Related papers  (2021-06-30T06:56:56Z)
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
  It remains vastly open how to learn the Stackelberg equilibrium in general-sum games efficiently from samples. This paper initiates the theoretical study of sample-efficient learning of the Stackelberg equilibrium in two-player turn-based general-sum games.
  arXiv  Detail & Related papers  (2021-02-23T05:11:07Z)
• Fundamental Limits and Tradeoffs in Invariant Representation Learning [99.2368462915979]
  Many machine learning applications involve learning representations that achieve two competing goals. Minimax game-theoretic formulation represents a fundamental tradeoff between accuracy and invariance. We provide an information-theoretic analysis of this general and important problem under both classification and regression settings.
  arXiv  Detail & Related papers  (2020-12-19T15:24:04Z)
• Hindsight and Sequential Rationality of Correlated Play [18.176128899338433]
  We look at algorithms that ensure strong performance in hindsight relative to what could have been achieved with modified behavior. We develop and advocate for this hindsight framing of learning in general sequential decision-making settings. We present examples illustrating the distinct strengths and weaknesses of each type of equilibrium in the literature.
  arXiv  Detail & Related papers  (2020-12-10T18:30:21Z)
• No-regret learning and mixed Nash equilibria: They do not mix [64.37511607254115]
  We study the dynamics of "follow-the-regularized-leader" (FTRL) We show that any Nash equilibrium which is not strict cannot be stable and attracting under FTRL. This result has significant implications for predicting the outcome of a learning process.
  arXiv  Detail & Related papers  (2020-10-19T13:49:06Z)
• Chaos, Extremism and Optimism: Volume Analysis of Learning in Games [55.24050445142637]
  We present volume analyses of Multiplicative Weights Updates (MWU) and Optimistic Multiplicative Weights Updates (OMWU) in zero-sum as well as coordination games. We show that OMWU contracts volume, providing an alternative understanding for its known convergent behavior. We also prove a no-free-lunch type of theorem, in the sense that when examining coordination games the roles are reversed: OMWU expands volume exponentially fast, whereas MWU contracts.
  arXiv  Detail & Related papers  (2020-05-28T13:47:09Z)
• Ex ante versus ex post equilibria in classical Bayesian games with a nonlocal resource [0.0]
  We analyze the difference between ex ante and ex post equilibria in classical games played with the assistance of a nonlocal resource. We introduce a new type of game, based on the Bell-theorem by V'ertesi and Bene, which does not have the latter property.
  arXiv  Detail & Related papers  (2020-05-26T13:53:56Z)
• Real World Games Look Like Spinning Tops [27.182163984605193]
  This paper investigates the geometrical properties of real world games (e.g. Tic-Tac-Toe, Go, StarCraft II) We hypothesise that their geometrical structure resemble a spinning top. We prove the existence of this geometry for a wide class of real world games, exposing their temporal nature. We show that this unique structure also has consequences for learning - it clarifies why populations of strategies are necessary for training of agents, and how population size relates to the structure of the game.
  arXiv  Detail & Related papers  (2020-04-20T17:41:42Z)
• Counterexamples to the Low-Degree Conjecture [80.3668228845075]
  A conjecture of Hopkins posits that for certain high-dimensional hypothesis testing problems, no-time algorithm can outperform so-called "simple statistics" This conjecture formalizes the beliefs surrounding a line of recent work that seeks to understand statistical-versus-computational tradeoffs.
  arXiv  Detail & Related papers  (2020-04-17T21:08:11Z)
• On the complex behaviour of the density in composite quantum systems [62.997667081978825]
  We study how the probability of presence of a particle is distributed between the two parts of a composite fermionic system. We prove that it is a non-perturbative property and we find out a large/small coupling constant duality. Inspired by the proof of KAM theorem, we are able to deal with this problem by introducing a cut-off in energies that eliminates these small denominators.
  arXiv  Detail & Related papers  (2020-04-14T21:41:15Z)

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.