PaperlayerView exact revision on arXiv

Source-linked AI summary

Complex dynamics in learning complicated games

Tobias Galla, J. Doyne Farmer

arXiv:1109.4250v1nlin.CDcs.GTphysics.soc-ph

TL;DR

The paper asks whether equilibrium-based game theory describes complicated games with many possible moves and learning players. It studies randomly generated two-player games with experience-based learning and finds transitions among fixed points, cycles, and high-dimensional chaos, including intermittent payoff fluctuations. These results frame complicated strategic interactions as dynamical systems whose behavior can become effectively unpredictable.

  • Problem

    Traditional equilibrium analysis is well understood for simple games, but its applicability is unclear when games have many moves and players must learn their strategies.

  • Method

    The study analyzes two-player games with randomly generated payoff matrices and experience-weighted learning, combining simulations with path-integral calculations of stability boundaries.

  • Results

    The strategies can converge to fixed points, limit cycles, or chaotic attractors; chaotic regimes are associated with high-dimensional dynamics and intermittent payoff fluctuations.

  • Takeaways & Limitations

    Non-zero-sum games with long-memory learning are harder to learn because strategies may fail to converge, making dynamical-systems concepts useful for describing their behavior.

Abstract

from arXiv · show

Game theory is the standard tool used to model strategic interactions in evolutionary biology and social science. Traditional game theory studies the equilibria of simple games. But is traditional game theory applicable if the game is complicated, and if not, what is? We investigate this question here, defining a complicated game as one with many possible moves, and therefore many possible payoffs conditional on those moves. We investigate two-person games in which the players learn based on experience. By generating games at random we show that under some circumstances the strategies of the two players converge to fixed points, but under others they follow limit cycles or chaotic attractors. The dimension of the chaotic attractors can be very high, implying that the dynamics of the strategies are effectively random. In the chaotic regime the payoffs fluctuate intermittently, showing bursts of rapid change punctuated by periods of quiescence, similar to what is observed in fluid turbulence and financial markets. Our results suggest that such intermittency is a highly generic phenomenon, and that there is a large parameter regime for which complicated strategic interactions generate inherently unpredictable behavior that is best described in the language of dynamical systems theory

I. MODEL

The paper models two players who choose among N moves using experience-weighted reinforcement learning, with strategy frequencies updated deterministically from past payoffs. Learning depends chiefly on memory α and choice intensity β, while randomly generated payoff matrices are correlated through Γ.

  • Game and strategies: Each player’s strategy is a frequency vector over N possible moves, and the payoff depends on the pair of moves selected.
  • Learning rule: Players update strategies through experience-weighted attraction learning, favoring actions that were more successful in the past.
  • Learning rule: The deterministic strategy dynamics approximate players who vary their strategies slowly relative to the timescale of game play.
  • Learning parameters: β controls how strongly historical advantages determine choice probabilities, while α controls how quickly past learning is forgotten.
  • Payoff ensemble: Random payoff matrices are parameterized by Γ, with Γ = −1 denoting zero-sum games and Γ = 0 denoting uncorrelated player payoffs.

II. RESULTS

Simulations reveal stable fixed points, limit cycles, and chaotic attractors across the learning parameter space. Chaotic regimes can have high-dimensional strategy dynamics and intermittent payoff fluctuations, while analytical stability boundaries and simulations identify where these behaviors occur.

  • Learning dynamics: With N = 50 moves, the 98-dimensional strategy state can converge to a fixed point, limit cycle, or chaotic attractor depending on the parameters and payoff draw.
  • Stability diagram: Stable learning is associated with Γ ≈ −1 and large α, whereas instability is associated with Γ ≈ 0 and small α.
  • Stability diagram: The highest-dimensional behavior occurs near Γ ≈ −0.6 and α ≈ 0, although the authors state that they do not understand why.
  • Scope and limitations: The study uses specific EWA parameter choices, and it remains unknown whether attractor dimension approaches a finite limit or grows without bound as N →∞.
  • Analysis and simulations: The analytical stability boundary is computed with path-integral methods in the N →∞ limit, while simulations estimate attractor dimensions across payoff matrices.
  • Payoff fluctuations: Chaotic dynamics produce intermittent bursts of large payoff changes separated by relative quiescence, with fluctuation amplitude increasing with attractor dimension.

III. WHY IS DIMENSIONALITY RELEVANT?

High-dimensional chaotic attractors matter because they can make complicated games intrinsically difficult or impossible to learn from past data. The study also uses the random-game framework to relate learning dynamics to game structure and established EWA parameters.

  • Why dimensionality matters: High-dimensional chaos suggests that failure to converge is independent of the learning algorithm, making the game intrinsically hard to learn.Lower-dimensional cycles or attractors may remain predictable, whereas the curse of dimensionality undermines prediction from finite data.
  • Predicting learning dynamics: The study claims that any complicated two-player game can be located in a random-game ensemble to predict qualitative reinforcement-learning dynamics.Its stability diagram estimates whether strategies converge by combining game and learning parameters.
  • Predicting learning dynamics: Zero-sum structure and memory length organize learnability: non-zero-sum games with long memory are harder to learn because strategies do not converge.The paper characterizes zero-sumness with Γ and identifies it as a key property of the game.
  • Learning model: The EWA model represents action propensities as attractions updated from past success, with β controlling choice intensity and α controlling memory loss.β = 0 yields equal-probability choices, while α = 0 retains the full history of play.
  • Learning model: The analysis restricts EWA to a tractable case that updates all strategy scores, uses cumulative reinforcement, and applies exponential discounting when α > 0.These restrictions define the learning rule studied rather than the full EWA parameter space.

3. Relation to experimental data

The paper compares its chaotic-learning predictions with experimentally fitted EWA parameters while emphasizing that the experiments use low-dimensional games. Under a cautious extrapolation, fitted parameters may place real-world non-zero-sum learning near the chaotic phase.

  • Relation to experimental data: EWA parameters fitted to real-world data vary substantially across games, although the paper’s analytically tractable choices are described as reasonably realistic.The cited fits include κ values from 0.15 to 0.99.
  • Relation to experimental data: The ratio α/β is the crucial indicator for chaos, and pooled experimental data suggest α/β ≈ 0.03 with considerable variation.The paper notes that this ratio can place experiments in the chaotic phase depending on whether games are zero-sum.
  • Relation to experimental data: The experimental games are low-dimensional because each player chooses among only a small number of moves, so extrapolation to high-dimensional random games requires care.The paper explicitly warns that the experimental setting differs from the high-dimensional games analyzed theoretically.
  • Deterministic learning: In the adiabatic limit, stochastic action outcomes are replaced by expected payoffs against the opponents’ mixed strategies, producing a deterministic learning map.This approximation averages over a large number of rounds between adaptation steps and neglects fluctuation effects.
  • Deterministic learning: The resulting two-player model has two N-component strategy vectors subject to probability constraints, defining a reduced strategy-space representation.The notation uses x_i(t) for Alice’s action probabilities and y_i(t) for Bob’s.

2. Relation between discrete-time dynamics and continuous-time Sato-Crutchfield equations

The discrete-time learning map connects to continuous-time Sato-Crutchfield dynamics in the small-β limit, while sharing fixed points for any β. The ratio of choice intensity to memory loss is the central control parameter, and random-game analysis uses correlated Gaussian payoffs.

  • Discrete-to-continuous relation: In the β → 0 limit, the discrete-time dynamics become the continuous-time Sato-Crutchfield equations after time rescaling, with α′ = α/β.The same correspondence holds for Bob’s strategy dynamics.
  • Discrete-to-continuous relation: For any β, the fixed points of the discrete-time map coincide with those of the continuous-time dynamics.The comparison assumes fixed points lie in the interior of the strategy simplex.
  • Control parameter: Provided a fixed point exists, its components depend only on α/β rather than on α and β separately.The paper therefore uses r = β/α as the relevant control parameter, analogous to a Reynolds number.
  • Random games: The random-game ensemble draws Gaussian payoff matrices whose elements remain fixed during evolution, with Γ measuring correlations between a_ij and b_ji.Γ = −1 corresponds to zero-sum games, Γ = 0 to uncorrelated payoffs, and the analysis focuses on −1 ≤ Γ ≤ 0.
  • Random games: The payoff and strategy rescalings are chosen to produce a non-trivial thermodynamic limit as N →∞.The scaling keeps payoff combinations entering the learning process well defined and of order one.

Appendix C: Path-integral analysis

The path-integral analysis averages over quenched random payoff disorder and reduces the many-variable dynamics to self-consistent effective processes. Saddle-point conditions then determine response and correlation quantities in the large-N limit.

  • Generating functional: The analysis applies generating-functional and path-integral methods from disordered-systems theory to the continuous learning dynamics.The disorder average is taken over the randomly chosen payoff matrices, which remain fixed during evolution.
  • Generating functional: The generating functional introduces correlation, response, and auxiliary order parameters through delta-function representations of the dynamics.These quantities organize the disorder-averaged expression before the large-N saddle-point calculation.
  • Saddle-point reduction: In the N →∞ limit, the saddle-point method finds extrema of the exponent and produces equations for the effective processes.Variations with respect to the order parameters impose relations among the response and correlation functions.
  • Saddle-point reduction: Normalization implies that the response-related quantities L_x(t,t′) and L_y(t,t′) vanish for all times.This follows from Z[ψ = 0, ϕ = 0, h] = 1 for every h.
  • Effective dynamics: The resulting effective dynamics have self-consistent noise correlations matching the opposite player’s strategy correlations and mean strategy equal to one.The same self-consistency structure applies to the discrete-time effective process, with causality restricting dependence to earlier times.

b. Fixed point analysis

The fixed-point analysis derives self-consistency equations for the effective dynamics, determining statistical properties of fixed points such as mixed-strategy distributions and entropy.

  • Fixed points of the discrete-time effective dynamics are characterized by fixed-point conditions, with an equivalent condition obtained from the continuous-time process.
  • The analysis represents η_x as √qz, where z is a zero-mean, unit-variance static Gaussian variable, and selects the positive solution x(z).
  • The order parameters χ, q, and ρ are determined self-consistently.
  • These equations determine fixed-point statistics, including the distribution of pure-action frequencies and the entropy of mixed strategies.

c. Linear stability analysis

The stability analysis perturbs fixed points, linearizes the effective dynamics, and identifies instability when the self-consistent fixed-point solution breaks down.

  • The analysis introduces small noise perturbations around a fixed point and expands the dynamics to linear order in the deviations.
  • Perturbations are analyzed in Fourier space while restricting attention to components with positive fixed-point values.
  • The fraction φ of strategies with non-zero probability is incorporated into the stability calculation, together with the symmetry between players and self-consistency relations.
  • A divergence signals instability, while the predicted negative value of the relevant fixed-point quantity indicates that the self-consistent solution breaks down.
  • Eq. (C40) defines the boundary of the stable fixed-point phase, where the fraction of active strategies is φ = 1 for Γ < 0.

1. Test of theoretical predictions against simulations

Theoretical fixed-point predictions are compared with direct simulations and agree well for strategy-component distributions and entropy, while the analytical fixed-point theory does not extend to the chaotic regime.

  • The path-integral analysis determines order parameters χ, q, and ρ through nonlinear self-consistency equations in the fixed-point phase.
  • Analytical predictions for the non-Gaussian distribution of strategy components agree rather well with direct simulations of the original learning dynamics.
  • Theoretical predictions and direct measurements of mixed-strategy entropy agree very well in simulations.
  • For very quick memory loss, mixed strategies concentrate near the centre of strategy space, with x_i ≈ 1 under the stated normalization.
  • The fixed-point equations predict only the stable fixed-point phase; analytical treatment of the chaotic regime remains unavailable.

b. Onset of instability

The onset of instability is tested by locating where simulations cease to converge to fixed points and comparing that boundary with the theoretical prediction.

  • The predicted onset of instability is the boundary of the chaotic phase, and simulations confirm it by measuring attractor dimensions in parameter space.
  • Larger-system tests determine the instability boundary by varying α/β for fixed Γ across random payoff-matrix samples.
  • A run is classified as reaching a fixed point when all final-time Jacobian eigenvalues lie within the unit circle and total fluctuations remain below a threshold.
  • The numerical agreement with theory is very good, with possible deviations attributed to finite simulation time, discrete-time dynamics, and finite-size effects.

2. Estimation of the attractor dimension

The study estimates attractor dimensions from Lyapunov exponents after equilibration and checks convergence over extended simulation windows. It also measures payoff returns and finds exponential tails in their distribution.

  • Dimension estimation: 150,000 iterations are used for equilibration before estimating Lyapunov exponents from the linearized dynamics.The simulation is then extended until the dimension estimate meets the convergence criterion or reaches 10^6 iterations.
  • Dimension estimation: The Kaplan-Yorke dimension uses ordered Lyapunov exponents and the largest index whose cumulative sum remains nonnegative.This dimension measures the effective number of degrees of freedom on the attractor.
  • Convergence criterion: An attractor dimension is considered converged when its maximum and minimum estimates within 20,000 iterations differ by less than 5%.The reported value is the average over that time window.
  • Payoff returns: Total payoff returns are computed as the change in total payoff between consecutive time steps during the equilibrated regime.The corresponding return distribution is shown in Fig. 7 and has exponential tails.
Loading 1109.4250v1…