CS Paper Radar

Learning in Large Populations With Anticipatory Payoffs: Bregman Meets Willems and Lyapunov

Tzuyu Jeng, Nuno C. Martins

cs.GT math.OCeess.SY ·submitted 2026-10-02 21:48 UTC · v1

Abstract

We study evolutionary Nash equilibrium learning in large populations whose payoffs are generated by dynamic mechanisms. Counterclockwise dissipativity (CCW) provides a passivity-like framework for establishing learning/convergence under a broad convex cone of so-called well-behaved learning rules satisfying a natural payoff-alignment condition according to which, away from equilibria, the population's state (strategic profile) moves in a direction positively correlated with the payoffs. The cone is closed under conic combinations and encompasses a broad range of noise-free rules, including discontinuous rules such as best response, imitative rules such as the replicator rule that is not $δ$-passive, and all noise-free $δ$-passive rules. Existing CCW results require no knowledge of the particular rule, but establish convergence without providing a Lyapunov function or Lyapunov stability. We develop a methodology that closes this gap by constructing rule-independent Lyapunov functions from CCW storage functions of the payoff mechanism. For a nonlinear class of anticipatory mechanisms, in which agents compare current payoffs with those associated with a smoothed population state, we show that a storage can be derived as a Bregman divergence. The resulting Lyapunov function combines a potential gap with this divergence and establishes global asymptotic stability. A congestion game with a nonlinear congestion-growth toll illustrates the results.

Closest papers

Nearest neighbours by meaning across the whole index.

Stabilization Limits of Payoff-Based Higher-Order Replicator Dynamics

eess.SY ·2026-08-15 ·Hassan Abdelraouf, Vijay Gupta, Jeff S. Shamma
similarity 0.71
Abstract

Replicator dynamics (RD) is a fundamental model in learning in games, connecting evolutionary game theory and online learning. This paper studies payoff-based higher-order variants of RD represented as a cascade interconnection between an integrator in parallel with an auxiliary linear time-invariant (LTI) system and the softmax mapping. We investigate learnability of Nash equilibria under this Nash-stationary learning rule. First, we revisit recent results that establish convergence to Nash Equilibrium whenever the auxiliary LTI system is strictly passive and prove a converse passivity result: if the auxiliary LTI system is not passive, then there exists a static strictly contractive game whose interior Nash equilibrium is unstable under the closed-loop learning dynamics. Second, we show that there exists a class of games with isolated interior Nash equilibria that cannot be locally asymptotically stabilized by any payoff-based higher-order RD whose auxiliary LTI system is asymptotically stable and strictly proper. Finally, we show that if Nash stationarity (i.e., all Nash equilibria are stationary points of the learning dynamics) is relaxed, then generalized exponential RD (Ex-RD) can locally asymptotically stabilize a logit equilibrium for any continuously differentiable game. The stabilized equilibrium can be viewed as an entropy-regularized approximate Nash equilibrium.

0.04

Entropic Risk-Sensitive Evolutionary Learning and Equilibrium Selection in Coordination Games

eess.SY cs.GTcs.MA ·2026-09-08 ·Solaleh Mohammadi, Xiang Gao, Kaiqing Zhang
publishedbenchmark similarity 0.66
Abstract · Preliminary version accepted to IEEE CDC 2026

We study risk-sensitive evolutionary learning dynamics and their long-run equilibrium selection behaviors in coordination games. Agents' risk attitudes enter through the classical entropic risk measure, which evaluates opponent-induced payoff uncertainty and feeds into noisy best responses under two standard revision protocols: best response with mutations and logit choice. We first analyze $2\times 2$ coordination games in both single-population symmetric and two-population asymmetric settings. In the single-population setting, unlike the risk-neutral case where the dynamics are known to favor the risk-dominant equilibrium, we show that risk sensitivity can change the stochastically stable outcome: a greater risk-seeking attitude favors the payoff-dominant equilibrium, while a greater risk-averse attitude favors the maximin equilibrium. Thus, the population's risk attitude may act as a control knob for long-run equilibrium selection. In both population settings, we also identify a robust regime: any super-dominant equilibrium is stochastically stable for all risk attitudes, under both protocols, and across populations. We further extend the single-population analysis to symmetric $k$-action games, which include symmetric $k$-action coordination games as a special case, under risk-sensitive best response with mutations. In this setting, we show that, for sufficiently large populations, sufficiently risk-seeking agents uniquely select the strongly payoff-dominant equilibrium when it exists, whereas sufficiently risk-averse agents uniquely select the strongly maximin equilibrium when it exists. These results show that entropic risk sensitivity may serve as a systematic mechanism for steering equilibrium selection in evolutionary games, beyond the classical risk-neutral benchmark.

0.33

Bayesian Replicator Dynamics and the Inversion of Strict Dominance in Bimatrix Games

cs.GT cs.MA ·2026-10-26 ·Jaime Ruiz-Serra, Nihat Ay, Michael Harré
similarity 0.64
Abstract · 18 pages, 3 figures

Replicator dynamics, the central model of evolutionary game theory, describe populations evolving under selection and agents learning by trial and error. They also admit a third use: continuous-time Bayesian inference, in which an agent planning against an opponent accumulates evidence for each candidate strategy. Here we show that this use divides all two-player games into two classes. With the standard expected-utility payoff, the dynamics can be expressed as Bayesian updating only in games (with any number of actions) where no player has a dominant strategy. The logarithmic payoff of Ay and Erb (2005) admits the Bayesian representation in every game. Coordination, anti-coordination, and cyclic games share qualitative dynamics under both payoff definitions, with equilibria displaced and selection thresholds shifted. In contrast, the flows of every game with a dominant strategy are reversed between the payoff definitions, with the strictly dominant strategy eliminated under logarithmic payoffs. Cooperation therefore emerges in the Prisoner's Dilemma, and games of common interest converge to mutual defection. For two-action games the classification is complete and rests on an exact Hamiltonian structure shared by both payoff definitions. The structure gives a behavioural test: cycles in the classic Matching Pennies game have amplitude-independent period (isochronous) under logarithmic payoffs, but not under expected utility. Logarithmic evidence integration thus determines which strategic outcomes dynamical selection can reach, wherever learning approximates Bayesian updating.

0.23

SIS Epidemic Containment under Game-theoretic Rational Learning

eess.SY ·2026-10-02 ·Urmee Maitra, Keith Paarporn, Ceyhun Eksin
similarity 0.64
Abstract

We consider a susceptible-infected-susceptible (SIS) epidemiological model in which individuals dynamically decide whether to follow social distancing or not. Driven by game-theoretic payoffs, their actions influence the spread of infection. Much of the existing work in this area considers individuals that are imitative learners, leading to the well-studied replicator equation. In this paper, we investigate how the dynamical outcomes may fundamentally shift when individuals are instead equipped with logit learning rules, i.e., when individuals possess bounded rationality. We analyze the local asymptotic stability of equilibria that exist in different parameter regimes of the coupled dynamical system. We show that in regimes where the disease-free equilibrium is unstable under imitative learning and sufficiently high-rationality logit learning, sufficiently low rationality can avoid such an undesirable outcome by stabilizing the disease-free equilibrium. We also identify parameter regimes in which an unstable endemic equilibrium stabilizes when rationality falls below a threshold. We numerically illustrate the convergence of infection state and response trajectories to a stable disease-free equilibrium at a lower degree of rationality, whereas the same trajectories otherwise converge to a stable endemic equilibrium as the rationality level rises. We also compare a specific case in which trajectories under replicator dynamics fail to converge, and illustrate convergence when rationality is below an analytically derived threshold.

0.24

How Learning Selects Equilibria and When It Leads to Collusion

cs.GT ·2026-10-26 ·Hanzhang Wang, Manxi Wu
benchmark similarity 0.64
Abstract

We study how learning algorithm design shapes equilibrium selection in infinite-horizon discounted Markov games with finite states and actions. Each episode, players choose smooth best responses to beliefs about opponents' policies, test them using noisy observations, and resample rejected beliefs or explore at rates determined by increasing transformations of their discounted values. We show that stochastically stable states induce approximate stationary Nash equilibria maximizing the minimum transformed discounted value across players, with transformations governing which players selection favors. In repeated games with bounded recall of noisy public signals, longer recall weakly increases the selected minimum transformed value. In repeated Cournot games, every stochastically stable state induces an approximate public perfect equilibrium whose minimum discounted profit across firms exceeds the Cournot-Nash benchmark. Collusion is therefore inevitable under these conditions and learning dynamics. For symmetric firms, selected profits can approach the monopoly benchmark arbitrarily closely. These results offer a novel equilibrium-selection perspective on algorithmic collusion.

0.17

Metric-Based Equilibrium Selection in Noncooperative Differentiable Games

cs.GT eess.SY ·2026-10-05 ·Karan Mahesh, Runyu Zhang, Michael R. Benjamin, Gioele Zardini
similarity 0.64
Abstract · 8 pages, 2 figures

Metric conditioning can change which equilibrium attracts learning dynamics without moving the equilibria of a differentiable game. We study how to use state-dependent symmetric positive-definite (SPD) metrics to select among known equilibria by keeping a designated equilibrium attracting while making a rival unstable. Building on classical results on matrix stability under positive-definite multiplication, we characterize when such destabilization is possible and show how restricting the metric to act independently on each player limits the stability changes that can be achieved at differential Nash equilibria. We then combine a stabilizing metric at the selected equilibrium with a destabilizing metric at the rival through smooth interpolation, yielding a single metric field that preserves every equilibrium of the game while assigning the desired local stability types. We also derive a step-size condition for implementing the method in discrete time. The approach is validated on a continuous-commitment stag hunt and an entropy-regularized iterated prisoner's dilemma, where it selects the desired equilibrium in both settings.

0.28

Evolutionary Stability Does Not Guarantee Learning Accessibility: A Multi-Agent Reinforcement Learning Perspective on Cooperation Emergence

cs.AI ·2026-09-23 ·Yijie Wang
similarity 0.63
Abstract

Cooperation emergence is a central problem in multi-agent systems because decentralized agents must coordinate while adapting to the changing behavior of others. Evolutionary game theory identifies strategically stable outcomes, but stability under a population adjustment dynamic need not imply that finite-sample learning agents can reach the same outcome through local reward feedback. We study this distinction in a transparent three-agent governance-motivated game involving a government, a platform firm, and users. We derive replicator dynamics for the fixed stage-game incentives, evaluate the cooperative evolutionary basin on a symmetric initial-condition grid, and compare it with learning-basin estimates for three decentralized value-based learners. The learning analysis uses independent Q-learning with $\varepsilon$-greedy action selection, scaled Boltzmann exploration, and SA--EA BQL under the same payoff environment and outcome criterion. The evolutionary basin has volume $V_E=1.00$ on the sampled grid. The empirical learning basin is $0.88$ for $\varepsilon$-IQL and $0.00$ for both scaled Boltzmann and SA--EA BQL. Diagnostic traces show that broader action diversity and nonzero value separation can coexist with failure to sustain the cooperative joint action in this fixed configuration. These results indicate that evolutionary stability and learning accessibility are distinct properties of a coupled game--learning system. The shared-bike setting is a motivating application; the broader contribution is a framework for comparing population-level stability with the finite-sample accessibility of cooperation under specified multi-agent learning dynamics.

0.13

Multi-Agent Learning of Reactive Strategies in Iterated Games

cs.GT physics.soc-phq-bio.PE ·2026-10-10 ·James P. Wolfe, Joshua B. Plotkin
theorycode/data similarity 0.62
Abstract · 27 pages, 14 figures (12 pages + 3 figures main text; 15 pages + 11 figures Supplemental Material). Code: https://github.com/james-wolfe/rea…

Learning agents, whether humans or algorithms, adapt to one another rather than to a fixed environment. Selfish learning need not produce a good outcome for the group, especially when learners face a social dilemma. The iterated prisoner's dilemma (IPD) is the classical example, but it is usually studied in populations of agents who imitate successful strategies. Here, we instead study selfish gradient ascent learners on the two-dimensional space of reactive strategies. A reactive strategy is described by two continuous traits: reciprocity, the chance of cooperating after the co-player cooperates, and forgiveness, the chance of cooperating after the co-player defects. Each learner updates its strategy in the direction that most rapidly improves its payoff against all other learners, by an amount governed by its learning rate. We show that heterogeneity in learning rates can qualitatively change the long-term outcome: a population with uniform learning rates converges to always-defect (ALLD), whereas a population with variable learning rates approaches generous-tit-for-tat (GTFT), which produces nearly optimal collective payoffs. In simulations, every population passes through a transient state of minimal forgiveness, in which the distribution of reciprocity determines the outcome. Variable learning rates promote cooperation because slow learners preserve high reciprocity until the population reaches this state. We prove sufficient conditions on the distribution of reciprocity for convergence to ALLD or to tit-for-tat (TFT). Variable learning rates also allow cooperation to recover from perturbation, which is provably impossible under uniform learning. These results suggest that purely selfish and myopic learning can produce persistent cooperation provided the population has intrinsic variability in learning rates.

0.40