Sink equilibria and the attractors of learning in games

• URL: http://arxiv.org/abs/2502.07975v1
• Date: Tue, 11 Feb 2025 21:40:11 GMT
• Title: Sink equilibria and the attractors of learning in games
• Authors: Oliver Biggar, Christos Papadimitriou,
• Abstract summary: Characterizing the limit behavior -- that is, the attractors -- of learning dynamics is one of the most fundamental open questions in game theory. We show through a topological construction that the one-to-one conjecture is false. Second, we make progress on the attractor characterization problem for two-player games by establishing that the one-to-one conjecture is true.
• Score: 0.0
• License:
• 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 in 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. We make threefold progress on the problem of characterizing attractors. First, we show through a topological construction that the one-to-one conjecture is false. Second, we make progress on the attractor characterization problem for two-player games by establishing that the one-to-one conjecture is true in the absence of a local pattern called a weak local source -- a pattern that is absent from zero-sum games. Finally, we look -- for the first time in this context -- at fictitious play, the longest-studied learning dynamic, and examine to what extent the conjecture generalizes there. We establish that under fictitious play, sink equilibria always contain attractors (sometimes strictly), and every attractor corresponds to a strongly connected set of nodes in the preference graph.

Related papers

• 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)
• 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)
• 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)
• 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)
• 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)
• 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)
• No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium [76.78447814623665]
  We give the first uncoupled no-regret dynamics that converge to correlated equilibria in normal-form games. We introduce a notion of trigger regret in extensive-form games, which extends that of internal regret in normal-form games. Our algorithm decomposes trigger regret into local subproblems at each decision point for the player, and constructs a global strategy of the player from the local solutions.
  arXiv  Detail & Related papers  (2020-04-01T17:39: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.