PaperlayerView exact revision on arXiv

Source-linked AI summary

How Learning Selects Equilibria and When It Leads to Collusion

Hanzhang Wang, Manxi Wu

arXiv:2610.36306v1cs.GT

TL;DR

When learning dynamics leave multiple equilibria possible, the paper asks how learning-rule design determines which outcomes persist. It models episodic belief testing and value-dependent exploration, and shows that selected outcomes maximize a minimum transformed value; in repeated Cournot games, they are collusive under stated conditions.

  • Problem

    When a game has multiple equilibria, it remains open which outcome learning will produce and sustain, and how exploration rules affect that selection.

    Source: §1 · p. 1

  • Method

    Players use smooth best responses to beliefs about opponents, test beliefs using observations, and resample rejected beliefs or explore at rates governed by increasing transformations of discounted value.

    Source: §1 · p. 2

  • Results

    Stochastically stable states induce approximate stationary Nash equilibria maximizing the minimum transformed value, and every such Cournot outcome is collusive under the stated conditions.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    The results connect persistent algorithmic collusion to equilibrium selection shaped by individual exploration rules, without explicit joint-profit targeting.

    Source: §1 · pp. 2–3

    In the public-monitoring setting, transient empty-history states cannot be tested by simply increasing epoch length; the analysis therefore uses a restart protocol.

    Source: §4.1 · p. 12, §4.2 · p. 14

Abstract

from arXiv · show

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.

1 Introduction

The paper studies how belief testing and value-dependent exploration select equilibria in discounted Markov games, then applies the framework to bounded-recall repeated games and Cournot competition. It connects persistent collusion to individual learning-rule design.

1 Introduction

  • The episodic dynamic uses smooth best responses to state-dependent beliefs, tests those beliefs using observations, and resamples rejected beliefs or explores according to transformed discounted value.The observations may be noisy signals of opponents’ actions.Source: §1 · p. 2
  • Stochastically stable belief–policy states induce approximate stationary Nash equilibria that maximize the minimum transformed discounted value across players.This characterizes long-run selection under suitable assumptions and learning parameters.Source: §1 · p. 2
  • Player-specific transformations can favor players assigned lower transformed values, because they are more likely to explore and can steer selection toward equilibria with higher payoffs for them.With a common increasing transformation, selection instead maximizes the minimum value.Source: §1 · p. 2
  • With learning parameters fixed, longer public recall weakly increases the selected minimum transformed value in repeated games.Bounded public histories can be represented as states of a finite Markov game, linking approximate public perfect equilibria to approximate stationary Nash equilibria.Source: §1 · p. 2
  • In Cournot competition, every stochastically stable outcome is collusive under sufficient patience, recall, monitoring accuracy, and suitable learning parameters.For symmetric firms, the collusion index can approach one, and learning does not explicitly target joint-profit maximization.Source: §1 · p. 3
  • The Markov-game result extends prior max–min selection work to infinite-horizon discounted games and noisy signals, while the repeated-game recall and Cournot guarantees are new to this paper.The extension requires analysis of state-dependent smooth best responses, consistent states, and testing errors under dependent observations and random state-visit counts.Source: §1 · p. 4

2 Model

The model is an infinite-horizon discounted Markov game with finite players, states, and actions. Players evaluate stationary policies using expected discounted values and form state-dependent beliefs about opponents’ actions.

2 Model

  • The game has finite players, states, and action sets, with stage payoffs, state transitions, a discount factor, and an initial-state distribution.A stationary policy maps each state to a distribution over that player’s actions.Source: §2 · p. 4
  • A player’s expected total discounted payoff is evaluated over the state-action trajectory induced by the stationary policy profile and initial-state distribution.The paper refers to this expected payoff as the player’s value.Source: §2 · pp. 4–5
  • Each player’s beliefs specify distributions over opponents’ actions at each state, with opponents’ actions assumed conditionally independent given the state.The beliefs are restricted to a finite grid for computational tractability.Source: §2 · p. 5
  • Players respond to their beliefs with a smooth best response, which exists uniquely and can be computed by regularized value iteration.The response maximizes an entropy-regularized value.Source: §2 · pp. 5–6

3 Learning Dynamics and Stochastically Stable Set

The learning dynamic alternates play, belief testing and updating, and smooth best-response policy updates. Under the stated assumptions, its stochastically stable states induce approximate stationary Nash equilibria selected by the minimum transformed value across players.

3.1 Learning Dynamics

  • Each epoch plays the Markov game from an initial state, gathers action or signal observations, tests beliefs, updates them, and revises policies by smooth best response.Testing occurs independently with player-specific probability; accepted beliefs may still be resampled through exploration.Source: §3.1 · pp. 6–8
  • Every consistent belief-policy state induces an ϵ-stationary Nash equilibrium under Assumptions 1 and 2.The consistent-state set is nonempty.Source: §3.1 · p. 8
  • The generalized likelihood ratio test can satisfy the required error control with finite epoch length when reachability and identifiability hold.The test uses a player’s belief and observations without requiring knowledge of opponents’ utilities, beliefs, or best-response functions.Source: §3.1 · pp. 9–10

3.2 Stochastically Stable Set Characterization

  • As testing errors and exploration vanish, the epoch-level belief-policy process spends almost all epochs in its stochastically stable states.The sequence of belief-policy states forms a Markov chain on the finite state space.Source: §3.2 · pp. 10–11
  • Under Assumptions 1–6, stochastically stable states select consistent belief-policy states maximizing the minimum transformed value across players.With a common increasing transformation, selection is max–min on values; player-specific transformations can favor different equilibrium value distributions.Source: §3.2 · p. 11
  • Hypothesis testing excludes inconsistent states from stochastic stability, while value-dependent exploration determines which consistent states persist.The player with the smallest transformed value has the highest exploration probability and is most likely to initiate departure.Source: §3.2 · p. 11

4 Equilibrium Selection in Repeated Games and Algorithmic Collusion

This section connects bounded public recall in repeated games to finite-state Markov games and public perfect equilibria, then examines learning-driven outcomes in repeated Cournot competition. It describes a symmetric cooperative-profile construction that yields profits above the Cournot–Nash benchmark and, when maximal symmetric profit equals uC, a bound reaching 1−ε; longer recall and firm symmetry shape how far selected outcomes move toward monopoly profits.

4.1 Repeated Games with Public Monitoring

  • An L-recall public policy is an ϵ-perfect public equilibrium exactly when it is an ϵ-stationary Nash equilibrium of the induced finite-state Markov game.The induced game uses public histories of length L as states.Source: §4.1 · p. 12
  • Repeated runs from the initial history pool observations for transient early histories, allowing error control and the stochastic-stable-set characterization to apply.Restarts replace the need for Assumption 3 for states in the first L stages.Source: §4.1 · pp. 12–13
  • With learning parameters held fixed, increasing recall weakly raises the minimum transformed value at selected approximate public perfect equilibria.The comparison is between games with recall lengths L and L+1.Source: §4.1 · p. 13

4.2 Algorithmic Collusion in Cournot Competition

  • Longer recall weakly increases the belief-based collusion index and approximately increases the actual-payoff index across stochastically stable outcomes.The actual-payoff comparison is approximate because beliefs about opponents’ policies need not coincide with their actual policies.Source: §4.2 · pp. 15–16
  • Under sufficiently long recall, high discounting, and sufficiently low monitoring noise, learning parameters can make every stochastically stable Cournot outcome yield profits above the Nash benchmark.The theorem establishes a positive actual-payoff collusion index for every stochastically stable state under these conditions.Source: §4.2 · pp. 15–16
  • With symmetric firms, sufficiently long recall, high discounting, and low monitoring noise allow selected outcomes to approach the monopoly-profit benchmark arbitrarily closely.The theorem states that the actual-payoff collusion index can approach one.Source: §4.2 · pp. 15–16
  • The construction uses a symmetric profile attaining maxq∈Ai ui(q, . . . , q) as its cooperative profile.The passage states that this profile gives every firm profit above uN.Source: §4.2 · p. 19
  • With identical cost functions and symmetric qN, that profile gives every firm profit maxq∈Ai ui(q, . . . , q) > uN.Source: §4.2 · p. 19
  • When maximal symmetric profit equals uC, the construction’s bound reaches 1−ε for any ε > 0.This is the symmetric case of the bound obtained by substituting the construction’s choices into (18).Source: §4.2 · p. 19

5 Conclusion

The paper characterizes how episodic belief testing and value-dependent exploration select equilibria in discounted Markov games. In bounded-recall repeated games, longer recall does not decrease the selected minimum transformed value; under stated Cournot conditions, stable outcomes are collusive and symmetric firms can approach monopoly profits.

5 Conclusion

  • Stochastically stable states maximize the minimum transformed value among consistent states and induce approximate stationary Nash equilibria under suitable learning parameters.The analysis accommodates consistency tests satisfying the required error bounds, established for a generalized likelihood ratio test.Source: §5 · p. 19
  • Longer public recall does not decrease the selected minimum transformed value; in Cournot competition, belief-based collusion is nondecreasing in recall while actual-payoff collusion is approximately monotone.The conclusion states that the actual-payoff index obeys an approximate monotonicity bound.Source: §5 · p. 19
  • With sufficiently long recall, patient firms, accurate monitoring, and suitable learning parameters, every stochastically stable Cournot state yields collusion.The collusion index is positive, and for symmetric firms selected outcomes can yield joint profits arbitrarily close to the monopoly level.Source: §5 · p. 19
  • The current implementation requires model information, coordinated epochs and restarts, and faces scalability limits as the state space grows, particularly with public recall.The paper identifies decentralized and scalable implementations preserving the equilibrium-selection criterion as future work.Source: §5 · p. 19

A Proof of Proposition 1

The proof establishes regularity of the smooth best-response construction, obtains a fixed point, and uses approximation bounds to show that its policy profile is an ϵ-stationary Nash equilibrium.

A Proof of Proposition 1

  • The regularized Bellman operator has a contraction property, and the softmax map is continuous.These properties support the smooth best-response construction used in the proof.Source: A Proof of Proposition 1 · p. 20

Proof of Proposition 1.

  • The smooth best response is Lipschitz in beliefs, enabling the continuity argument for the fixed-point map.The proof derives this property using contraction and a Lipschitz bound for softmax in the Q-value vector.Source: Proof of Proposition 1 · pp. 20–21
  • Continuity of the best-response map yields a fixed point through Brouwer’s theorem, which is then rounded to a policy profile.The proof invokes the fixed point and simplex rounding before applying its approximation bounds.Source: Proof of Proposition 1 · pp. 21–22
  • The approximation bounds imply that the resulting policy profile is an ϵ-stationary Nash equilibrium.The proof bounds regularization error by σ log(max_j |A_j|)/(1−δ) and the remaining term by 2K_Vτ, with each at most ϵ/2.Source: Proof of Proposition 1 · p. 23

B Proof of Proposition 2

The proof reduces likelihood testing to finitely many representatives, then uses likelihood bounds and a martingale argument to control Type I errors across states.

B Proof of Proposition 2

  • The test uses the signal distribution induced by a candidate opponent policy, with positive likelihood denominators under the full-support assumption.The proof sets its threshold using a Markov-inequality bound and the number of likelihood representatives.Source: B Proof of Proposition 2 · pp. 23, 25
  • The observations enter each state’s likelihood through counts of action-signal pairs, allowing a finite representative set of candidate policies.For each count array, the proof chooses a likelihood maximizer from the mixed-strategy set.Source: B Proof of Proposition 2 · p. 23
  • The likelihood maximizers exist by continuity and compactness, and restricting to them preserves the relevant likelihood comparison.The proof also handles the case where all null likelihoods vanish, for which both sides of the stated equality are −∞.Source: B Proof of Proposition 2 · p. 24
  • A martingale likelihood argument and a union bound over candidates and states control the probability that the true policies fail the consistency test.The true profile belongs to the null candidate set at every state, and the resulting Type I bound holds for every positive epoch length T.Source: B Proof of Proposition 2 · pp. 24–25

3. Separation from null candidates. Define

This proof establishes separation from null candidates and uses state visits to bound Type II testing error. For sufficiently long epochs, the testing conditions hold for every player and state.

3. Separation from null candidates. Define

  • A state maximizing the belief-policy discrepancy separates each null candidate by at least d, yielding a signal-affinity bound with β = π_minκ^2d^2/2 > 0.The positive separation follows from the minimum over finitely many strictly positive discrepancies; the affinity bound then limits distinguishability at the selected state.Source: §3 · p. 25
  • The Type II event is split by whether visits meet a threshold, combining the visit-count bound with the error bound conditional on sufficiently many visits.The resulting bounds are combined using Markov’s inequality and the logarithmic estimate in the proof.Source: §3 · pp. 25–27
  • Reachability gives a positive lower bound on the chance of visiting the selected state in each complete block, enabling a visit-count bound without assuming independence.The proof divides the epoch into blocks of m + 1 stages and uses Hoeffding’s lemma and iteration over blocks to control visits.Source: §3 · pp. 26–27
  • For every integer T ≥ T̄(ξ), the Type II error is at most ξ^r̄, and together with the Type I bound this establishes Assumption 6 for all players and states.The proof obtains the bound by controlling the logarithm of the error bound and choosing the epoch length sufficiently large.Source: §3 · pp. 27–28

C Sufficient Condition for Assumption 5

A sufficient condition for Assumption 5 is a strictly positive separation margin across players and beliefs. The condition holds for all sufficiently small positive τ.

C Sufficient Condition for Assumption 5

  • The image-size condition gives a positive separation margin for every player and belief, so Assumption 5 holds for every τ ∈ (0, τ̄).The proof adapts Yang and Wu [19, Lemma 7] to full stationary-policy profiles by replacing distances with maximum statewise Euclidean distances.Source: C Sufficient Condition for Assumption 5 · p. 28

D Proof of Theorem 1

The proof derives a max–min selection rule by analyzing perturbations, recurrent states, and transition resistances. The stochastically stable consistent states are approximate stationary Nash equilibria selected by transformed discounted values.

D Proof of Theorem 1

  • Stochastically stable states follow the max–min rule over players’ transformed discounted values, and the selected states satisfy the approximate-equilibrium conclusion.When each transformation is the identity, the rule uses untransformed discounted values.Source: D Proof of Theorem 1 · pp. 28, 31, 32
  • The proof adapts the prior three-step approach to state-dependent beliefs and stationary policies, using testing-error bounds, recurrent classes, and resistance trees.The steps establish regular perturbation and transition resistances, characterize recurrent classes, then compare paths between consistent states.Source: D Proof of Theorem 1 · pp. 28, 31
  • The perturbed process converges to the unperturbed process, and normalized transition probabilities converge to positive finite limits that verify the resistance formula.The proof compares actual and auxiliary processes by coupling their test outcomes and bounding the probability of any incorrect test.Source: D Proof of Theorem 1 · pp. 29–30
  • The unperturbed process has singleton recurrent classes exactly at consistent states, which are absorbing; every inconsistent state can reach one within two transitions.Consistency requires beliefs to be within tolerance of opponents’ policies at every state.Source: D Proof of Theorem 1 · pp. 28, 30, 31
  • The least resistance from a consistent state to any other consistent state depends only on the departing state and equals its minimum transformed discounted value across players.A path attaining the bound first changes the belief of a player with minimum transformed value, then reaches the destination without further exploration resistance.Source: D Proof of Theorem 1 · pp. 31–32
  • Because every tree rooted at a state sums the same departing-state contributions, stochastic potential yields the max–min selection rule.The resistance-tree criterion identifies states with minimum stochastic potential as stochastically stable.Source: D Proof of Theorem 1 · p. 32

Related papers

Loading 2610.36306v1…