# Collusive Outcomes Without Collusion:
Algorithmic Pricing in a Duopoly Model

In-Koo Cho  Department of Economics
Emory University  and  Noah Williams  Miami Herbert Business School
University of Miami

###### Abstract.

We develop a model of algorithmic pricing which shuts down every channel for
explicit or implicit collusion, and yet still generates collusive outcomes. We
analyze the dynamics of a duopoly market where both firms use pricing
algorithms consisting of a parameterized family of model specifications. The
firms update both the parameters and the weights on models to adapt
endogenously to market outcomes. We show that the market experiences recurrent
episodes where both firms set prices at collusive levels. We analytically
characterize the dynamics of the model, using large deviation theory to
explain the recurrent episodes of collusive outcomes. Our results show that
collusive outcomes may be a recurrent feature of algorithmic environments with
complementarities and endogenous adaptation, providing a challenge for
competition policy.

##  1\. Introduction

In early February 2024, Senator Amy Klobuchar (D-MN), Chairwoman of the Senate
Judiciary Subcommittee on Competition Policy, Antitrust, and Consumer Rights,
introduced the Preventing Algorithmic Collusion Act.

> “Price fixing is illegal under our antitrust laws, but the development of
> automated price-setting algorithms can create loopholes in current law that
> could be used to unfairly raise prices on everything from rent to
> rideshares,” said Klobuchar. “My bill will strengthen antitrust law and
> guarantee needed transparency to prevent companies from using algorithms to
> fix prices to ensure consumers are able to get the full benefits of
> competition.” (Klobuchar, 2024)

The proposed legislation focuses on algorithms which use non-public competitor
data, which could potentially be used by pricing algorithms to engage in a
form of tacit collusion, without needing an explicit agreement or
communication. While there seems to be agreement that the current legal and
regulatory framework in the United States cannot address algorithmic collusion
which arises in the absence of communication, this particular proposed
legislation is just one example of the increasing interest in adapting the
current framework.111See Harrington (2019), Ezrachi and Stucke (2020), MacKay
and Weinstein (2022), and Stucke (2023) for some discussions. For example,
Stucke (2023) states “…[P]ricing algorithms continuously monitor and respond
to competitors’ online pricing, thereby inhibiting rivals from gaining sales
through discounts. Detecting and challenging such collusion is challenging, as
conscious parallelism alone does not violate the Sherman Act. There must be
proof of an agreement.” Similar legal and regulatory changes to address
algorithmic collusion have also been discussed in the EU and the OECD.222See
Calzolari (2021) and OECD (2017), for example.

The legal and regulatory interest in pricing algorithms draws on both
empirical and theoretical work in economics showing that algorithmic pricing
may lead to firms to set supra-competitive prices.333See Deng (2024) for a
good recent survey. We discuss the related literature more below. While some
types of algorithms and some forms of algorithmic interactions may be amenable
to legal or regulatory sanction, in this paper we illustrate the limits of
competition policy. We develop an example that rigorously eliminates all
possible channels of collusion between firms, but yet generates collusive
outcomes. Coordinated price increases to collusive levels in markets populated
by algorithmic price setters therefore cannot be used as evidence of
collusion, unless augmented by other evidence such as the inside information
about the algorithm itself.

Any legal or regulatory framework must distinguish between outcomes and the
mechanisms that lead to them. We define collusive outcomes as prices above the
competitive level, which are also commonly known as supra-competitive
outcomes. We use the former term because the collusive outcome has precise
meaning in our model, as the cartel or joint monopoly outcome. As for the
mechanisms that generate outcomes, Harrington (2019) provides a useful
definition: “Collusion is when firms use strategies that embody a
reward–punishment scheme which rewards a firm for abiding by the supra-
competitive outcome and punishes it for departing from it.”

In order to achieve implicit or explicit collusion, we typically need one or
more of the following conditions to hold:

  * •

Communication between firms. Even though explicit communication is blocked by
law, the firms can implicitly communicate with each other via rational
expectations about their opponent’s strategy.

  * •

Agreement. Firms must agree over the target outcome and the punishment needed
to enforce the agreement. Agreement can be explicit or tacit.

  * •

Patient players. Unless a firm cares about future profits, no punishment is
effective. Without a credible punishment, no collusive agreement can be
sustained.

  * •

Ability to handle complex agreements. The punishment requires changing actions
according to the history of outcomes. An oligopolistic firm may have to
predict the response of the competing firm in response to violation of the
agreement, conditioned possibly on a long history of actions to implement a
credible punishment.

We construct a model of algorithmic interaction that shuts down every one of
these possible channels of collusion, yet recurrently generates collusive
outcomes. We show that two myopic firms that independently choose an
algorithmic pricing specification that they update over time can be led to
jointly increase prices to collusive levels. As we discuss, our model relies
on the combination of endogenous algorithmic selection and adaptation with an
endogenous data generating process.

Our paper is related to the previous work in economics analyzing algorithmic
collusion. Some of that work has shown that algorithmic pricing entails an
aspect of commitment, where prices are set more frequently than algorithms are
revised. This allows for algorithms to learn opponents’ strategies, as in
Salcedo (2015) and Lamba and Zhuk (2023), or for asymmetries in frequency or
commitment to lead to collusive outcomes as in Brown and MacKay
(2023).444Leisten (2024) studies the interaction between algorithmic pricing
and human overriding, showing that it can lead to Edgeworth price cycles
similar to the outcomes in our model. Our model lacks such commitment: firms
do not learn each other’s strategies, but instead treat the price process of
the competing firm as an exogenous process.

More closely related to our paper is work that has illustrated through
simulations how collusive outcomes can arise, seemingly spontaneously, through
the interaction of firms using algorithms that adapt prices over time. Some
important papers here include Waltman and Kaymak (2008), Hansen, Isra, and Pai
(2021), Calvano, Calzolari, Denicolò, and Pastorello (2020), and Asker,
Fershtman, and Pakes (2023).555While the other papers consider versions of
profit maximization, Hansen, Isra, and Pai (2021) assumes regret minimization
behavior, which is identical to the aspiration learning behavior. Cho and
Matsui (2005) examined aspiration learning dynamics in the prisoner’s dilemma
game to show that the collusive outcome is the unique stable solution under a
general condition. Although they differ in details, these papers share certain
features:

  1. (1)

They consider duopoly markets with strategic complements. The best response of
one firm is an increasing function of the action of the other firm.666Banchio
and Skrzypacz (2022) consider a related model of algorithmic competition in
auctions.

  2. (2)

They impose an exogenous algorithmic specification. The authors make explicit
assumptions on how each firm “models the behavior of the other firm,” which in
turn determines the dynamics.777A reinforcement learning algorithm (or
Q-learning algorithm) is a popular specification. Other learning rules such as
multi-armed bandit problems are used as well.

  3. (3)

Their analysis is based on simulations. Simulations of the algorithms produce
an outcome that deviates from one shot Nash equilibrium with a positive
frequency.

Recent work by Banchio and Mantegazza (2023) and Possnig (2023) provides some
analytic results in related settings, which we discuss in more detail below.

We keep feature (1), but change (2) and (3). Rather than maximizing a
discounted profit stream, we consider two duopoly firms that are myopic
optimizers, which makes collusion even more challenging. Instead of imposing a
particular algorithmic structure, we allow the firms to adapt the structure of
their algorithms over time. We want to understand why a firm chooses a
particular specification of the opponent’s behavior. Finally, instead of
numerical analysis, we pursue an analytic approach to understand precisely how
these features generate collusive outcomes between algorithmic duopolists,
offering new insight beyond what the numerical analysis in previous work can
provide.

We focus on a pricing algorithm, as defined in the Congressional legislation
discussed above:

> The term “pricing algorithm” means any computational process, including a
> computational process derived from machine learning or other artificial
> intelligence techniques, that processes data to recommend or set a price or
> commercial term that is in or affecting interstate or foreign commerce.
> United States, Congress, Senate (2024)

Instead of the reinforcement learning algorithms studied in the previous
literature, we assume that each firm has a family of parametric specifications
of its opponent’s pricing reaction function. Our model is built on Williams
(2001), who first observed collusive outcomes generated by duopolists who are
learning a linear reaction function of the competing firm. But instead of
imposing a particular model, we assume here that a duopolist entertains two
possible specifications: a “Nash reaction” where the competing firm does not
respond to its price, and a “linear reaction” where the competing firm’s
reaction function is a linear function of its own price. Facing model
uncertainty, a duopolist averages the two specifications by assigning them a
probability weight. The firm optimizes static profits under each
specification, and chooses a weighted best response. Then, based on
observations of realized prices and sales, each firm updates both the
parameters of each specification and the probability weights. We study the
dynamics of the adjustment process where prices, parameters, and
specifications all evolve endogenously over time.

Figure 1. Simulated prices in the duopoly model, with gain $\lambda=0.01$ and
shock variance $\sigma^{2}=0.0025$.

Our specification allows us to obtain precise analysis of both the limits and
time paths of the evolving duopoly market. The simple nature of the algorithms
employed and the market structure of our model make it easy to identify and
eliminate any possible channels of collusion.

We start with an observation that the static Nash equilibrium (or competitive
outcome) is the unique stable stationary point of the learning dynamics. Thus,
if the economy is initialized at the Nash equilibrium, the prices should stay
in a small neighborhood of the Nash equilibrium with probability close to 1 in
the limit. We also show that if the duopolists are committed to the “Nash
specification,” recurrent escapes to the collusive outcome do not arise.

But the algorithmic interactions lead to outcomes which are very different
from these Nash limit predictions. As in the sample simulation shown in Figure
1, the model has “rare” but recurrent episodes where prices increase to
collusive levels. These outcomes arise in the algorithmic specifications that
allow for non-trivial feedback. In these episodes, each duopolist’s “linear
reaction” specification captures that the sample paths of the pair of prices
are highly correlated, which leads to the collusive outcome.

Since each duopolist chooses a specification and its price independently, the
sample path of the two prices should be independent most of the time. A
collusive outcome is not an equilibrium of the algorithmic dynamics, as it
requires highly correlated pricing rules. Yet, it is a recurrently observed
event. Importantly, the subjective weight assigned to “linear reaction”
specifications converges to one, as the algorithm learns from the market data.
Thus recurrent episodes of collusive prices are a robust feature of our model.

Although the collusive outcome is an integrated part of the algorithmic
dynamics, such outcomes are not explained by common limit results applied in
the literature. These methods focus on analysis of the associated
deterministic dynamics of the stochastic system, such as the fluid equation or
the associated ordinary differential equation (ODE).888See Benaim (1996) for a
discussion of the deterministic dynamics of stochastic approximation and Meyn
(2007) for an overview of fluid limits. Related methods have been widely used
in economics, for example in Marcet and Sargent (1989), Evans and Honkapohja
(2001), and Fudenberg and Levine (1998). The deterministic component of the
algorithmic outcomes converge to the competitive, static Nash prices in the
limit, implying that the static Nash prices are the stable stationary point of
the learning dynamics.

Collusive outcomes occur for “non-limit” sample paths. Our goal is to
understand how the optimal forecasting scheme and the interaction between the
data generating process and the algorithm trigger the collusive outcome. We
show that the large deviation properties of the stochastic approximation
precisely identify the mechanism of the escape from the competitive outcome to
the collusive outcome.999Our approach explains why the episode of the escape
to a collusive outcome vanishes as the number of oligopolistic firms
increases. Banchio and Mantegazza (2023) investigated the dynamics “away” from
the stable point but fell short of formally explaining the switching mechanism
from the stable point to the (rare) escape path. Large deviation theory
explains the “switching mechanism,” which is crucial to our analysis. Since
the data generating process is endogenous, we use stochastic approximation to
analyze its asymptotic properties. The collusive outcomes is a “rare” event,
whose probability vanishes in the limit. Thus the analysis of the
deterministic limit dynamics cannot characterize such events. By examining the
large deviation properties of the algorithm as in Cho, Williams, and Sargent
(2002), Cho and Kasa (2017), and Williams (2019), we explain the frequency of
collusive outcomes, and why the outcomes differ across model specifications.
We also characterize the “most likely” trajectory from the competitive outcome
to the cartel outcome, which helps us understand the mechanism driving
collusive outcomes.

As in Figure 1, we find that in the algorithmic market both prices and profits
are higher on average than under competition, but the time paths display
significant fluctuations. Apparently collusive episodes of high prices are
followed by a series moves where firms undercut the opponent’s price. These
outcomes are reminiscent of the repeated game punishment strategies in price
wars like Green and Porter (1984) or cartel equilibria in Abreu, Pearce, and
Stachetti (1986). Calvano, Calzolari, Denicolò, and Pastorello (2020)
suggested that the collusive outcomes in their model were sustained by similar
punishment strategies. However the mechanism supporting high prices is quite
different in our environment, where collusive outcomes and reversion to
competitive outcomes emerge endogenously as a result of learning by firms that
are unable to implement complex repeated game strategies.

In our model firms’ prices are driven by independent shock processes. However
the firms will get correlated shock realizations with a small positive
probability. As firms update their reaction function estimates, they will
start to believe that their opponents will respond in kind to increases in
prices. The perceived changes lead them to jointly increase prices, which
reinforces their perceptions that the competing firm reacts to its own price
on a one-to-one basis. This process leads the firms to rapidly boost prices to
collusive levels near the joint monopoly outcome. At the collusive outcome,
the feedback process stops and the correlation between the two prices
vanishes. Eventually, the independent idiosyncratic shocks pull them back to
the Nash outcomes. Together, this produces a pattern of collusion and
reversion similar to the paths of play from repeated game strategies, but
entirely driven by the learning dynamics.

Beyond our application to algorithmic pricing, our analysis highlights the
important theoretical point that characterizing convergence and average limit
outcomes are not sufficient to characterize behavior, as emphasized by Sargent
(1999). Averaging over stochastic paths misses some important structure and
leads to different predictions. Banchio and Mantegazza (2023) and Possnig
(2023) both use related stochastic approximation results to characterize the
convergence of reinforcement learning rules to study the emergence of
collusive outcomes. Banchio and Mantegazza (2023) study the fluid limit of two
interacting myopic reinforcement learners. Similar to our model, they
emphasize how independent experimentation by players can produce correlated
outcomes through the algorithmic dynamics. However their mechanism and limit
results are different. They show that if the algorithms do not employ
sufficient experimentation, they may converge to limits that sustain non-
competitive outcomes. Possnig (2023) studies the stability of interactions of
agents using a more sophisticated actor-critic algorithm. He shows that by
expanding the state space that firms condition on, firms in a Cournot duopoly
may converge to a collusive outcome. Since both of these papers focus on the
deterministic limit dynamics, they cannot explain the recurrent stochastic
dynamics observed in simulations.

The rest of the paper is organized as follows. In the next section we lay out
the baseline model and the choice of model specification, all in a static
environment with fixed beliefs. Section 3 then introduces algorithm and its
dynamics. We characterize the limit outcomes, showing that all specifications
converge to the competitive outcome. However the different model
specifications have vastly different time series outcomes, which we illustrate
and discuss in Section 4, which motivates the rest of the paper. Section 5
then turns to the analysis of the model, presenting our main analytic results.
We provide a full formal analysis of belief updating and model specification,
showing providing precise analytic results characterizing the limit outcomes
and large deviation properties, and showing that the weight on the model with
feedback converges to one. Section 6 delves further into the details
underlying these results, analyzing dynamics assuming that firms maintain a
fixed, symmetric specification. Here we show that while the limit outcomes of
the specifications are the same, the large deviation properties are very
different. Section 7 provides a brief conclusion. The appendix contains
intermediate calculations, formal proofs, background results, and further
illustrations.

##  2\. Baseline Model and Specification Choice

We study a simple environment with strategic interaction, a textbook Bertrand
duopoly model. In this environment we suppose that the firms face uncertainty
about their opponents’ strategies, that we parameterize into different
specifications. Later we develop an algorithmic approach to pricing, which
considers both specification choice and updating.

###  2.1. Basic Setup

We start with a Bertrand duopoly market with differentiated products where two
firms are myopic optimizers. The demand for good $i\in\\{1,2\\}$ produced by
firm $i$ is

$q_{i}=A-Bp_{i}+Cp_{j}\qquad i\neq j\in\\{1,2\\}$ (2.1)

where $A,B,C>0$. Since $C>0$, two goods are strategic complements. We assume
that $B-C>0$ (that is, the demand of good $i$ is more elastic to the price of
good $i$ than the price of good $j\neq i$) to make the Nash equilibrium and
the cartel outcome well defined. The best response $b_{i}(p_{j})$ of firm $i$
against firm $j$’s price $p_{j}$ is

$b_{i}(p_{j})=\frac{A+Cp_{j}}{2B}$ (2.2)

The unique Nash equilibrium price is

$p^{N}=\frac{2A}{2B-C}.$

Let $\Pi^{N}$ be the Nash equilibrium payoff of a duopolist.

The second benchmark is the cartel outcome $(p^{C}_{1},p^{C}_{2})$ that solves
the joint maximization problem:

$\max_{(p_{1},p_{2})}p_{1}q_{1}+p_{2}q_{2}.$

A simple calculation shows

$p^{C}_{1}=p^{C}_{2}=\frac{A}{2(B-C)}.$

Let $\Pi^{C}$ be the payoff from the cartel outcome. Clearly we have

$\Pi^{C}>\Pi^{N}.$

###  2.2. Model Specification

While most of the previous learning and algorithmic pricing literature
considers a fixed subjective model specification, we embed the specification
choice as part of the interaction. The behavioral assumption behind a Nash
equilibrium is that firm $i$ treats firm $j$’s action as a constant and
optimizes against the constant function:

$p_{j}=\alpha^{0}_{i}.$ (2.3)

Let ${\mathcal{M}}^{0}$ be the set of all functions represented as (2.3),
where each firm perceives its opponent’s price as an unobserved constant.
Given $\alpha^{0}_{i}$, firm $i$ chooses its best response $b^{0}_{i}$ by
solving

$\max_{p_{i}}p_{i}(A-Bp_{i}+C\alpha^{0}_{i}),$

which gives the best response:

$b^{0}_{i}=\frac{A+C\alpha^{0}_{i}}{2B}.$

We let $\Pi^{0}_{i}$ denote the optimized profit for firm $i$ under model
$\mathcal{M}^{0}$.

Alternatively, firm $i$ may perceive that firm $j(\neq i)$ reacts to firm
$i$’s price as in (3.7). Let ${\mathcal{M}}^{1}$ be the set of all linear
reaction functions

$p_{j}=\alpha^{1}_{0i}+\alpha^{1}_{1i}p_{i}\qquad i\neq j\in\\{1,2\\}.$ (2.4)

We define the belief vector as
$\alpha^{1}_{i}=(\alpha^{1}_{0i},\alpha^{1}_{1i})$. Duopolist $i$ then chooses
its best response $b^{1}_{i}=b(\alpha^{1}_{i})$ by solving

$\max_{p_{i}}p_{i}(A-Bp_{i}+C(\alpha^{1}_{0i}+\alpha^{1}_{1i}p_{i})).$

For any vector $\alpha_{i}=(\alpha_{0i},\alpha_{1i})$, we define the best
response function:

$b(\alpha_{i})=\frac{A+C\alpha_{0i}}{2(B-C\alpha_{1i})}.$ (2.5)

Then we have $b^{1}_{i}=b(\alpha_{i}^{1})$, and we can also interpret
$b^{0}_{i}=b((\alpha^{0}_{i},0))$.

Clearly ${\mathcal{M}}^{0}$ is a subset of ${\mathcal{M}}^{1}$, and each
represents a plausible subjective specification. $\mathcal{M}^{0}$ depicts a
common derivation of Nash equilibrium which optimizes against a fixed
strategy, while $\mathcal{M}^{1}$ depicts a common derivation in a duopoly
setting, where the Nash equilibrium is at the intersection of firms’ reaction
functions.

We consider a game where each duopolist first chooses a specification from
${\mathcal{M}}_{i}\in\\{{\mathcal{M}}^{0},{\mathcal{M}}^{1}\\}$
$i\in\\{1,2\\}$. For any specification, each firm $i$ will employ a forecast
$f_{i}$ of the other firm $j$’s price, as $f_{i}=\alpha^{0}_{i}$ for
${\mathcal{M}}^{0}$ and $f_{i}=\alpha^{1}_{0i}+\alpha^{1}_{1i}p_{i}$ for
$\mathcal{M}^{1}$, then choose the corresponding response
$b(\alpha_{i})\in\\{b_{i}^{0},b_{i}^{1}\\}$. Our equilibrium concept, self-
confirming equilibrium, is a situation where each firm optimizes given a
specification and associated beliefs about the other firm, and each firm’s
forecasts are correct in equilibrium.

######  Definition 2.1.

$({\mathcal{M}}_{1},{\mathcal{M}}_{2})$ is a self-confirming equilibrium
specification, if
${\mathcal{M}}_{1},{\mathcal{M}}_{2}\in\\{{\mathcal{M}}^{0},{\mathcal{M}}^{1}\\}$,
and $\exists(\alpha_{1},\alpha_{2})\in({\mathcal{M}}_{1},{\mathcal{M}}_{2})$
such that:

$\displaystyle b_{i}$ $\displaystyle=$ $\displaystyle b(\alpha_{i})\ \text{ as
in (\ref{eq: br})},\qquad\forall i\in\\{1,2\\}$ $\displaystyle b_{j}$
$\displaystyle=$ $\displaystyle f_{i}(b_{i})\qquad\forall i\neq
j\in\\{1,2\\}.$

To be an equilibrium, the price of firm $i$ must be an optimal choice given
its perceived law of motion $p_{j}=f_{i}(p_{i})$ about how firm $j$ responds
to firm $i$, and the belief must be confirmed at the optimal choice. The
notion of equilibrium is weaker than Nash equilibrium, as we admit
misspecified beliefs about the opponent’s response outside the equilibrium
price.

The problem is that a pair of specifications can admit multiple self-
confirming equilibria. In Appendix A we show that for the specification
$({\mathcal{M}}^{1},{\mathcal{M}}^{1})$, a self-confirming equilibrium is
$\alpha^{1}_{i}=(p^{N},0)$, which supports that Nash equilibrium outcomes.
However the belief $\alpha^{1}_{i}=(0,1)$ is also a self-confirming
equilibrium, and it supports the collusive outcome $(p^{C},p^{C})$. We need a
criterion to select a self-confirming equilibrium for each pair of
specifications, which we turn to next. Further, the equilibria that we just
constructed were not arbitrary. We show below that the two symmetric
equilibria with $(\alpha_{1,i}=0,p_{i}=p^{N})$ and
$(\alpha_{1,i}=1,p_{i}=p^{C})$ are important reference points in the
algorithmic dynamics that we analyze.

##  3\. Dynamics of the Algorithm

In this section we describe the structure of the algorithmic pricing that the
firms employ. We suppose that, given a particular specification of the
opponent’s behavior, each firm learns in real time. Each firm sets its price
based on its current perception of its opponent’s behavior, then after
observing its opponents price, it updates its beliefs. Similar models of
adaptive learning are widely used both as stability and selection criteria for
equilibria and as models to explain observed behavior.101010See Fudenberg and
Levine (1998), Evans and Honkapohja (2001), and Sargent (1999) for an overview
and examples.

Instead of imposing a particular belief specification, we consider learning
with the endogenous choice of model specification. Rather than selecting a
single specification, we suppose that each firm engages in model averaging.
Such techniques are widely used in applied and empirical work, and are common
in economic forecasting.111111See Steel (2020) for a recent overview and
references. Facing model uncertainty, the duopolist wants to hedge against the
wrong choice of the specification by mixing the two specifications. The weight
on the different specifications will then be updated over time depending on
average forecast profits. We study the endogenous dynamics of model weights on
models and beliefs within in a model.

###  3.1. Layout

As described above, each duopolist entertains two specifications for the
behavior of the opponent. Instead of committing to a particular specification,
a duopolist averages the two specifications. Let $\pi_{i,t}$ be the
probability assigned to specification ${\mathcal{M}}^{1}$ by duopolist $i$ in
period $t$, which duopolist $i$ updates according to the average forecast
profit of ${\mathcal{M}}^{1}$ over the average forecast profit of
${\mathcal{M}}^{0}$. Ultimately, duopolist $i$ assigns a larger probability to
a specification forecasting a larger long-run average profit.

At the beginning of period $t$, the state of the algorithm of duopolist
$i\in\\{1,2\\}$ is given by the vector:

$\left(\pi_{i,t-1};\alpha^{0}_{0i,t-1};\alpha^{1}_{0i,t-1},\alpha^{1}_{1i,t-1};{\overline{\Pi}}^{0}_{i,t-1},{\overline{\Pi}}^{1}_{i,t-1}\right)$
(3.6)

Each firm’s behavior is described as an algorithm that updates this vector
recursively, where the dating convention captures the information available.
Here $\pi_{i,t}$ is the probability assigned to the hypothesis that the
opponent’s behavior is specified as $\mathcal{M}^{1}$, $\alpha^{0}_{0i,t}$ is
the coefficient for the specification of $\mathcal{M}^{0}$ as in (2.3),
$\alpha^{1}_{i,t}=(\alpha^{1}_{0i,t},\alpha^{1}_{1i,t})$ is the coefficient
vector of the linear reaction function in $\mathcal{M}^{1}$ as in (2.4), and
${\overline{\Pi}}^{k}_{i,t}$ is the average payoff of duopolist $i$ at the end
of period $t$ when duopolist $i$ is using specification ${\mathcal{M}}^{K}$
where $k\in\\{0,1\\}$.

The timing of the model is such that each firm enters with a belief
specification and model weight, chooses its price, and then based on its
observations, updates the parameters. We denote
$b^{0}_{i,t}=b(\alpha^{0}_{i,t-1})$ and $b^{1}_{i,t}=\alpha^{1}_{i,t-1}$ as
the recommended actions by $\mathcal{M}^{0}$ and $\mathcal{M}^{1}$,
respectively. Duopolist $i$ chooses the best response in period $t$ by mixing
the recommendations according to $\pi_{i,t-1}$:

$b_{i,t}=(1-\pi_{i,t-1})b^{0}_{i,t}+\pi_{i,t-1}b^{1}_{i,t}.$ (3.7)

From this target best response, we suppose that the actual price includes some
small noise:

$p_{i,t}=b_{i}+\epsilon_{i,t}$

where $\epsilon_{i,t}$ is an i.i.d. white noise with mean zero and variance
$\sigma^{2}_{i,t}$. The shock $\epsilon_{i,t}$ induces experimentation in
prices, with the degree of experimentation measured by the second moment. This
randomness could also arise from cost shocks, which naturally lead to
variation in prices. To simplify the notation, we assume that
$\sigma^{2}_{i,t}$ is independent over ${i,t}$, and

$\sigma^{2}=\sigma^{2}_{i,t}\qquad i\in\\{1,2\\},\ t\geq 1.$

Our main results remain valid as long as the ratio of
$\sigma^{2}_{1,t}/\sigma^{2}_{2,t}$ is uniformly bounded.

After observing $(p_{1,t},p_{2,t})$, duopolist $i$ updates the coefficients of
each specification. The coefficients for each specification under
${\mathcal{M}}^{0}$ and ${\mathcal{M}}^{1}$ are updated according to recursive
least squares. If duopolist $i$ opts for $\mathcal{M}^{0}$, he estimates the
average price of duopolist $j\neq i$:

$\alpha^{0}_{0i,t}=\alpha^{0}_{0i,t-1}+{\lambda_{t}}\left(p_{j,t}-\alpha^{0}_{0i,t-1}\right).$
(3.8)

Here $\lambda_{t}$ is the gain sequence, which represents the weight on new
information. We mostly focus on the case where $\lambda_{t}=1/t$, which means
that each firm believes its opponent is playing a fixed strategy. Such a
setting means that the estimate is simply the sample mean of the opponent’s
price:

$\alpha^{0}_{i,t-1}=\frac{1}{t-1}\sum_{s=1}^{t-1}p_{j,s}.$

Some of our illustrations use the constant gain case where
$\lambda_{t}=\lambda$ is a small positive constant. A constant gain is
appropriate when a firm believes its opponent’s strategy drifts over time. The
same basic techniques and characterizations apply for the decreasing and
constant gain cases, and only the sense of convergence differs.

If duopolist $i$ opts for $\mathcal{M}^{1}$, he estimates the slope
$\alpha^{1}_{1i,t}$ and the intercept $\alpha^{1}_{0i,t}$:

$\displaystyle\left[\begin{matrix}\alpha^{1}_{0i,t}\\\
\alpha^{1}_{1i,t}\end{matrix}\right]$ $\displaystyle=$
$\displaystyle\left[\begin{matrix}\alpha^{1}_{0i,t-1}\\\
\alpha^{1}_{1i,t-1}\end{matrix}\right]+{\lambda_{t}}R^{-1}_{i,t-1}\left[\begin{matrix}1\\\
p^{1}_{i,t}\end{matrix}\right]\left(p_{j,t}-\alpha^{1}_{0i,t-1}-\alpha^{1}_{1i,t-1}p^{1}_{i,t}\right)$
(3.9) $\displaystyle R_{i,t}$ $\displaystyle=$ $\displaystyle
R_{i,t-1}+{\lambda_{t}}\left(\left[\begin{matrix}1&p^{1}_{i,t}\\\
p^{1}_{i,t}&(p^{1}_{i,t})^{2}\end{matrix}\right]-R_{i,t-1}\right).$

Here $R_{i,t}$ is an estimate of the second moment matrix of the regressors.
In the specification ${\mathcal{M}}^{0}$. the only regressor is a constant, so
we can dispense with $R_{i,t}$. But under ${\mathcal{M}}^{1}$, the second
moment matrix adjusts the speed of update of the intercept and slope
parameters, as more volatile regressors naturally convey less information.

We can calculate the profit forecast by specification ${\mathcal{M}}^{0}$

$\Pi^{0}_{i,t}=p^{0}_{i,t}(A-Bp^{0}_{i,t}+Cp_{j,t})$

and by specification ${\mathcal{M}}^{1}$

$\Pi^{1}_{i,t}=p^{1}_{i,t}\left(A-Bp^{1}_{i,t}+Cp_{j,t}\right)$

from which we update the average expected payoff

$\displaystyle{\overline{\Pi}}^{0}_{i,t}$ $\displaystyle=$
$\displaystyle{\overline{\Pi}}^{0}_{i,t-1}+{\lambda_{t}}\left(\Pi^{0}_{i,t}-{\overline{\Pi}}^{0}_{i,t-1}\right)$
$\displaystyle{\overline{\Pi}}^{1}_{i,t}$ $\displaystyle=$
$\displaystyle{\overline{\Pi}}^{1}_{i,t-1}+{\lambda_{t}}\left(\Pi^{1}_{i,t}-{\overline{\Pi}}^{1}_{i,t-1}\right)$

and

$\pi_{i,t}=\pi_{i,t-1}+{\lambda_{t}}\left({\mathbb{I}}\left({\overline{\Pi}}^{1}_{i,t}>{\overline{\Pi}}^{0}_{i,t}\right)-\pi_{i,t-1}\right).$

This completes the specification of the updating process of the algorithm.

###  3.2. Implications for Collusion

Before we turn to analysis of the model, we note several of its important
features. In particular, we have shut down all avenues for either explicit or
implicit collusion.

First, there is no communication between firms, which would be the most
obvious and overt way to implement a collusive agreement. Here each duopolist
behaves independently, without any explicit or implicit communication.
Moreover, each firm chooses its model specification independently each period,
and given its specification, employs independent exploration in setting its
price.

In the repeated game oligopoly literature, including the classic works of
Green and Porter (1984) and Abreu, Pearce, and Stachetti (1986), collusion can
also be sustained in equilibrium by patient firms who implement rather complex
strategies. Calvano, Calzolari, Denicolò, and Pastorello (2020) suggest that
the collusive outcomes they found were due to the algorithms learning repeated
game strategies. Our specification eliminates such possibilities in two ways.
First, each duopolist is myopic, maximizing its one-period payoff. This
shortcuts the possibility of implementing repeated game strategies with
punishment phases, which are key to sustaining collusion. On top of that, we
consider an algorithmic specification with fairly minimal complexity. Each
duopolist $i$ only remembers the few parameters in its state vector (3.6), and
does not know anything about duopolist $j$’s parameters or algorithm at all.
Our duopolists are not capable of handling a complex repeated game strategy,
which is essential for sustaining implicit collusion.

Other avenues for collusion rely on rational expectations, where firms
correctly their forecast opponent’s behavior. But in our setting, duopolist
$i$’s algorithm does not know the internal state of the algorithm of the
competing firm. Consequently, duopolist $i$’s algorithm cannot predict how the
competing firm $j$ would react if $i$ were to deviate. Thus we differ from the
algorithmic collusion literature where algorithms imply a form of commitment
where firms can learn opponents’ strategies, as in Salcedo (2015) and Lamba
and Zhuk (2023), or where asymmetries in frequency or commitment to lead to
collusive outcomes, as in Brown and MacKay (2023).

Even more, in our setting both firms subjective models are misspecified.
Duopolist $i$ does not know the probabilistic properties of its opponent’s
price $p_{j,t}$, treating it as an exogenous stochastic process. Our notion of
self-confirming equilibrium imposes weak, on-path restrictions on firms’
beliefs, which hold in the limit of the learning process.

###  3.3. Summary of Stability under Learning

We now analyze the long-run behavior of the algorithmic interactions. Here we
briefly summarize the key results on the limit of beliefs, which illustrates
the ineffectiveness of standard stability conditions based on the analysis of
the associated continuous time dynamics. We apply standard stochastic
approximation results in the learning literature, providing more detail below.

Given a pair of specifications
$({\mathcal{M}}_{1},{\mathcal{M}}_{2})\in\\{{\mathcal{M}}^{0},{\mathcal{M}}^{1}\\}^{2}$,
let $\Pi^{k\ell}_{i,t}$ be the profit of firm $i$ in period $t$ if duopolist 1
chooses ${\mathcal{M}}^{k}$ and duopolist 2 chooses ${\mathcal{M}}^{\ell}$
where $k,\ell\in\\{0,1\\}$.

######  Proposition 3.1.

Suppose that firm $i$ chooses ${\mathcal{M}}^{1}$. Then, firm $i$ uses the
linear reaction function to forecast firm $j$’s response

$p_{j}=\alpha_{0i,t}+\alpha_{1i,t}p_{i}$

by estimating the coefficients $(\alpha^{1}_{0i,t},\alpha^{1}_{1i,t})$, and

$\lim_{t\rightarrow\infty}(\alpha^{1}_{0i,t},\alpha^{1}_{1i,t})=(p^{N},0)$

with probability 1. Moreover, for any combination
$({\mathcal{M}}^{k},{\mathcal{M}}^{\ell})$ of specifications, the average
profit ${\overline{\Pi}}^{k\ell}_{i,t}$ of firm $i$ converges to the Nash
equilibrium profit:

$\lim_{t\rightarrow\infty}{\overline{\Pi}}^{k\ell}_{i,t}=\Pi^{N}$

with probability 1.

As long as $\epsilon_{1,t}$ and $\epsilon_{2,t}$ are independent, the slope of
the estimated reaction function must be zero on average. If we select a self-
confirming equilibrium, which is a stable stationary solution of the least
square learning dynamics, the payoff matrix of the specification game is
written in terms of the payoff of duopolist 1:

$\bordermatrix{&{\mathcal{M}}^{0}&{\mathcal{M}}^{1}\cr{\mathcal{M}}^{0}&\Pi^{N},\Pi^{N}&\Pi^{N},\Pi^{N}\cr{\mathcal{M}}^{1}&\Pi^{N},\Pi^{N}&\Pi^{N},\Pi^{N}\cr}.$
(3.10)

The stability of the mean dynamics of the learning algorithm is a widely used
selection criterion. Here stability under learning results reduces the set of
the self-confirming equilibria to a unique equilibrium where the duopolists
play the Nash equilibrium regardless of the specification. For any combination
of specifications, the stable stationary payoff from the learning dynamics is
the Nash equilibrium payoff. The mean dynamics cannot explain why a firm
chooses a particular specification of the response of the other firm. We need
a refinement of self-confirming equilibrium.

##  4\. Illustrations and Motivation

While the limit of all combinations of specifications is the Nash outcome
$p^{N}$, we saw above in Figure 1 that the algorithmic price dynamics display
sample path properties that are quite different. The time series feature
recurrent escapes from the Nash price $p^{N}$ to an outcome near the collusive
price $p^{C}$. Here we illustrate these features and discuss the mechanisms
driving these dynamics. While the limits of the symmetric specifications where
both firms use $\mathcal{M}^{0}$ and both use ${\mathcal{M}}^{1}$ are the
same, $({\mathcal{M}}^{0},{\mathcal{M}}^{0})$ and
$({\mathcal{M}}^{1},{\mathcal{M}}^{1})$ imply very different “non-limit
outcomes.” Below we show that these differences are due to different large
deviation properties.

Figure 2. Top panel: simulated best responses $b_{i,t}$. Bottom panel:
probability on specification $\mathcal{M}^{1}$, $\pi_{i,t}$.

###  4.1. Simulated Algorithmic Dynamics

We have already seen the striking behavior of the algorithmic prices in Figure
1 above. Figure 2 plots some of components underlying the price dynamics. For
all of our illustrations, we use the following parameters: $A=1$, $B=1$,
$C=0.7$. With this parametrization, the Nash price is
$p_{N}=A/(2B-C)=1/(2-0.7)\approx 0.77$, while the cartel price is
$p^{C}=A/(2(B-C))=1/0.6\approx 1.67$. We assume the price exploration shocks
$\epsilon_{i,t}$ are i.i.d. normal, independent across firms, with mean zero
and stand deviation $\sigma^{2}=0.025$. Later we explore the consequences of
varying the degree of price exploration through $\sigma^{2}$, which has a key
difference across the model specifications. Most of our plots use a constant
gain $\lambda=0.01$. As we discuss below, as the gain $\lambda$ shrinks, the
time between the episodes of price changes increases exponentially, consistent
with convergence to the Nash outcome in the small gain limit.

The top panel of Figure 2 plots the “intended” part of the price series,
$b_{i,t}$, for the two firms in the same simulation as in Figure 1 above. This
includes the averaged best responses across the two model specifications,
$(1-\pi_{i,t})b^{0}_{i,t}+\pi_{i,t}b^{1}_{i,t}$, but not the exploration
component $\epsilon_{i,t}$ of prices. Thus it gives a less noisy version of
the price dynamics that we saw in Figure 1 above. In both figures, we plot the
last 5,000 periods of a 10,000-period simulation. The bottom panel of Figure 2
plots the weight $\pi_{i,t}$ that each firm puts on the reaction function
specification $\mathcal{M}^{1}$.

The convergence results in Proposition 3.1 suggest that, at least in the long
run, we would expect to see small fluctuations around the Nash equilibrium
price. But instead we observe recurrent episodes where both firms increase
their prices to collusive levels. The price increases occur roughly
simultaneously over just a few periods from the Nash equilibrium price $p^{N}$
to near the collusive, joint monopoly price $p^{C}$.121212The average price
during these episodes falls just short of $p^{C}$, for reasons we will
describe below. Prices remain near the joint monopoly levels for a while, then
firms cut prices in a staggered fashion, and gradually both prices return to
the Nash equilibrium levels. Prices remain low for a while, until another
episode where they increase prices again.

As we discuss below, the escapes from the Nash price $p^{N}$ to higher prices
occur under the reaction-function specification $\mathcal{M}^{1}$, but not
under the constant specification $\mathcal{M}^{0}$. Moreover these “collusive
episodes” (without collusion) of higher prices are clearly beneficial to
firms, allowing them to earn higher profits. Thus, as shown in the bottom
panel of Figure 2, both firms put nearly all weight on specification
$\mathcal{M}^{1}$, with $\pi_{i,t}\approx 1$ for most of the sample. The
deviations from a model probability near unity occur during the asymmetric
episodes of price cutting, with the second-moving firm finding temporarily
higher profits under the constant $\mathcal{M}^{0}$ specification. Such
asymmetric deviations are short-lived, and we show below that $\pi_{i,t}$
converges to one in the limit.

While the price dynamics are stochastic, they display clear and regular
features. The timing of the episodes of price increases is random, and when
the gain $\lambda$ is smaller, the dynamics slow and firms spend more time
near the Nash level. But the collusive episodes recur and have similar
character: each time, both firms act nearly in unison to increase prices to
the same levels. This correlation in price increases is striking, as firms
operate, choose algorithms, update, and experiment independently.

The correlation in prices breaks down once the firms approach the cartel
price, and the price-cutting episodes are asymmetric. One firm initially
undercuts the other, dropping part of the way back down toward the Nash price.
While one firm initially remains at a higher price, it later responds by
further undercutting down to near the Nash level. Figure 2 shows that the
price-cutting episodes are regular, but there is also a random component in
determining which firm cuts price first.

###  4.2. Differences Across Specifications

Figure 3. Left panel: $\mathcal{M}^{0}$ predicted price $\alpha^{0}_{i,t}$.
Right panel: $\mathcal{M}^{1}$ reaction function slope $\alpha^{1}_{1i,t}$

We find that the sample average payoff from ${\mathcal{M}}^{1}$ is larger than
that from ${\mathcal{M}}^{0}$, even though both average payoffs converge to
the same limit $\Pi^{N}$. Firms endogenously and independently find that
entertaining a reaction function specification leads to higher profits, which
in turn increases the probability weight assigned to ${\mathcal{M}}^{1}$. In
the end, $\pi_{i,t}\rightarrow 1$, so the price dynamics are dictated by
$({\mathcal{M}}^{1},{\mathcal{M}}^{1})$, generating recurrent excursions from
the Nash to the collusive outcome.

We now describe in more detail the dynamics of beliefs and prices in each
specification. Figure 3 shows the time series of the key components of beliefs
in the two specifications. Here we focus on the first half of the sample from
the figures above, to isolate a single episode of price increases and
decreases. The left panel of the figure shows the time series of the estimated
coefficients $\alpha^{0}_{i}$ under $\mathcal{M}^{0}$ for each of the two
firms. When each firm uses $\mathcal{M}^{0}$, the estimated price exhibits
small fluctuations around the Nash equilibrium price $p^{N}$, shown with a
dashed line. Note that the scale is smaller here than on the price dynamics
plots above in order to make the belief changes visible. Since each firm
estimates that its opponent plays close to $p^{N}$, the firms’ best responses
$b^{0}_{i,t}$ will also be close to $p^{N}$, and most price fluctuations come
from the price shocks $\epsilon_{i,t}$ rather than revisions of beliefs. There
also appears to be no correlation in the deviations of firms’ beliefs from the
equilibrium levels, so prices would be uncorrelated as well. When the gain
$\lambda$ shrinks, the distribution of beliefs becomes more tightly
concentrated on the Nash equilibrium price.

However very different outcomes emerge when each firm uses the reaction-
function specification $\mathcal{M}^{1}$. Firms now estimate an intercept and
a slope, and we saw in Proposition 3.1 that $\alpha_{i,t}$ converges to
$(p^{N},0)$. The right panel of Figure 3 shows the slope coefficients
$\alpha^{1}_{1,it}$ for each of the two firms. These are the key parameters
which drive the price dynamics in Figures 1 and 2 above. There are large
fluctuations in these estimated slopes, which increase in near unison from
near zero to near one during the episodes of price increases, then decline
asymmetrically and non-monotonically back to zero during the episodes of price
cuts.

###  4.3. Objectives

The central idea of stochastic approximation, which we applied in Proposition
3.1, is to approximate the stochastic dynamics by deterministic dynamics
represented by an ordinary differential equation. Relying on a law of large
numbers, this approximation keeps track of the dynamics of the mean of the
stochastic process, thus called the mean dynamics. The conventional learning
literature focuses on the stable stationary point of the mean dynamics. Our
exercise reveals that as we approximate a stochastic process by deterministic
dynamics, we “wash out” important information about the stochastic process.
While every combination of the specifications shares the Nash equilibrium
outcome as the unique stable stationary point, the analysis of
${\mathcal{M}}^{0}$ and ${\mathcal{M}}$ reveals that the sample path of prices
under the two specifications show dramatically different properties.

In our analysis, we examine the center of the distribution over the sample
path, namely the mean dynamics, as well as the tail of the distribution where
a rare event, such as the escape from the neighborhood of the stable
stationary outcome, occurs. By using large deviation theory to analyze the
tail portion of the probability distribution over sample paths, we explain
several features the mean dynamics and its stability analysis cannot explain.

  * •

Why are the escapes from the stable point significantly more frequent under
$({\mathcal{M}}^{1},{\mathcal{M}}^{1})$ than
$({\mathcal{M}}^{0},{\mathcal{M}}^{0})$?

  * •

Why does the escape path always point to the collusive outcome?

  * •

How can we explain the almost perfect coordination of the escape time and path
between the two duopolists, even though the selection of the specification and
the exploration are independent?

An essential feature of our model is that the specification of the model is
endogenously determined. In conventional learning models, the specification of
the model is imposed by an outsider, and the players inside of the model can
learn about the parameters. Instead, we assume that each firm chooses a
specification from $\\{{\mathcal{M}}^{0},{\mathcal{M}}^{1}\\}$
probabilistically, according to the average performance of each specification.

###  4.4. Discussion of the Mechanism Driving the Dynamics

Figure 4. Simulated best responses for the two firms, $b_{1,t}$ versus
$b_{2,t}$. Also shown are the Nash price $p^{N}$, the collusive price $p^{C}$,
and the 45 degree line connecting them.

Before proceeding to the analysis of the algorithm, we provide an overview and
discussion of the key mechanism of the dynamics which drive our results.
Figure 4 plots the best responses for the two firms, $b_{1,t}$ and $b_{2,t}$
as defined in (3.7). In Figure 2 above we saw these time series, but now we
plot them against each other. The figure also shows the self-confirming and
Nash limit outcome $p^{N}$ along with the collusive price $p^{C}$. The
episodes of price increases are rapid, correlated movements nearly along the
45 degree line. The price-cutting episodes are slower, asymmetric movements
where prices drop back down to $p^{N}$. The correlation and lack thereof are
key elements we now describe.

We have seen that the key features of the time series are driven by the
specification $\mathcal{M}^{1}$. In the self-confirming equilibrium, which is
the limit of learning, the slope of each firm’s estimated reaction function is
zero, so each firm believes that its opponent will set prices independently of
its own price. With fixed beliefs, the firms’ prices are just i.i.d.
fluctuations around the fixed best response function $b(\alpha^{1}_{i})$. Thus
the equilibrium of the learning dynamics is the same in $\mathcal{M}^{1}$,
when firms estimate a reaction function, as in $\mathcal{M}^{0}$ when they
forecast their opponent’s price as an average of past prices.

But even though the experimentation processes $\\{\epsilon_{1,t}\\}$ and
$\\{\epsilon_{2,t}\\}$ are mutually independent, there will occasionally be
correlated sequences of realizations. These sequences are rare, and thus do
not affect the mean of the limit distribution, as the events are “washed out”
in calculating the mean dynamics by invoking a law of large numbers. However
tail events matter substantially and drive the key price dynamics, if the
duopolists respond to the rare events which in turn reinforce the beliefs of
the duopolists. It takes a relatively short sequence of correlated shocks to
trigger a sequence of changes in beliefs which are reinforced by the
endogenous best response dynamics, leading to rapid movement away from the
limit point.

In particular, since firms under $\mathcal{M}^{1}$ are estimating reaction
functions, these correlated shock realizations – which make prices move
together – will increase the perceived slope. Once a firm starts to believe
its opponent’s price is be positively correlated with its own,
$\alpha_{1,i}>0$, it will increase its price. The perceived positive slope in
the reaction function effectively makes the firm’s residual demand less
elastic. Firm $i$ thinks that firm $j$ will respond to an increase in $p_{i}$
with an increase in $p_{j}$. Then firm $i$’s perceived demand will be less
responsive to its own price, and it will optimally increase its price.

Thus the correlated realizations lead to an increase in the perceived slope
$\alpha^{1}_{1,it}$ and a corresponding increase in the expected price
$b(\alpha^{1}_{i,t})$. The increase in the average price is a notable
deviation from recent observations, which were mostly clustered around the
Nash price. The new data point is an influential observation affecting the
firm’s estimated reaction function. Thus instead of just the random movements
in $\epsilon_{i,t}$, both firms increase $b^{1}_{i,t}$. Firms’ prices increase
together, and they rapidly adjust their estimated reaction function to account
for this observed correlation, which leads to further price increases. Thus
the initial movement in beliefs is locally self-reinforcing, with an increase
in perceived correlation leading to correlated behavior, which takes firms
farther away from the Nash limit outcome.

As the price increases continue and approach the joint monopoly price $p^{C}$,
the price increases slow down. Once firms’ reaction function slopes are
$\alpha^{1}_{i,t}=1$ they set the collusive price $p^{C}$, but at that point
do not further increase prices. With little or no change in the expected price
$b(\alpha^{1}_{i,t})$, the realized price movements then come to be driven
more by the independent shocks $\epsilon_{i,t}$.

Thus the perceived correlation starts to decline, and so do prices. The escape
dynamics leading to the price increases are symmetric, driven by correlated
behavior, but the price cuts which lead back to the Nash equilibrium level are
asymmetric, with firms undercutting each other. After remaining near the joint
monopoly price for a while, both firms start to cut prices slightly, then one
undertakes a larger price cut. The other firm keeps its price high for a
while, then undercuts its opponent to a lower price, which is later matched or
further undercut. The path of price cuts is asymmetric, and which firm starts
process with the larger initial cut is random. Eventually, the price
correlations decay back to zero, and prices approach the Nash equilibrium
level.

As we have emphasized, our model shuts down all avenues for collusion between
the firms. The episodes of “collusive outcomes” with high prices are “non-
limit events” driven by correlated shock realizations and the strategic
complementarity of the environment. All that is required is that firms simply
be minimally reactive to their observations of their opponent’s behavior,
which allows them to realize higher profits.

The remainder of the paper provides analytic backing to the description above.
We show that the specifications $\mathcal{M}^{0}$ and $\mathcal{M}^{1}$ have
the same limit outcome but very different large deviation properties. For the
specification $\mathcal{M}^{1}$, small deviations from the limit equilibrium –
in a particular direction, toward price coordination – are self-reinforcing,
and lead to the recurrent episodes of joint price increases.

###  4.5. Perturbed Game

Before proceeding to the analysis, we consider one further illustration, which
sheds light on the dynamics of the probability weight assigned to
${\mathcal{M}}^{1}$. We have seen that in the limit all specification choices
give rise to the same expected payoffs. But since firms’ specification weights
evolve endogenously along a sample path, what matters is not the limit (3.10),
but a perturbed version of obtained by replacing the payoff vector with the
sample average.

$\bordermatrix{&{\mathcal{M}}^{0}&{\mathcal{M}}^{1}\cr{\mathcal{M}}^{0}&{\overline{\Pi}}^{00}_{1,t},{\overline{\Pi}}^{00}_{2,t}&{\overline{\Pi}}^{01}_{1,t},{\overline{\Pi}}^{01}_{2,t}\cr{\mathcal{M}}^{1}&{\overline{\Pi}}^{10}_{1,t},{\overline{\Pi}}^{10}_{2,t}&{\overline{\Pi}}^{11}_{1,t},{\overline{\Pi}}^{11}_{2,t}\cr}$
(4.11)

Since $\Pi^{k\ell}_{i,t}\rightarrow\Pi^{N}$ $\forall k,\ell\in\\{0,1\\}$ and
$\forall i\in\\{1,2\\}$, it is not straightforward to differentiate one
average payoff from another. Nevertheless, the numerical simulations reveal a
useful pattern as we’ve seen. Evaluating the average payoffs in the
simulations leads to:

$\bordermatrix{&{\mathcal{M}}^{0}&{\mathcal{M}}^{1}\cr{\mathcal{M}}^{0}&0.5913,0.5913&0.5909,0.5911\cr{\mathcal{M}}^{1}&0.5911,0.5909&0.6796,0.6796\cr}$
(4.12)

While ${\mathcal{M}}^{1}$ is not a dominant specification over
${\mathcal{M}}^{0}$, it is a risk dominant specification with a very small $p$
value in the long run. We shall formalize the intuition.

We have seen above that the pair of specifications
$({\mathcal{M}}^{0},{\mathcal{M}}^{0})$ generates sample paths that stay in a
small neighborhood of Nash equilibrium price. On the other hand, the pair of
specifications $({\mathcal{M}}^{1},{\mathcal{M}}^{1})$ generates sample paths
which entail repeated excursions to the collusive price with almost perfect
coordination, returning to the Nash equilibrium in a less coordinated manner.
Thanks to the repeated excursions to the collusive outcome, the average profit
for firm $1$ is strictly higher than the Nash equilibrium payoff $\Pi^{N}$.

${\overline{\Pi}}^{11}_{1,t}\simeq
0.6796>0.5913\simeq{\overline{\Pi}}^{00}_{1,t}\simeq\Pi^{N}.$

If firm $1$ uses ${\mathcal{M}}^{0}$, his payoff is mainly independent of
duopolist 2’s specification, remaining close to Nash equilibrium payoff
$\Pi^{N}$.

${\overline{\Pi}}^{00}_{1,t}\simeq 0.5913\simeq
0.5909\simeq{\overline{\Pi}}^{01}_{1,t}.$

By the same token, if firm 2 uses ${\mathcal{M}}^{0}$, duopolist 1’s average
profit changes little by switching from ${\mathcal{M}}^{0}$ to
${\mathcal{M}}^{1}$. Consequently, ${\mathcal{M}}^{1}$ becomes the risk
dominant strategy. Since

${\overline{\Pi}}^{11}_{1,t}-{\overline{\Pi}}^{10}_{1,t}=0.0885\gg-0.0004={\overline{\Pi}}^{01}_{1,t}-{\overline{\Pi}}^{00}_{1,t},$

it takes only a small probability of firm 2 choosing ${\mathcal{M}}^{1}$ to
make ${\mathcal{M}}^{1}$ become the best response to duopolist 2’s choice of
(mixed) specifications.

##  5\. Analysis

We use stochastic approximation to analyze the asymptotic limits and the large
deviation properties of the endogenous variables in our model. In this section
we establish three main analytic results:

  1. (1)

under specification $\mathcal{M}^{0}$ each firm’s expected profits are
asymptotically equivalent to the Nash profits, while

  2. (2)

under $\mathcal{M}^{1}$ the firms will recurrently visit a neighborhood of the
collusive outcome and so earn higher profits, which together imply

  3. (3)

in the long run both firms will put probability one on specification
$\mathcal{M}^{1}$.

We state the main results in the text, but the proofs and some supporting
calculations are rather involved and are reported in Appendix B.

###  5.1. Large Deviations

While we work with different processes, we take reaction function coefficients
as an example. Given a discrete time stochastic process
$\\{\alpha^{1}_{i,t}\\}_{t=1}^{\infty}$, we construct a continuous time
process by linearly interpolating the values at $t$ and $t-1$. Since we are
interested in the tail behavior of the algorithm, as described in the appendix
we work with the left-shifted continuous time process
$\alpha^{1,K}_{i}(\tau)$, which is the right tail of the interpolated sample
path of $\\{\alpha^{1}_{i,t}\\}$ starting from time $K$.

We saw above that in the limit the algorithm converges to the Nash outcomes.
But we need to go beyond the convergence and stability results. The focus of
our investigation is the probability that the parameter estimates escape from
a small neighborhood of stable point. To do this, we use large deviation
theory, which characterizes events with limit probability zero. More detail on
the background and calculations is provided in Appendix E.1, and in Section
6.1 below.

For simplicity, we assume that

$\sigma^{2}_{1,t}=\sigma^{2}_{2,t}=\sigma^{2}\qquad\ \forall t\geq 1.$

The main results of the paper remains valid if
$\sigma^{2}_{2,t}\neq\sigma^{2}_{1,t}$, as long as the ratio is uniformly
bounded away from zero and from above. We assume that the exploration
probability does not decrease too quickly. We define $m(K+\tau)$ as the
smallest number $T$ satisfying $\sum_{t=t_{K}}^{T}\lambda_{t}\geq\tau$.

######  Assumption 5.1.

$\forall\tau>0$,

$\lim_{K\rightarrow\infty}\frac{\sigma^{2}_{m(K+\tau)}}{\sigma^{2}_{t_{K}}}=1.$

Roughly, $\sigma^{2}_{t}$ can converge to 0 at the same rate as $1/t^{\gamma}$
for some $\gamma\leq 1$. Let

${\hat{\epsilon}}_{i,t}=\epsilon_{i,t}/\sigma_{i,t}$

be the normalized exploration probability.

Let $I\mathrel{\mathop{\mathchar 58\relax}}X\rightarrow[0,\infty]$ be a non-
negative extended real valued function. In case of
$\alpha^{1}_{i,t}\in{\mathbb{R}}^{2}$, $X\subset{\mathbb{R}}^{2}$. Let

${\overline{\epsilon}}_{i,t}=\frac{1}{t}\sum_{k=1}^{t}{\hat{\epsilon}}_{i,t}$

be the average of ${\hat{\epsilon}}_{i,t}$. To avoid technical issues, we
impose mild regularity conditions satisfied by virtually all popular
distributions.

######  Assumption 5.2.

${\hat{\epsilon}}_{i,t}$ has a good rate function if for any closed subset $F$
and for any open subset $G$ of Borel set $X$,

$\displaystyle-\inf_{x\in F}I(x)$ $\displaystyle\geq$
$\displaystyle\limsup_{t\rightarrow\infty}\frac{1}{t}\log{\sf
P}\left({\overline{\epsilon}}_{i,t}\in F\right)$ (5.13) $\displaystyle\geq$
$\displaystyle\liminf_{t\rightarrow\infty}\frac{1}{t}\log{\sf
P}\left({\overline{\epsilon}}_{i,t}\in G\right)\geq-\inf_{x\in G}I(x).$ (5.14)

In addition, we assume that $\inf_{x\in G}I(x)<\infty$ and $\inf_{x\in
F}I(x)<\infty$.

This is an example of a large deviation statement, providing exponential
bounds on rare events. We do not assume that $I(x)$ is continuous, although
most popular distributions have continuous rate functions. Instead, we require
that $I(x)$ is a finite good rate function.

The core of the exercise is to calculate the rate function $\inf I(x)$ and the
sample path that achieves the inequality as an equality in (5.13) and (5.14).
We extend this result, which is a large deviation principle for a random
variable, to cover the sample paths of the parameters of the algorithm. We are
particularly interested in the probability of escape from a $\mu$-neighborhood
$\mathcal{N}_{\mu}$ of the stable stationary point $\bar{\alpha}=(p^{N},0)$.
For such events, the rate function can be characterized as:

$\bar{S}(\mu)=-\lim_{t\rightarrow\infty}\frac{1}{t}\log{\sf
P}\left((\alpha^{1}_{1,\tau},\alpha^{1}_{2,\tau})\not\in{\mathcal{N}}_{\mu}(\bar{\alpha},\bar{\alpha})\text{
for some $\tau\leq t$}\right)$

when the limit is well defined. Otherwise, we take
$\limsup_{t\rightarrow\infty}$.

We use a simple result to check the rate function of a special class of random
variables.

######  Lemma 5.3.

Suppose a sequence of bounded random variables $x_{t}$ with ${\sf E}x_{t}=0$
converges to 0 with probability 1. Let
${\overline{x}}_{t}=\frac{1}{t}\sum_{s=1}^{t}x_{s}$ be the sample average.
Then, the rate function of ${\overline{x}}_{t}$ is infinite:

$\limsup_{t\rightarrow\infty}\frac{1}{t}\log{\sf
P}\left({\overline{\epsilon}}_{i,t}\in F\right)=-\infty.$

###  5.2. Properties of ${\overline{\Pi}}^{0}_{i,t}$ and
${\overline{\Pi}}^{1}_{i,t}$

In this section we show that the expected profits under specification
$\mathcal{M}^{0}$ are “essentially” asymptotically equal to the Nash
equilibrium profits. To do so, we make use of the following notion of
asymptotic equivalence of random variables, following Dembo and Zeitouni
(1998).

######  Definition 5.4.

A random variable $x_{t}$ is exponentially equivalent to $0$ if :
$\forall\mu>0$,

$-\lim_{t\rightarrow\infty}\frac{1}{t}\log{\sf
P}\left(\left|x_{t}\right|>\mu\right)=\infty.$

If a random variable is exponentially equivalent to a number, we can treat the
random variable as equal to the number in the long run in any practical sense.
Abusing notation, if $x_{t}$ is exponentially equivalent to $m$, we write
$x_{t}=m$ because we deal with a large $t$.

A numerical simulation shows that under $\mathcal{M}^{0}$, prices were very
close to the Nash equilibrium level $p^{N}$. The following result, proved in
Appendix B.2 makes the intuition precise.

######  Lemma 5.5.

${\overline{\Pi}}^{0}_{i,t}$ is exponentially equivalent to $\Pi^{N}$.

By contrast, under $\mathcal{M}^{1}$, prices recurrently visit a neighborhood
of the collusive price level $p^{C}$. In Appendix B.3 we construct an
“unusual” sequence of $(\epsilon_{1,t},\epsilon_{2,t})$ where the two shocks
are almost perfectly positively correlated. While rare, such an event has a
small but positive probability, and leads firms to increase their slope
coefficient estimates $\alpha^{1}_{11,t}$ and $\alpha^{1}_{12,t}$
simultaneously at the same rate. With a sufficient increase, the beliefs then
enter a region where the expected direction of motion leads away from the
stable point. As firms start to move prices together, they increase the
estimated slope in the reaction function, which leads to a further increase in
prices. What is crucial for such a result to persist is that the threshold to
enter the “self-reinforcing” region is small enough. In Lemma B.2 in Appendix
B.3 we show that the threshold gets smaller as $\sigma^{2}$, or the size of
the experimentation gets smaller.

In general, as $\sigma^{2}\rightarrow 0$, the size of exploration decreases,
and it becomes more difficult from the small neighborhood of the stable
stationary point. In the case of specification ${\mathcal{M}}^{0}$, the lower
bound of the rate function goes to infinity as $\sigma^{2}\rightarrow 0$,
which is a crucial step in showing that ${\overline{\Pi}}^{0}_{i,t}$ is
exponentially equivalent to $\Pi^{N}$. In contrast, $\bar{S}(\mu;\sigma^{2})$,
the large deviation rate function now emphasizing its dependence on the
exploration variance, is uniformly bounded from above even if
$\sigma^{2}\rightarrow 0$.

######  Lemma 5.6.

$\limsup_{\sigma^{2}\rightarrow 0}\bar{S}(\mu;\sigma^{2})<\infty$

###  5.3. Dynamics of $\pi_{i,t}$

Recall that $\pi_{i,t}$ is the probability assessment of specification
$\mathcal{M}^{1}$ at time $t$, which evolves according to

$\pi_{i,t}=\pi_{i,t-1}+{\lambda_{t}}\left({\mathbb{I}}({\overline{\Pi}}^{1}_{i,t}>{\overline{\Pi}}^{0}_{i,t})-\pi_{i,t-1}\right).$

Since we know that ${\overline{\Pi}}^{0}_{i,t}$ is exponentially equivalent to
$\Pi^{N}$, we can write the recursive form as

$\pi_{i,t}=\pi_{i,t-1}+{\lambda_{t}}\left({\mathbb{I}}({\overline{\Pi}}^{1}_{i,t}>\Pi^{N})-\pi_{i,t-1}\right),$

whose associated ODE is

${\dot{\pi}}_{i}={\sf
P}\left({\overline{\Pi}}^{1}_{i,t}>\Pi^{N}\right)-\pi_{i}.$

Our key result, proved in Appendix B.4, shows that in the limit each duopolist
will put probability one on specification $\mathcal{M}^{1}$. This result is a
consequence of our previous analysis, that profits are higher under the
specification with feedback than the constant specification.

######  Proposition 5.7.

For any $\sigma^{2}_{t}\rightarrow 0$,

$\lim_{t\rightarrow\infty}{\sf
P}\left({\overline{\Pi}}^{1}_{i,t}>\Pi^{N}\right)=1.$

Thus each duopolist, who chooses prices and experiments independently, and
independently chooses a model specification, will in the long run choose the
specification $\mathcal{M}^{1}$. Under this specification, the two firms will
recurrently and in almost perfect unison, increase prices to near the
cartelized, joint monopoly level, as first observed in Williams (2001). We
have shut down all avenues for explicit or implicit collusion, and yet the
pricing algorithms recurrently lead to prices near collusive levels. Thus the
observation of parallel price increases to supra-competitive levels cannot on
its own be used as evidence of collusion. In the remainder of the paper we
further explore the key features of the model and its structure which underlie
these results.

##  6\. Analysis of Fixed Specifications

While a key aspect of our model is the endogenous specification choice, it is
instructive to analyze cases with fixed, symmetric specifications. The
comparison of environments with $({\mathcal{M}}^{0},{\mathcal{M}}^{0})$ and
$({\mathcal{M}}^{1},{\mathcal{M}}^{1})$ shows the fundamental difference in
the stochastic properties of the two different pairs of specifications. For
simplicity, we refer here to $\mathcal{M}^{i}$ as the symmetric pair
$(\mathcal{M}^{i},\mathcal{M}^{i})$. In addition to being simpler, studying a
fixed specification allows us to draw on existing results from the learning
literature, including Cho, Williams, and Sargent (2002) and Williams (2019).

The contrast in the large deviation properties of the two cases highlights
features that conventional analysis of the stability of the learning dynamics
cannot capture. While both specifications converge to the Nash outcomes, the
convergence in specification $\mathcal{M}^{1}$ is less robust, in a sense we
make clear. Applying the large deviation results allows us to characterize the
collusive outcomes which arise without collusion.

###  6.1. Analysis of $\mathcal{M}^{0}$

As described in Section 3.1, under ${\mathcal{M}}^{0}$, firm $i$ treats the
opponent’s action as an unobserved parameter and estimates the parameter by
averaging the past actions. Let $\alpha^{0}_{i,t}$ be the estimate of
duopolist $i$ about duopolist $j$’s action based on $t$ periods. Given
$\alpha^{0}_{i,t-1}$, firm $i$ chooses its best response $b^{0}_{i,t}$ in
period $t$, with the actual price incorporating the exploration shock. Given
$(p_{1,t},p_{2,t})$, duopolist $i$ receives profit $\Pi^{00}_{i,t}$ in period
$t$, and updates its estimate of duopolist $j$’s price according to the
recursive algorithm (3.8).

As discussed in Appendix C.1, as $\lambda_{t}\rightarrow 0$, we can
approximate the dynamics from (3.8) by the solution of the ordinary
differential equation:

${\dot{\alpha}}^{0}_{i}(t)=b(\alpha^{0}_{j}(t))-\alpha^{0}_{i}(t)$

The stable point of this ODE system for $i,j=1,2$ is the limit point of
beliefs. Thus we can show that (3.8) converges to the Nash equilibrium price,
which is a unique stable stationary point of the differential equation:

$\lim_{t\rightarrow\infty}\alpha^{0}_{i,t}=p^{N}$

with probability 1, where

$p^{N}=\frac{A}{2B-C}.$

Thus as $t\rightarrow\infty$ the beliefs $\alpha^{0}_{i,t}$ will converge to
the stable point where expected prices $b_{i,t}$ are equal to the Nash
equilibrium price $p^{N}$ and observed prices $p_{i,t}$ are i.i.d.
fluctuations around this constant price level. This is consistent with what we
observed in Figure 3.

We need to go beyond the convergence and stability results, using large
deviation theory. More detail on the background and calculations is provided
in Appendix E.1. We saw above in Lemma 5.5 that profits in $\mathcal{M}^{0}$
are asymptotically equivalent to the Nash profits. Here we provide more detail
and illustration of this result.

In earlier work Cho, Williams, and Sargent (2002) and Williams (2019), we
adapted results from large deviation theory due to Kushner and Yin (2003) to
characterize this probability. In particular, under mild regularity conditions
on $\epsilon_{i,t}$, there exists a real-valued function rate function $S$ for
sample paths that satisfies

$-\inf_{x\in X}S(x)=\lim_{t\rightarrow\infty}\frac{1}{t}\log{\sf
P}\left((\alpha^{0}_{1,\tau},\alpha^{0}_{2,\tau})\in X\text{ for some
$\tau\leq t$}\mid\ (\alpha^{0}_{1,0},\alpha^{0}_{2,0})=(p^{N},p^{N})\right)$

We are particularly interested in exit from sets of radius $r$, so we define

${\bar{S}}(r)=\inf_{\\{x\mathrel{\mathop{\mathchar
58\relax}}\|x-(p^{N},p^{N})\|=r\\}}S(x).$

If $\epsilon_{i,t}$ is a Gaussian random variable with mean 0 and variance
$\sigma^{2}$, we can compute $\bar{S}(r)$ explicitly.131313The calculations
here are analogous to Freidlin and Wentzell (1998). First, we suppose that the
beliefs follow mean dynamics but are subject to a perturbation:

$\dot{\alpha}^{0}_{i}(t)=b(\alpha^{0}_{j}(t))-\alpha^{0}_{i}(t)+v_{i}(t).$
(6.15)

Then we stack the estimates into a vector
$\alpha^{0}=(\alpha^{0}_{1},\alpha^{0}_{2})$ and define an instantaneous cost
function $L$ that weights the perturbations $v$ by the shock variance:

$L(\alpha^{0},v)=\frac{1}{2\sigma^{2}}v^{\prime}v.$

Here the cost function $L$ is independent of $\alpha^{0}$, but we keep the
more general notation for later reference. Then we solve the control problem:

$\bar{S}(r)=\inf_{v(\cdot),T}\int_{0}^{T}L(\alpha^{0}(s),v(s))ds$

where the minimization is subject to the dynamics (6.15) and:

$\alpha^{0}(0)=(p^{N},p^{N}),\ \ \text{ and
}\|\alpha^{0}(T)-(p^{N},p^{N})\|=r.$

If $v\equiv 0$ then the beliefs follow the mean dynamics. The cost is zero,
but the beliefs do not escape. To find the most probable escape path, we find
a least cost path of perturbations that pushes beliefs a distance $r$ from the
Nash equilibrium.

As we discuss in Appendix E.1, the solution of this cost minimization problem
characterizes the most likely escape path from the stable stationary point.
The probability of observing an escape on a bounded time interval is
exponentially decreasing, at a rate given by the minimized cost. The
minimizing path from the cost function also determines the most likely escape
path. With probability approaching one, escapes occur at the point determined
from the solution of the cost minimization problem.

In Appendix E.2 we show how to calculate the large deviation rate function
$S(x)$ explicitly. In particular, $S(x)$ is a quadratic function of $x$, with
$S(p^{N},p^{N})=0$. The level sets of the cost function are ellipses, with the
major axis on the 45 degree line. Thus we expect that large deviations from
the equilibrium point are nearly symmetric, and are equally likely to result
from correlated increases or decreases in prices.

Moreover, we can write:

${\bar{S}}(r)=\frac{S_{0}\ r^{2}}{\sigma^{2}},$

for a constant $S_{0}>0$. Note that as $r$ increases, the neighborhood of the
stable stationary point becomes larger, which makes it more difficult for
$(\alpha^{0}_{1,t},\alpha^{0}_{2,t})$ to escape. If $\sigma^{2}$ decreases,
the “scope” of exploring the prices around $b^{0}_{i,t}$ decreases, and it
takes more explorations to escape from the neighborhood, as depicted in Figure
5. The comparative static properties of the large deviation rate function are
central to our analysis.

Figure 5. Solution of the cost minimization problem determining the rate
function $\bar{S}(r)$ for different radius $r$ and different shock volatility
$\sigma^{2}$ for the specification $\mathcal{M}^{0}$.

Overall, our results for $\mathcal{M}^{0}$ support what we observed in the
simulations. Convergence to the equilibrium beliefs and Nash price is strong,
and deviations are quite rare. When they occur, the most likely large
deviations are associated with coordinated price movements. But decreases in
prices are as likely to be realized as price increases, and the likelihood of
significant changes in prices is very small. Furthermore, the rate function
varies inversely with the variance $\sigma^{2}$, so for smaller shocks the
likelihood of escaping the equilibrium diminishes rapidly. Many of these
properties differ sharply when we allow feedback in the next section.

###  6.2. Specification $\mathcal{M}^{1}$

Now we suppose that each firm chooses specification ${\mathcal{M}}^{1}$. As
described above, duopolist $i$ predicts duopolist $j$ reacts to duopolist
$i$’s price as a linear function (2.4). Let
$\alpha^{1}_{i,t}=(\alpha^{1}_{0i,t},\alpha^{1}_{1i,t})$ be the estimate of
firm $i$, who then chooses best response $b^{1}_{i,t}=b(\alpha^{1}_{i,t})$.
After observing $(p_{1,t},p_{2,t})$, each firm updates according to (3.9).

We again apply standard results in stochastic approximation to characterize
the limit. Details of the calculations are in Appendix D. In particular, the
mean dynamics ODEs now take the form:

$\displaystyle\dot{\alpha}^{1}_{i}(t)$ $\displaystyle=$ $\displaystyle
R_{i}(t)^{-1}g_{i}(\alpha^{1}_{i}(t))$ $\displaystyle\dot{R}_{i}(t)$
$\displaystyle=$ $\displaystyle M(\alpha^{1}_{i}(t)-R_{i}(t).$

Full expressions are given there, and in particular:

$g_{i}(\alpha^{1}_{i})=\left[\begin{matrix}b(\alpha^{1}_{j})-\alpha^{1}_{0,i}-\alpha^{1}_{1,i}b(\alpha^{1}_{i})\\\
\left(b(\alpha^{1}_{j})-\alpha^{1}_{0,i}-\alpha^{1}_{1,i}b(\alpha^{1}_{i})\right)b(\alpha^{1}_{i})-\alpha^{1}_{1,i}\sigma^{2}\end{matrix}\right].$

The stationary point of the ODE satisfies $g_{i}(\alpha^{1}_{i})=0$, which
thus requires $b(\alpha^{1}_{j})=\alpha^{1}_{0,i}$ and $\alpha_{1i}=0$.
Therefore we have, for $i=1,2$,:

$\lim_{t\rightarrow\infty}(\alpha^{1}_{0i,t},\alpha^{1}_{1i,t})=(p^{N},0)$

with probability 1, which is the Nash equilibrium outcome. Thus, each
duopolist’s profit converges to $\Pi^{N}$.

While the equilibrium $(p^{N},0)$ is stable, the mean dynamics which draw
belief toward the equilibrium are “weak” along some directions. For example,
two of the eigenvalues of the Jacobian matrix of the mean dynamics are very
small, and vanish as $\sigma^{2}\rightarrow 0$. This is a manifestation of the
multiplicity of self-confirming equilibria that we saw above. Absent the price
shocks, the equilibrium conditions $g_{i}(\alpha^{1}_{i})=0$ do not uniquely
identify the slope and intercept coefficients in the reaction function.
Instead, any point $\alpha=(\alpha_{0},\alpha_{1})$ on the surface

$\alpha_{0}=b(\alpha)-\alpha_{1}b(\alpha)$

will be an equilibrium. With price shocks and hence $\sigma^{2}>0$, only
$(p^{N},0)$ satisfies the equilibrium conditions, but the other points along
the surface come close to doing so, in that divergence of the mean dynamics
from zero is of order $\sigma^{2}$.

We saw above that the episodes of price increases were symmetric, but there
were asymmetries in the episodes when prices are cut from near the joint
monopoly price $p^{C}$ to the Nash equilibrium price $p^{N}$. As discussed
above, the price increases occur after an unusual sequence of correlated
shocks. However, the price decreases are expected, and result from the mean
dynamics leading back to the stable point. We illustrate the mean dynamics
driving the price cutting episodes in Appendix D. Small differences in the
realizations of shocks after the escapes determine which firm initiates the
price cutting episode.

While both symmetric ${\mathcal{M}}^{0}$ and $\mathcal{M}^{1}$ specifications
converge to the Nash equilibrium, the large deviation properties of the
estimators are dramatically different. As above, the rate function can be
found by solving a cost minimization problem. The beliefs are initialized at
the limit point $\alpha^{1}_{i}=(p^{N},0)$ and they follow perturbed mean
dynamics until they move a distance $r$. In Appendix E.3, we show how to
calculate the rate function when $\epsilon_{i,t}$ are Gaussian random
variables with variance $\sigma^{2}$.

Figure 6. Solution of the cost minimization problem determining the rate
function $\bar{S}(r)$ for different radius $r$ and different shock volatility
$\sigma^{2}$ for the specification $\mathcal{M}^{1}$.

The rate function $\bar{S}(r)$ for $\mathcal{M}^{1}$ is shown in Figure 6. We
saw above that as $\sigma^{2}\rightarrow 0$, the probability of escaping from
a small neighborhood of the stable stationary point under ${\mathcal{M}}^{0}$
decreases. In contrast, the escape probability under ${\mathcal{M}}^{1}$
increases as $\sigma^{2}\rightarrow 0$. As $\sigma^{2}$ converges to 0, so
does $\bar{S}$. For a small $\sigma^{2}$, it becomes very easy for
$(\alpha^{1}_{1t},\alpha^{1}_{2,t})$ to escape from a “small” neighborhood of
the Nash equilibrium outcome. This is a reflection of the weakness mean
dynamics that we noted above. In order to escape from the equilibrium point,
the perturbations must fight against the mean dynamics which would pull
beliefs back to the equilibrium point. As the variance of the price shocks
shrinks, the mean dynamics become weaker and the radius of local stability
shrinks as well.

Note that ${\bar{S}}(r)$ is a weakly increasing function of $r$ but has a flat
portion, implying that the size of the neighborhood where
$(\alpha^{1}_{1t},\alpha^{1}_{2,t})$ can escape easily is in fact “large.”
This explains the large fluctuations of the prices charged by each duopolist,
which we’ve seen in Figures 1 and 2 above. The shape of the rate function
${\bar{S}}(r)$ means that once the beliefs escape a small distance from the
equilibrium point, they are very likely to continue to escape until the
inflection point where ${\bar{S}}$ starts to increase again.

###  6.3. Relation Between Mean Dynamics and Large Deviations

The significant escape dynamics and flat portion of the rate function are
driven by features of the mean dynamics in the $\mathcal{M}^{1}$
specification. Above we saw that the that there is a unique stable equilibrium
which we can denote $\bar{\alpha}=[p^{N},0]$, which is a stationary point of
the mean dynamics $g(\bar{\alpha})=0$ and all of the eigenvalues of the
Jacobian matrix have negative real part. Thus at least locally around
$\bar{\alpha}$ the mean dynamics point back toward $\bar{\alpha}$.

However, outside a neighborhood of $\bar{\alpha}$ the mean dynamics point away
from it. We established this analytically in the proof of Lemma 5.6
analytically, and we illustrate it numerically in the Appendix E.3. This means
that once the beliefs escape a neighborhood around the equilibrium, we would
expect further movement away from the equilibrium. The perturbations $v$ in
the large deviation cost minimization problem are only necessary to push
against the mean dynamics. If the mean dynamics point away from the
equilibrium, further escapes happen “for free” with $v=0$.

We show in Appendix E.4 that these properties of the mean dynamics help
explain the properties of the rate function $\bar{S}(r)$ and hence the escape
dynamics. $\bar{S}(r)$ is increasing for very small $r$ inside the stability
radius, has a long flat portion where the mean dynamics lead the beliefs away
from the stable equilibrium, and then starts increasing again when the mean
dynamics point back toward the equilibrium. For less volatile shocks with
smaller $\sigma^{2}$, the radius of stability is smaller, so it is much easier
to escape the equilibrium (the cost $S$ is much lower) and the inflection
point is closer to the beliefs that support the collusive price.

As we discussed in Section 4.4, the collusive outcomes arise in the absence of
any opportunity for collusion. The collusive episodes are caused by correlated
realizations of independent shock processes, which are unlikely events with
limit probability zero. Nonetheless, away from the limit, these collusive
outcomes are a recurrent feature of the model.

##  7\. Conclusion

We have developed a model of algorithmic pricing which shuts down every
channel for explicit or implicit collusion, and yet still generates collusive
outcomes. Our model uses common, widely-used ingredients – model averaging and
least squares estimation – in a simple, textbook setting – linear Bertrand
duopoly with myopic profit maximization. In this environment, the algorithmic
learning dynamics are stable, and we have asymptotic convergence to a
competitive outcome. But even in such a common, stable, and well-behaved
environment, recurrent collusive outcomes arise.

We show that the market experiences recurrent episodes where both firms set
prices at collusive levels, followed by a period of price-cutting and
reversion to competitive prices. We analytically characterize the dynamics of
the model, using large deviation theory to explain the recurrent episodes of
collusive outcomes. Our results suggest that collusive outcomes may be a
recurrent feature of environments with complementarities, arising endogenously
from interactions and adaptation, while not relying on explicit communication,
tacit collusion, or punishment strategies supporting collusive outcomes. Our
results thus provide a challenge for lawmakers and regulators seeking policy
reforms to enhance competition in markets with algorithmic pricing. Even if
outcomes appear highly collusive, an outsider cannot conclude that a firm
learns to collude via an algorithm.

## References

  * Abreu et al. (1986) Abreu, D., D. Pearce, and E. Stachetti (1986).  Optimal Cartel Equilibria with Imperfect Monitoring.  Journal of Economic Theory 39, 251–269.
  * Asker et al. (2023) Asker, J., C. Fershtman, and A. Pakes (2023).  The Impact of Artificial Intellgence Design on Pricing.  Journal of Economics and Management Strategy.  forthcoming.
  * Banchio and Mantegazza (2023) Banchio, M. and G. Mantegazza (2023).  Aritficial Intelligence and Spontaneous Collusion.  Stanford University.
  * Banchio and Skrzypacz (2022) Banchio, M. and A. Skrzypacz (2022).  Artifical Intelligence and Auction Design.  arXiv: 2202.05947v1.
  * Benaim (1996) Benaim, M. (1996).  A Dynamical System Approach to Stochastic Approximations.  SIAM Journal of Control and Optimization 34, 437–472.
  * Brown and MacKay (2023) Brown, Z. Y. and A. MacKay (2023).  Competition in Pricing Algorithms.  American Economic Journal: Microeconomics 15, 109–156.
  * Calvano et al. (2020) Calvano, E., G. Calzolari, V. Denicolò, and S. Pastorello (2020, October).  Artificial intelligence, algorithmic pricing, and collusion.  American Economic Review 110(10), 3267–97.
  * Calzolari (2021) Calzolari, L. (2021).  The Misleading Consequences of Comparing Algorithmic and Tacit Collusion: Tackling Algorithmic Concerted Practices Under Art. 101 TFEU.  European Papers 6(2), 1193–1228.
  * Cho and Kasa (2017) Cho, I.-K. and K. Kasa (2017).  Gresham’s Law of Model Averaging.  American Economic Review 107(11), 1–29.
  * Cho and Matsui (2005) Cho, I.-K. and A. Matsui (2005).  Learning Aspiration in Repeated Games.  Journal of Economic Theory 124(2), 171–201.
  * Cho et al. (2002) Cho, I.-K., N. Williams, and T. J. Sargent (2002).  Escaping Nash Inflation.  Review of Economic Studies 69, 1–40.
  * Dembo and Zeitouni (1998) Dembo, A. and O. Zeitouni (1998).  Large Deviations Techniques and Applications (2nd ed.).  New York: Springer-Verlag.
  * Deng (2024) Deng, A. (2024).  What Do We Know About Algorithmic Collusion Now? New Insights from the Latest Academic Research.  Charles River Associates.
  * Dupuis and Kushner (1989) Dupuis, P. and H. J. Kushner (1989).  Stochastic Approximation and Large Deviations: Upper Bounds and w.p.1 Convergence.  SIAM Journal of Control and Optimization 27, 1108–1135.
  * Evans and Honkapohja (2001) Evans, G. W. and S. Honkapohja (2001).  Learning and Expectations in Macroeconomics.  Princeton University Press.
  * Ezrachi and Stucke (2020) Ezrachi, A. and M. E. Stucke (2020).  Sustainable and Unchallenged Algorithmic Tacit Collusion.  Northwestern Journal of Technology and Intellectual Property 17, 217–260.
  * Freidlin and Wentzell (1998) Freidlin, M. I. and A. D. Wentzell (1998).  Random Perturbations of Dynamical Systems (2nd ed.).  Springer-Verlag.
  * Fudenberg and Levine (1998) Fudenberg, D. and D. Levine (1998).  Learning in Games.  M.I.T. Press.
  * Green and Porter (1984) Green, E. and R. Porter (1984).  Noncooperative Collusion Under Imperfect Price Information.  Econometrica 52, 87–100.
  * Hansen et al. (2021) Hansen, K. T., K. Isra, and M. M. Pai (2021).  Algorithmic Collusion: Supra-Competitive Prices via Independent Algorithms.  UCSD and Rice.
  * Harrington (2019) Harrington, J. E. (2019).  Developing Competition Law for Collusion by Autonomous Artificial Agents.  Journal of Competition Law & Economics 14, 331–363.
  * Klobuchar (2024) Klobuchar, A. (2024).  Klobuchar, Colleagues Introduce Antitrust Legislation to Prevent Algorithmic Price Fixing.  press release.
  * Kushner and Yin (2003) Kushner, H. J. and G. G. Yin (2003).  Stochastic Approximation Algorithms and Applications (2nd ed.).  Springer-Verlag.
  * Lamba and Zhuk (2023) Lamba, R. and S. Zhuk (2023).  Pricing with Algorithms.  Pennsylvania State University.
  * Leisten (2024) Leisten, M. (2024).  Algorithmic Competition, with Humans.  Federal Trade Commission.
  * MacKay and Weinstein (2022) MacKay, A. and S. N. Weinstein (2022).  Dynamic Pricing Algorithms, Consumer Harm, and Regulatory Response.  Washington University Law Review 100(1), 111–174.
  * Marcet and Sargent (1989) Marcet, A. and T. J. Sargent (1989).  Convergence of Least Squares Learning Mechanisms in Self Referential Linear Stochastic Models.  Journal of Economic Theory 48, 337–368.
  * Meyn (2007) Meyn, S. P. (2007).  Control Techniques for Complex Networks.  Cambridge University Press.
  * OECD (2017) OECD (2017).  Algorithms and Collusion: Competition Policy in the Digital Age.  https://www.oecd.org/competition/algorithms-and-collusion.htm.
  * Possnig (2023) Possnig, C. (2023).  Reinforcement Learning and Collusion.  University of Waterloo.
  * Salcedo (2015) Salcedo, B. (2015).  Pricing Algorithms and Tacit Collusion.  University of Western Ontario.
  * Sargent (1999) Sargent, T. J. (1999).  The Conquest of American Inflation.  Princeton University Press.
  * Steel (2020) Steel, M. F. J. (2020).  Model Averaging and Its Use in Economics.  Journal of Economic Literature 58(3), 644–719.
  * Stucke (2023) Stucke, M. E. (2023).  What Can Policymakers Do About Algorithmic Collusion and Discrimination?  ProMarket, University of Chicago.
  * United States, Congress, Senate (2024) United States, Congress, Senate (2024).  S.3686 - Preventing Algorithmic Collusion Act of 2024.  https://www.congress.gov/bill/118th-congress/senate-bill/3686/text.
  * Waltman and Kaymak (2008) Waltman, L. and U. Kaymak (2008).  Q-Learning Agents in a Cournot Oligopoly Model.  Journal of Economic Dynamics and Control 32, 3275–3298.
  * Williams (2001) Williams, N. (2001).  Escape Dynamics in Learning Models.  Ph. D. thesis, University of Chicago.
  * Williams (2019) Williams, N. (2019).  Escape Dynamics in Learning Models.  Review of Economic Studies 86, 882–912.

##  Appendix A Construction of Self-Confirming Equilibria

As an example, consider a $({\mathcal{M}}^{1},{\mathcal{M}}^{1})$ pair of
specifications as in (2.4). The equilibrium conditions are then:

$\displaystyle p_{2}$ $\displaystyle=$
$\displaystyle\alpha_{0,1}+\alpha_{1,1}p_{1}$ (A.16) $\displaystyle p_{1}$
$\displaystyle=$ $\displaystyle\alpha_{0,2}+\alpha_{1,2}p_{2}$ (A.17)
$\displaystyle p_{1}$ $\displaystyle=$
$\displaystyle\frac{A+C\alpha_{0,1}}{2(B-C\alpha_{1,1})}$ (A.18)
$\displaystyle p_{2}$ $\displaystyle=$
$\displaystyle\frac{A+C\alpha_{0,2}}{2(B-C\alpha_{1,2})}$ (A.19)

Here (A.16) and (A.17) imply the perfect foresight conditions for firms 1 and
2, respectively. (A.18) and (A.19) imply that the price of firms 1 and 2 must
be best responses. We now construct two reference self-confirming equilibria.
First, suppose that $\alpha_{1,1}=\alpha_{1,2}=0$. Then the equilibrium
conditions reduce to:

$\displaystyle p_{2}$ $\displaystyle=$ $\displaystyle\alpha_{0,1},\ \
p_{1}=\alpha_{0,2}$ $\displaystyle p_{1}$ $\displaystyle=$
$\displaystyle\frac{A+C\alpha_{0,1}}{2B},\ \
p_{2}=\frac{A+C\alpha_{0,2}}{2B}.$

Which imply that the self-confirming equilibrium price is precisely the Nash
equilibrium price

$p_{1}=p_{2}=p^{N}=\frac{A}{2B-C}.$

Alternatively suppose that

$\alpha_{0,1}=\alpha_{0,2}=0\ \text{and}\ \alpha_{1,1}=\alpha_{1,2}=1.$

Then from (A.18) and (A.19) we get

$p_{1}=p_{2}=p^{C}$

and

$\Pi_{1}=\Pi_{2}=\Pi^{C}.$

Following the same logic, we can construct multiple self-confirming equilibria
for $({\mathcal{M}}^{0},{\mathcal{M}}^{1})$ and
$({\mathcal{M}}^{1},{\mathcal{M}}^{0})$.

##  Appendix B Proofs and Background for the Results in Section 5

###  B.1. Preliminaries

It is necessary to define the basic notation for the analysis. We describe the
notational convention of
$\alpha^{1}_{i,t}=(\alpha^{1}_{0i,t},\alpha^{1}_{1i,t})$ as an example, which
will be used for other endogenous variables such as $\alpha^{0}_{i,t}$.

Given a discrete time stochastic process
$\\{\alpha^{1}_{i,t}\\}_{t=1}^{\infty}$, we construct a continuous time
process by linearly interpolating the samples in $t$ and $t-1$ periods. Define
$\alpha^{1}_{i}(\tau)$ as the continuous time process obtained by linear
interpolation. Since $\sum_{t=1}^{T}\lambda_{t}\rightarrow\infty$ as
$T\rightarrow\infty$, $\forall K\in\\{1,2,\ldots\\}$, there is a unique
$t_{K}$ that is the smallest $T$ where $\sum_{t=1}^{T}\lambda_{t}\geq K$. For
a real number $\tau>0$, define $m(K+\tau)$ as the smallest number $T$
satisfying $\sum_{t=t_{K}}^{T}\lambda_{t}\geq\tau$. Given a continuous time
process $\alpha^{1}_{i}(\tau)$, define the left shifted continuous time
process as

$\alpha^{1,K}_{i}(\tau)=\alpha^{1}_{i}(K+\tau)$

which is essentially a right tail of the sample path of $\alpha^{1}_{i}(\tau)$
starting from time $K$. We will use the same convention for the other
variables by adding superscript K and the real number $\tau>0$ to represent
the left shift continuous time process.

####  B.1.1. Exploration Probability

$\pi_{i,t}$ is the probability that duopolist $i$ assigns to specification
$\mathcal{M}^{1}$. We assume that the duopolist is not committed to any
particular specification.

######  Assumption B.1.

$\exists{\overline{\pi}},{\underline{\pi}}\in(0,1)$ such that

$0<{\underline{\pi}}\leq\pi_{i,t}\leq{\overline{\pi}}<1.$

The following is the proof of Lemma 5.3.

###### Proof.

It suffices to show that the $H$ functional of the sample average

$H({\overline{x}},\tau)=\lim_{\tau\rightarrow
0}\lim_{K\rightarrow\infty}\frac{1}{m(K+\tau)-t_{K}}\log{\sf
E}\left[e^{\alpha\sum_{t=t_{K}}^{m(K+\tau)}\xi_{t}}\ \mid\
{\overline{x}}_{t_{K}}=x\right]$

is 0. We can write

${\overline{x}}_{t}={\overline{x}}_{t-1}+\frac{1}{t}\left(x_{t}-{\overline{x}}_{t-1}\right).$

Define $\xi_{t}=x_{t}-{\overline{x}}_{t-1}$ which is a bounded martingale
difference. Since $x_{t}\rightarrow 0$ with probability 1, $\forall\nu>0$,
exists $T(\nu)$ such that $\forall t\geq T(\nu)$,
$\mathinner{\\!\left\lvert\xi_{t}\right\rvert}\leq\nu$ with probability
$1-\nu$. Note that $\forall\alpha$, $\forall t_{K}\geq T(\nu)$,

$e^{-\nu(m(K+\tau)-t_{K})}(1-\nu)+e^{-M(m(K+\tau)-t_{K})}\nu\leq{\sf
E}e^{\alpha\sum_{t=t_{K}}^{m(K+\tau)}\xi_{t}}\leq
e^{\nu(m(K+\tau)-t_{K})}(1-\nu)+e^{M(m(K+\tau)-t_{K})}\nu$

where $M=\sup_{t\geq 1}\mathinner{\\!\left\lvert x_{t}\right\rvert}<\infty$
since $x_{t}$ is bounded. We can choose $M^{\prime}$ such that for any
sufficiently small $\nu$,

$e^{\nu(m(K+\tau)-t_{K})}(1-\nu)+e^{M(m(K+\tau)-t_{K})}\nu<e^{M^{\prime}\nu(m(K+\tau)-t_{K})}$

and therefore,

$-M^{\prime}\nu\leq\frac{1}{m(K+\tau)-t_{K}}\log{\sf
E}e^{\alpha\sum_{t=t_{K}}^{m(K+\tau)}\xi_{t}}\leq M^{\prime}\nu.$

Since $\nu$ is arbitrary, $H({\overline{x}},\tau)=0$ $\forall\tau>0$. ∎

Consider the left shift process $\alpha^{1,K}_{i}(\tau)$ initialized at
$\alpha^{1,K}_{i}(0)=(p^{N},0)$ which is a stable stationary point of the
recursive algorithm of $\alpha^{1}_{i,t}$. Consider an open ball around the
stable stationary point $(p^{N},0)$ with radius $\mu$,
${\mathcal{N}}_{\mu}(p^{N},0)$. We are interested in the probability that
$\alpha^{1,K}_{i}(\tau)$ escape from ${\mathcal{N}}_{\mu}(p^{N},0)$, which is
a rare event. Dupuis and Kushner (1989) proved that there exists a non-
negative measurable function $S(x,\tau,\phi)$ such that for any closed subset
$F$ and open subset $G$ of ${\mathcal{N}}_{\mu}(p^{N},0)$ such that

$\displaystyle\limsup_{K\rightarrow\infty}a_{t_{K}}\log{\sf
P}\left(\exists\tau>0,\
\alpha^{1,K}_{i}(\tau)\not\in{\mathcal{N}}_{\mu}(p^{N},0)\ \mid\
\alpha^{1,K}_{i}(0)=(p^{N},0)\right)$ $\displaystyle\leq$
$\displaystyle-\inf_{\begin{subarray}{c}\phi(0)=(p^{N},0),\\\
\exists\tau^{\prime},\phi(\tau^{\prime})\not\in{\mathcal{N}}_{\mu}(p^{N},0)\end{subarray}}S(\alpha^{1,K}_{i}(0),\tau,\phi)\equiv
S^{*}(\alpha^{1,K}_{i}(0),{\mathcal{N}}_{\mu}(p^{N}j,0)).$

We call $S^{*}(\cdot)$ the rate function.

###  B.2. Properties of ${\overline{\Pi}}^{0}_{i,t}$

We know that $\alpha^{0}_{i,t}$ and
$\alpha^{1}_{i,t}=(\alpha^{1}_{0i,t},\alpha^{1}_{1i,t})$ satisfy the large
deviation properties (Dupuis and Kushner (1989)). Let
$S^{\alpha,0}_{i}({\mathcal{N}}_{\mu}(0),\sigma^{2})$ and
$S^{\alpha,1}_{i}({\mathcal{N}}_{\mu}(0,0),\sigma^{2})$ be the rate function
around $\mu$ neighborhood of the stable stationary point of $\alpha^{0}_{i,t}$
and $\alpha^{1}_{i,t}$ in case $\sigma^{2}_{i,t}=\sigma^{2}$ $\forall t\geq
1$, respectively. Recall that $b^{0}_{i,t}$ and $b^{1}_{i,t}$ are the
continuous transformation of $\alpha^{0}_{i,t}$ and $\alpha^{1}_{i,t}$. By the
contraction principle of the large deviation, the large deviation rate
functions of $b^{0}_{i,t}$ and $b^{1}_{i,t}$ are the continuous transformation
of the large deviation rate functions of $\alpha^{0}_{i,t}$ and
$\alpha^{1}_{i,t}$. That is, there exist continuous functions $g^{0}$ and
$g^{1}$ such that $\forall\mu>0$,

$\displaystyle-\lim_{t\rightarrow\infty}\frac{1}{t}\log{\sf E}{\sf
P}\left(\left|b^{0}_{i,t}-p^{N}\right|>\mu\right)\leq
g^{0}(S^{\alpha,0}_{i}({\mathcal{N}}_{\mu}(0),\sigma^{2}))$
$\displaystyle-\lim_{t\rightarrow\infty}\frac{1}{t}\log{\sf E}{\sf
P}\left(\left|b^{1}_{i,t}-p^{N}\right|>\mu\right)\leq
g^{1}(S^{\alpha,1}_{i}({\mathcal{N}}_{\mu}(0,0),\sigma^{2}))$

which imply

$\lim_{t\rightarrow\infty}b^{0}_{i,t}=p^{N}\ \ \text{and}\ \
\lim_{t\rightarrow\infty}b^{1}_{i,t}=p^{N}\qquad\forall i\in\\{1,2\\}$ (B.20)

with probability 1. Recall that

$p_{j,t}=(1-\pi_{j,t})b^{0}_{j,t}+\pi_{j,t}b^{1}_{j,t}+\epsilon_{j,t}$

with $\pi_{j,t}\geq{\underline{\pi}}>0$ and

$\displaystyle\alpha^{0}_{i,t}$ $\displaystyle=$
$\displaystyle{\overline{p}}_{j,t}=\frac{1}{t}\sum_{k=0}^{t-1}p_{j,k}$ (B.21)
$\displaystyle=$
$\displaystyle\sum_{k=0}^{t-1}(1-\pi_{j,k})b^{0}_{j,k}+\pi_{j,k}b^{1}_{j,k}+\frac{1}{t}\sum_{k=0}^{t-1}\epsilon_{j,k}.$
(B.22)

Thanks to (B.20),

$\lim_{t\rightarrow\infty}(1-\pi_{j,t})b^{0}_{j,t}+\pi_{j,t}b^{1}_{j,t}=p^{N}$

with probability 1. Therefore, $\forall\mu>0$,

$\lim_{t\rightarrow\infty}\frac{1}{t}\log{\sf
P}\left(\left|\frac{1}{t}\sum_{k=0}^{t-1}(1-\pi_{j,k})b^{0}_{j,k}+\pi_{j,k}b^{1}_{j,k}-p^{N}\right|>\mu\right)=-\infty.$

Since

$\frac{1}{t}\sum_{k=0}^{t-1}(1-\pi_{j,k})b^{0}_{j,k}+\pi_{j,k}b^{1}_{j,k}$

is exponentially equivalent to $p^{N}$ (Dembo and Zeitouni (1998)), we can
treat

$\alpha^{0}_{i,t}={\overline{p}}_{j,t}=p^{N}+\frac{1}{t}\sum_{k=0}^{t-1}\epsilon_{j,k}\qquad
i\neq j\in\\{1,2\\}.$

Hence,

$b^{0}_{i,t}=p^{N}+\frac{C}{2B}\frac{1}{t}\sum_{k=0}^{t-1}\epsilon_{j,k}.$

Since $\epsilon_{j,t}$ satisfies the large deviation property, $\forall\mu>0$,
$\exists S^{\epsilon}_{i}(\mu)$ such that

$-\lim_{t\rightarrow\infty}\frac{1}{t}\log{\sf
P}\left(\left|b^{0}_{i,t}-p^{N}\right|>\mu\right)\leq S^{\epsilon}_{i}(\mu).$

Thus,

$\Pi^{0}_{i,t}=\max_{p}p(A-Bp+C\alpha^{0}_{i,t})=\Pi^{N}+D{\overline{\epsilon}}_{i,t}+D^{\prime}({\overline{\epsilon}}_{i,t})^{2}$

for some constant $D,D^{\prime}$. Thus, if ${\lambda_{t}}=\frac{1}{t}$,

$\lim_{t\rightarrow\infty}\Pi^{0}_{i,t}=\Pi^{N}$

with probability 1.

With those preceding calculations, the following is the proof of Lemma 5.5 in
the text.

###### Proof.

Since

${\overline{\Pi}}^{0}_{i,t}={\overline{\Pi}}^{0}_{i,t-1}+{\lambda_{t}}\left(\Pi^{0}_{i,t}-{\overline{\Pi}}^{0}_{i,t-1}\right),$

${\overline{\Pi}}^{0}_{i,t}$ is the average of $\Pi^{0}_{i,t}$ which converges
to $\Pi^{N}$ with probability 1. Thus, ${\overline{\Pi}}^{0}_{i,t}$ is
exponentially equivalent to $\Pi^{N}$. ∎

###  B.3. Properties of ${\overline{\Pi}}^{1}_{i,t}$

To examine the sample path properties of $\Pi^{1}_{i,t}$, we need to examine
the properties of $\alpha^{1}_{i,t}=(\alpha^{1}_{0i,t},\alpha^{1}_{1i,t})$. It
is more convenient to replace intercept $\alpha^{1}_{0i,t}$ by
$({\overline{p}}_{1,t},{\overline{p}}_{2,t})$ for each $i$ to write the
updating rule as

$p_{j,t}-{\overline{p}}_{j,t}=\alpha^{1}_{i,t}(p_{i,t}-{\overline{p}}_{i,t})\qquad\forall
i\neq j,$

from which we can recover the intercept according to

$\alpha^{1}_{0i,t}={\overline{p}}_{j,t}-\alpha^{1}_{i,t}{\overline{p}}_{i,t}\qquad\forall
i\neq j.$

Since

$p_{i,t}=(1-\pi_{i,t-1})\frac{A+C\alpha^{0}_{0,t-1}}{2B}+\pi_{i,t-1}\frac{A+C\alpha^{0}_{0,t-1}}{2(B-C\alpha^{1}_{1i,t-1})}+\epsilon_{i,t},$

Recall that

$\alpha^{0}_{0i,t}={\overline{p}}_{j,t}.$

Instead of

$(\pi_{1,t},\pi_{2,t};\alpha^{0}_{01,t},\alpha^{0}_{02,t};{\overline{p}}_{1,t},{\overline{p}}_{2,t};\alpha^{1}_{11,t},\alpha^{1}_{12,t}),$

we can investigate

$(\pi_{1,t},\pi_{2,t};{\overline{p}}_{1,t},{\overline{p}}_{2,t};\alpha^{1}_{11,t},\alpha^{1}_{12,t}).$

Moreover, we know we can treat

${\overline{p}}_{i,t}=p^{N}+\frac{1}{t}\sum\epsilon_{i,t}.$

Thus, our analysis focuses on the evolution of the remaining four state
variables

$(\pi_{1,t},\pi_{2,t};\alpha^{1}_{11,t},\alpha^{1}_{12,t})$

with the initial value set at the stable stationary point.

Note

$\alpha^{1}_{i,t}=\frac{\sum(p^{1}_{ik}-{\overline{p}}_{ik})(p_{jk}-{\overline{p}}_{jk})}{\sum(p^{1}_{ik}-{\overline{p}}_{ik})^{2}}$

where

$p_{jk}=(1-\pi_{jk})(b^{0}_{jk}-{\overline{p}}_{jk})+\pi_{jk}(b^{1}_{jk}-{\overline{p}}_{jk})+\epsilon_{jk}$

and

$p^{1}_{ik}=b^{1}_{ik}+\epsilon_{ik}.$

Since $b^{0}_{jk}=p^{N}$ and ${\overline{p}}_{jk}=p^{N}$,

$p_{jk}=\pi_{jk}(b^{1}_{jk}-p^{N})+\epsilon_{jk}.$

Around the Nash equilibrium outcome,
$(\alpha^{1}_{0i,t},\alpha^{1}_{1i,t})=(p^{N},0)$ and therefore,
$b^{1}_{i,n}(p^{N},0)=p^{N}$. Hence,

$\alpha^{1}_{1i,t}=\frac{\sum_{k}\epsilon_{1k}\sum\epsilon_{2k}}{\sum_{k}\epsilon^{2}_{ik}}\rightarrow
0,$

since $\epsilon_{1k}$ and $\epsilon_{2k}$ are mutually independent. Hence,

${\dot{\alpha}}^{1}_{1i}=-\alpha^{1}_{1i}$

confirming the stability of $\alpha^{1}_{1i}=0$. Thus, an event like

$\exists T\geq 1,\
(\alpha^{1}_{11,T},\alpha^{1}_{12,T})\in{\mathcal{W}}({\underline{\alpha}},{\underline{\beta}})$

where ${\mathcal{W}}({\underline{\alpha}},{\underline{\beta}})$ is a convex
hull of
$\\{({\underline{\alpha}},{\underline{\alpha}}),({\underline{\alpha}},{\underline{\beta}}),({\underline{\beta}},{\underline{\alpha}})\\}$
for ${\underline{\beta}}>{\underline{\alpha}}>0$.

######  Lemma B.2.

$\exists{\underline{\beta}}>{\underline{\alpha}}>0$ such that if the initial
condition $(\alpha^{1}_{11,1},\alpha^{1}_{12,1})$ is in
${\mathcal{W}}({\underline{\alpha}},{\underline{\beta}})$, then
$({\dot{\alpha}}^{1}_{11},{\dot{\alpha}}^{1}_{12})>0$. Moreover, we can choose
${\underline{\alpha}}$ and ${\underline{\beta}}$ satisfying

$0<\lim_{\sigma^{2}\rightarrow
0}\frac{{\underline{\alpha}}}{\sigma^{2}}<\infty\ \ \text{and}\ \
0<\lim_{\sigma^{2}\rightarrow 0}\frac{{\underline{\beta}}}{\sigma}<\infty.$

###### Proof.

Suppose that
$(\alpha^{1}_{11,1},\alpha^{1}_{12,1})=({\underline{\alpha}},{\underline{\alpha}})$
for some ${\underline{\alpha}}$ whose value will be determined shortly. Recall
${\overline{p}}_{1,t}={\overline{p}}_{2,t}=p^{N}$. Since
${\overline{p}}_{i,t}$ is an average of a function of
$(\alpha^{1}_{11,1},\alpha^{1}_{12,1})$, ${\overline{p}}_{i,t}$ moves a slower
time scale than $(\alpha^{1}_{11,1},\alpha^{1}_{12,1})$, and can be treated as
a constant equal to $p^{N}$ while investigating the long run dynamics of
$(\alpha^{1}_{11,1},\alpha^{1}_{12,1})$.

Note that with a small but positive, probability,
$(\alpha^{1}_{11,t},\alpha^{1}_{12,t})\in{\mathcal{W}}({\underline{\alpha}},{\underline{\beta}})$
can occur. Consider an “unusual” sequence of $(\epsilon_{1,t},\epsilon_{2,t})$
where the two shocks are almost perfectly positively correlated. While rare,
such an event has a vanishingly small positive probability and leads to
$\alpha^{1}_{11,t}$ and $\alpha^{1}_{12,t}$ increasing simultaneously at the
same rate to reach a small neighborhood of
$({\underline{\alpha}},{\underline{\alpha}})$ while keeping
${\overline{p}}_{1,t}$ and ${\overline{p}}_{2,t}$ close to $p^{N}$.

Since
$(\alpha^{1}_{11,t},\alpha^{1}_{12,t})=({\underline{\alpha}},{\underline{\alpha}})$,

$b^{1}_{1,t}-{\overline{p}}_{1,t}=b^{1}_{2,t}-{\overline{p}}_{2,t}.$

Therefore,

${\sf E}(b^{1}_{1}-p^{N})(b^{1}_{2}-p^{N})={\sf E}(b^{1}_{1}-p^{N})^{2}.$

Note

$p_{j,t}=(1-\pi_{j,t})(b^{0}_{j,t}-{\overline{p}}_{j,t})+\pi_{j,t}(b^{1}_{j,t}-{\overline{p}}_{j,t})+\epsilon_{j,t}.$

Since ${\overline{p}}_{j,t}=p^{N}$,

$p_{j,t}=\pi_{j,t}(b^{1}_{j,t}-p^{N})+\epsilon_{j,t}=\pi_{j,t}(b^{1}_{i,t}-p^{N})+\epsilon_{j,t}.$

Since $\epsilon_{1,t}$ and $\epsilon_{2,t}$ are orthogonal,

${\sf
E}(p_{1,t}-{\overline{p}}_{1,t})(p_{2,t}-{\overline{p}}_{2,t})=\pi_{j}{\sf
E}(b^{1}_{i}-p^{N})^{2}.$

Similarly,

${\sf E}(p^{1}_{1,t}-{\overline{p}}_{1,t})^{2}={\sf
E}(b^{1}_{1}-p^{N})^{2}+\sigma^{2}.$

Thus,

${\dot{\alpha}}^{1}_{i}=\frac{\pi_{j}(b^{1}_{i}-p^{N})^{2}}{(b^{1}_{i}-p^{N})^{2}+\sigma^{2}}-\alpha^{1}_{i}\qquad\forall
i\neq j\in\\{1,2\\}$

which is positive if and only if

$\displaystyle 0$ $\displaystyle<$
$\displaystyle(\pi_{j}-\alpha^{1}_{1i})(C\alpha^{1}_{1i}p^{N})^{2}-4\alpha^{1}_{1i}\sigma^{2}(B-C\alpha^{1}_{1i})^{2}$
$\displaystyle=$
$\displaystyle\alpha^{1}_{1i}\left[C^{2}(p^{N})^{2}(\pi_{j}-\alpha^{1}_{1i})\alpha^{1}_{1i}-4\sigma^{2}(B-C\alpha^{1}_{1i})^{2}\right].$

Since $\alpha^{1}_{1i}>0$, the equation is positive if and only if the
quadratic term inside of the bracket is positive. Let ${\underline{\alpha}}$
and ${\overline{\alpha}}$ be the two solutions of the quadratic equation. We
can easily show that $\exists{\overline{\sigma}}^{2}$ such that
$\forall\sigma^{2}\in(0,{\overline{\sigma}}^{2})$, the two roots of the
quadratic equations are real-valued, and

${\underline{\alpha}}{\overline{\alpha}}=\frac{4\sigma^{2}B^{2}}{C^{2}\left((p^{N})^{2}\pi_{j}+4\sigma^{2}\right)}$

and

$\lim_{\sigma^{2}\rightarrow
0}{\overline{\alpha}}=\pi_{j}\geq{\underline{\pi}}>0$ (B.23)

by Assumption B.1. Thus,

$\lim_{\sigma^{2}\rightarrow
0}\frac{{\underline{\alpha}}}{\sigma^{2}}=\frac{4B^{2}}{\pi_{j}C^{2}\left((p^{N})^{2}\pi_{j}+4\sigma^{2}\right)}>0.$
(B.24)

Given the initial condition
$(\alpha^{1}_{11},\alpha^{1}_{12})=({\underline{\alpha}},{\underline{\alpha}})$,
the associated ODE of $(\alpha^{1}_{11},\alpha^{1}_{12})$ is

$\displaystyle{\dot{\alpha}}^{1}_{11}$ $\displaystyle=$
$\displaystyle\frac{(b^{1}_{1}-p^{N})(b^{1}_{2}-p^{N})}{(b^{1}_{1}-p^{N})^{2}+\sigma^{2}}-\alpha^{1}_{11}$
$\displaystyle{\dot{\alpha}}^{1}_{12}$ $\displaystyle=$
$\displaystyle\frac{(b^{1}_{1}-p^{N})(b^{1}_{2}-p^{N})}{(b^{1}_{1}-p^{N})^{2}+\sigma^{2}}-\alpha^{1}_{12}.$

Since

$b^{1}_{i}-p^{N}=\frac{A+Cp^{N}(1-\alpha^{1}_{1i})}{2(B-C\alpha^{1}_{1i})}-p^{N},$
${\dot{\alpha}}^{1}_{1i}=\frac{\alpha^{1}_{11}\alpha^{1}_{12}C^{2}(p^{N})^{2}}{(\alpha^{1}_{1i})^{2}C^{2}(p^{N})^{2}+\sigma^{2}}-\alpha^{1}_{1i}\qquad\forall
i.$

We are interested in the dynamics of $(\alpha^{1}_{11,t},\alpha^{1}_{12,t})$
from the neighborhood of initial condition
$({\underline{\alpha}},{\underline{\alpha}})$ where
${\dot{\alpha}}^{1}_{1i}>0$ $\forall i$. Since

$\displaystyle{\dot{\alpha}}^{1}_{11}-{\dot{\alpha}}^{1}_{12}$
$\displaystyle=$
$\displaystyle\frac{\alpha^{1}_{11}\alpha^{1}_{12}C^{2}(p^{N})^{2}}{(\alpha^{1}_{11})^{2}C^{2}(p^{N})^{2}+\sigma^{2}}-\frac{\alpha^{1}_{11}\alpha^{1}_{12}C^{2}(p^{N})^{2}}{(\alpha^{1}_{1i})^{2}C^{2}(p^{N})^{2}+\sigma^{2}}-\alpha^{1}_{1i}+(\alpha^{1}_{12}-\alpha^{1}_{11})$
$\displaystyle=$
$\displaystyle\frac{\alpha^{1}_{11}\alpha^{1}_{12}C^{2}(p^{N})^{2}}{((\alpha^{1}_{11})^{2}C^{2}(p^{N})^{2}+\sigma^{2})((\alpha^{1}_{12})^{2}C^{2}(p^{N})^{2}+\sigma^{2})}(\alpha^{1}_{12}-\alpha^{1}_{11})(\alpha^{1}_{12}+\alpha^{1}_{11})+(\alpha^{1}_{12}-\alpha^{1}_{11})$
$\displaystyle=$
$\displaystyle(\alpha^{1}_{12}-\alpha^{1}_{11})\left[\frac{\alpha^{1}_{11}\alpha^{1}_{12}C^{2}(p^{N})^{2}}{((\alpha^{1}_{11})^{2}C^{2}(p^{N})^{2}+\sigma^{2})((\alpha^{1}_{12})^{2}C^{2}(p^{N})^{2}+\sigma^{2})}(\alpha^{1}_{12}+\alpha^{1}_{11})+1\right],$

${\dot{\alpha}}^{1}_{11}-{\dot{\alpha}}^{1}_{12}>0$ if and only if
$\alpha^{1}_{12}-\alpha^{1}_{11}>0$.

Fix $\alpha^{1}_{11}={\underline{\alpha}}$. We need to find out the largest
value of $\alpha^{1}_{12}>{\underline{\alpha}}$ satisfying
${\dot{\alpha}}^{1}_{12}>0$, since we know
$\alpha^{1}_{12}>\alpha^{1}_{11}={\underline{\alpha}}$ implies
${\dot{\alpha}}^{1}_{11}>{\dot{\alpha}}^{1}_{12}>0$. A simple calculation
shows

$\alpha^{1}_{12}\leq\frac{\sqrt{{\underline{\alpha}}C^{2}(p^{N})^{2}-\sigma^{2}}}{Cp^{N}}$

and

${\dot{\alpha}}^{1}_{12}>0.$

By the same token,

$\alpha^{1}_{11}\leq\frac{\sqrt{{\underline{\alpha}}C^{2}(p^{N})^{2}-\sigma^{2}}}{Cp^{N}}={\sf
O}(\sigma)$

if $\alpha^{1}_{12}={\underline{\alpha}}$, and
$\alpha^{1}_{11}\geq{\underline{\alpha}}$. Define

${\underline{\beta}}=\frac{\sqrt{{\underline{\alpha}}C^{2}(p^{N})^{2}-\sigma^{2}}}{Cp^{N}}\sim{\sf
O}(\sigma),$ (B.25)

since ${\underline{\alpha}}={\sf O}(\sigma^{2})$. ∎

For fixed $\sigma^{2}$, choose $({\underline{\alpha}},{\underline{\beta}})$
according to Lemma B.2. We are interested in the probability of an event

$\exists T\geq 1,\
(\alpha^{1}_{11,t},\alpha^{1}_{12,t})\in{\mathcal{W}}({\underline{\alpha}},{\underline{\beta}})$

from the neighborhood of the Nash equilibrium outcome
$(\alpha^{1}_{11,t},\alpha^{1}_{12,t})=(0,0)$ which is the stable stationary
outcome. Since
$(0,0)\not\in{\mathcal{W}}({\underline{\alpha}},{\underline{\beta}})$, and
$(\epsilon_{1,t},\epsilon_{2,t})$ have a good rate function, there is a real-
valued function $I^{\alpha}\mathrel{\mathop{\mathchar
58\relax}}{\mathcal{W}}({\underline{\alpha}},{\underline{\beta}})\rightarrow{\mathbb{R}}$
such that for any closed subset $F$ and any open subset $G$ of
${\mathcal{W}}({\underline{\alpha}},{\underline{\beta}})$

$\displaystyle-S^{*}(\alpha^{1},G,\sigma^{2})\equiv-\inf_{x\in
G}I^{\alpha}(x)$ $\displaystyle\leq$ $\displaystyle\lim_{K\rightarrow
0}\frac{1}{m(t_{K}+\tau)-t_{K}}\log{\sf P}\left(\exists\tau>0,\
\alpha^{1,K}_{1}(\tau)=(\alpha^{1,K}_{11}(\tau),\alpha^{1,K}_{12}(\tau))\in{\mathcal{W}}({\underline{\alpha}},{\underline{\beta}})\
|\ \alpha^{1}_{1,1}=(0,0)\right)$ $\displaystyle\leq$
$\displaystyle-\inf_{x\in F}I^{\alpha}(x)$

We now prove Lemma 5.6.

###### Proof.

Let $t_{K}$ is the time when
$(\alpha^{1}_{1,t_{K}},\alpha^{1}_{2,t_{K}})=(0,0)$. We are interested in the
evolution of $\alpha^{1}_{i,t}$ over the (fictitious) time interval $\tau$
when

$\alpha^{1}_{i,t}=\frac{\pi_{j}\sum_{t=t_{K}}^{m(t_{K}+\tau)}\epsilon_{1t}\epsilon_{2t}}{\sum_{t=t_{K}}^{m(t_{K}+\tau)}\epsilon^{2}_{it}}\geq{\underline{\alpha}}$

occurs. Since $b^{1}_{i,t}=p^{N}$, and $p_{i,t}=b^{1}_{i,t}+\epsilon_{i,t}$,

$\alpha^{1}_{i,t}=\frac{\pi_{j}\sum_{t=t_{K}}^{m(t_{K}+\tau)}\epsilon_{1t}\epsilon_{2t}}{\sum_{t=t_{K}}^{m(t_{K}+\tau)}}.$

Ignoring the difference in period $m(t_{K}+\tau)$, we write

$\frac{\pi_{j}\sum_{t=t_{K}}^{m(t_{K}+\tau)}\epsilon_{1t}\epsilon_{2t}}{\sum_{t=t_{K}}^{m(t_{K}+\tau)}\epsilon^{2}_{it}}={\underline{\alpha}}.$

At the same time,

${\underline{\alpha}}\leq\alpha^{1,K}_{1j,t}=\frac{\pi_{i}\sum_{t=t_{K}}^{m(t_{K}+\tau)}\epsilon_{1t}\epsilon_{2t}}{\sum_{t=t_{K}}^{m(t_{K}+\tau)}\epsilon^{2}_{jt}}\leq{\underline{\beta}}.$

After a tedious calculation, one can show that the event

$\alpha^{1,K}_{i}(\tau)\in{\mathcal{W}}({\underline{\alpha}},{\underline{\beta}})$

is equivalent to

$\left\\{1\leq\frac{\pi_{1}\sum_{t=t_{K}}^{m(t_{K}+\tau)}\epsilon^{2}_{1,t}}{\pi_{2}\sum_{t=t_{K}}^{m(t_{K}+\tau)}\epsilon^{2}_{2,t}}\leq\frac{{\underline{\beta}}}{{\underline{\alpha}}}\right\\}\cup\left\\{1\leq\frac{\pi_{2}\sum_{t=1}^{T}\epsilon^{2}_{2,t}}{\pi_{1}\sum_{t=1}^{T}\epsilon^{2}_{1,t}}\leq\frac{{\underline{\beta}}}{{\underline{\alpha}}}\right\\}.$

Define

${\mathcal{L}}_{i}=\left\\{1\leq\frac{\pi_{i}\sum_{t=t_{K}}^{m(t_{K}+\tau)}\epsilon^{2}_{1,t}}{\pi_{j}\sum_{t=t_{K}}^{m(t_{K}+\tau)}\epsilon^{2}_{j,t}}\leq\frac{{\underline{\beta}}}{{\underline{\alpha}}}\right\\}\qquad\forall
i\neq j\in\\{1,2\\}.$

To simplify notation, let us calculate the probability of
${\mathcal{L}}_{1}({\underline{\alpha}},{\underline{\beta}})$, where at time
$\tau$, $\alpha^{1,K}_{1}(\tau)={\underline{\alpha}}$ and
${\underline{\alpha}}\leq\alpha^{1,K}_{2}(\tau)\leq\frac{{\underline{\beta}}}{{\underline{\alpha}}}$.
The probability of
${\mathcal{L}}_{2}({\underline{\alpha}},{\underline{\beta}})$ can be
calculated by following the same logic.

Note that the event
${\mathcal{L}}_{1}({\underline{\alpha}},{\underline{\beta}})$

$1\leq\frac{\pi_{1}\sum_{t=t_{K}}^{m(t_{K}+\tau)}\epsilon^{2}_{1,t}}{\pi_{2}\sum_{t=t_{K}}^{m(t_{K}+\tau)}\epsilon^{2}_{2,t}}\leq\frac{{\underline{\beta}}}{{\underline{\alpha}}}$

is equivalent to

$\displaystyle\frac{1}{m(t_{K}+\tau)}\sum_{t=t_{K}}^{m(t_{K}+\tau)}\left(\pi_{1}\epsilon^{2}_{1,t}-\pi_{2}\epsilon^{2}_{2,t}\right)$
$\displaystyle\geq$ $\displaystyle 0$
$\displaystyle\frac{1}{m(t_{K}+\tau)}\sum_{t=t_{K}}^{m(t_{K}+\tau)}\left(\pi_{1}\epsilon^{2}_{1,t}-\frac{{\underline{\beta}}}{{\underline{\alpha}}}\pi_{2}\epsilon^{2}_{2,t}\right)$
$\displaystyle\leq$ $\displaystyle 0$

which is, in turn, equivalent to

$\displaystyle\frac{1}{m(t_{K}+\tau)}\sum_{t=t_{K}}^{m(t_{K}+\tau)}\left(\pi_{1}\frac{\epsilon^{2}_{1,t}}{\sigma^{2}_{t_{K}}}-\pi_{2}\frac{\epsilon^{2}_{2,t}}{\sigma^{2}_{t_{K}}}\right)$
$\displaystyle\geq$ $\displaystyle 0$
$\displaystyle\frac{1}{m(t_{K}+\tau)}\sum_{t=t_{K}}^{m(t_{K}+\tau)}\left(\pi_{1}\frac{\epsilon^{2}_{1,t}}{\sigma^{2}_{t_{K}}}-\frac{{\underline{\beta}}}{{\underline{\alpha}}}\pi_{2}\frac{\epsilon^{2}_{2,t}}{\sigma^{2}_{t_{K}}}\right)$
$\displaystyle\leq$ $\displaystyle 0.$

Given $\tau>0$, we want to calculate

$\lim_{K\rightarrow\infty}{\sf
P}\left({\mathcal{W}}_{1}({\underline{\alpha}},{\underline{\beta}})\right).$
(B.26)

Since $\forall\tau>0$,

$\lim_{K\rightarrow\infty}\frac{\sigma^{2}_{t}}{\sigma^{2}_{t_{K}}}=1\qquad\forall
t\in\\{t_{K},\ldots,m(t_{K}+\tau)\\},$ $\lim_{K\rightarrow\infty}{\sf
P}\left({\mathcal{W}}_{1}({\underline{\alpha}},{\underline{\beta}})\right)\\\
=\lim_{K\rightarrow\infty}{\sf
P}\left(\begin{matrix}\frac{1}{m(t_{K}+\tau)-t_{K}}\sum_{t=t_{K}}^{m(t_{K}+\tau)}\left(\pi_{1}\frac{\epsilon^{2}_{1,t}}{\sigma^{2}_{t}}-\pi_{2}\frac{\epsilon^{2}_{2,t}}{\sigma^{2}_{t}}\right)\geq
0\\\\[2.0pt]
\frac{1}{m(t_{K}+\tau)-t_{K}}\sum_{t=t_{K}}^{m(t_{K}+\tau)}\left(\pi_{1}\frac{\epsilon^{2}_{1,t}}{\sigma^{2}_{t}}-\frac{{\underline{\beta}}}{{\underline{\alpha}}}\pi_{2}\frac{\epsilon^{2}_{2,t}}{\sigma^{2}_{t}}\right)\leq
0\end{matrix}\right).$

Note that $\forall t\in\\{t_{K},\ldots,m(t_{K}+\tau)\\}$,
$\frac{\epsilon^{2}_{i,t}}{\sigma^{2}_{t}}$ is i.i.d. Let $x_{i,t}$ be a
random variable drawn from the same distribution as
$\frac{\epsilon^{1}_{i,t_{K}}}{\sigma^{2}_{t_{K}}}$ for
$t\in\\{t_{K},\ldots,m(t_{K}+\tau)\\}$. clearly, $x_{i,t}$ is i.i.d. with mean
1 and a finite variance. Then, (B.26) is equal to

$\lim_{K\rightarrow\infty}{\sf
P}\left(\begin{matrix}\frac{1}{m(t_{K}+\tau)-t_{K}}\sum_{t=t_{K}}^{m(t_{K}+\tau)}\left(\pi_{1}x_{1,t}-\pi_{2}x_{2,t}\right)\geq
0\\\\[2.0pt]
\frac{1}{m(t_{K}+\tau)-t_{K}}\sum_{t=t_{K}}^{m(t_{K}+\tau)}\left(\pi_{1}x_{1,t}-\frac{{\underline{\beta}}}{{\underline{\alpha}}}\pi_{2}x_{2,t}\right)\leq
0\end{matrix}\right).$

Since ${\underline{\beta}}\sim{\sf O}(\sigma_{t_{K}})$ and
${\underline{\alpha}}\sim{\sf O}(\sigma^{2}_{t_{K}})$,

$\lim_{K\rightarrow\infty}\frac{{\underline{\beta}}}{{\underline{\alpha}}}=\infty.$

Define

${\mathcal{L}}^{*}_{1}(\sigma)=\left\\{(x_{1},x_{2})\ \mid\
\pi_{1}x_{1}-\pi_{2}x_{2}\geq 0\ \text{and}\
\pi_{1}x_{1}-\frac{{\underline{\beta}}}{{\underline{\alpha}}}\pi_{2}x_{2}\leq
0\right\\}$

since ${\underline{\beta}}$ and ${\underline{\alpha}}$ is parameterized by
$\sigma$. Recall that $({\sf E}x_{1,t},{\sf E}x_{2,t})=(1,1)$. If
$\pi_{1}\geq\pi_{2}$, then

$({\sf E}x_{1,t},{\sf E}x_{2,t})\in{\mathcal{L}}^{*}_{1}(\sigma)$

for any sufficiently large $K$. Moreover, since $\pi_{1}$ and $\pi_{2}$ are
independent of $\sigma^{2}$,

$\inf_{\sigma^{2}>0}\lim_{K\rightarrow\infty}{\sf
P}\left({\mathcal{L}}_{1}({\underline{\alpha}},{\underline{\beta}})\right)>0,$

which implies that

$-\lim_{\sigma^{2}\rightarrow 0}\lim_{\tau\rightarrow
0}\lim_{K\rightarrow\infty}\frac{1}{t_{K}}\log{\sf
P}\left({\mathcal{W}}_{1}({\underline{\alpha}},{\underline{\beta}})\right)=0.$

Thus, the large deviation rate function must be 0.

If $\pi_{1}<\pi_{2}$, then $\forall\sigma>0$,

$({\sf E}x_{1,t},{\sf E}x_{2,t})\not\in{\mathcal{L}}(\sigma).$ (B.27)

Recall that $\epsilon_{i,t}$ has a finite good rate function, and $x_{i,t}$ is
a continuous function of $\epsilon_{i,t}$. Thus, the contraction principle
implies that $x_{i,t}$ has a finite good rate function, say
$S^{x}({\mathcal{L}}^{*}_{1}(\sigma))$. Moreover, if $\sigma^{\prime}<\sigma$,

${\mathcal{L}}(\sigma)\subset{\mathcal{L}}(\sigma^{\prime}).$

Hence,

$S^{x}({\mathcal{L}}^{*}_{1}(\sigma))\geq
S^{x}({\mathcal{L}}^{*}_{1}(\sigma^{\prime})).$

Therefore,

$\limsup_{\sigma\rightarrow 0}S^{x}({\mathcal{L}}^{*}_{1}(\sigma))<\infty.$

Since $S^{x}$ is a good rate function, for any open subset
$G\subset{\mathcal{L}}^{*}_{1}(\sigma)$,

$\inf_{\sigma^{2}>0}\lim_{K\rightarrow\infty}{\sf
P}\left({\mathcal{L}}_{1}({\underline{\alpha}},{\underline{\beta}})\right)\geq-\inf_{G\subset{\mathcal{L}}^{*}_{1}(\sigma)}S^{x}(G)>-\infty.$

Combining the two cases, we conclude that

$-\lim_{\sigma^{2}\rightarrow 0}\lim_{\tau\rightarrow
0}\lim_{K\rightarrow\infty}\frac{1}{t_{K}}\log{\sf
P}\left({\mathcal{L}}_{1}({\underline{\alpha}},{\underline{\beta}})\right)<\infty.$

∎

###  B.4. Dynamics of $\pi_{i,t}$

The following is the proof of Proposition 5.7 in the text.

###### Proof.

We need to show that $\forall\tau>0$, $\forall\nu>0$, $\exists K(\nu,\tau)$
such that $\forall K>K(\nu,\tau)$,

${\sf
P}\left(\frac{1}{m(t_{K}+\tau)-t_{K}}\sum_{t=t_{K}}^{m(t_{K}+\tau)}\Pi^{1}_{i,t}-\Pi^{N}>0\right)>1-\nu.$

Fix $\\{\sigma^{2}_{K}\\}_{K=1}^{\infty}$ where $\sigma^{2}_{K}\rightarrow 0$.
Fix an arbitrarily small $\tau>0$, $\nu^{\prime}>0$, a decreasing sequence
$\\{\mu_{K}\\}_{K=1}^{\infty}$ of positive numbers with

$\lim_{K\rightarrow\infty}\mu_{K}=0$

to examine successively smaller neighborhood ${\mathcal{N}}_{\mu_{K}}(0,0)$ of
$(\alpha^{1}_{1},\alpha^{1}_{2})=(0,0)$ but

$({\underline{\alpha}},{\underline{\alpha}})\in{\mathcal{N}}_{\mu_{K}}(0,0)\qquad\forall
K.$

Let $S^{*}_{i}(\mu_{K},\sigma^{2}_{K})$ be the rate function that
$(\alpha^{1}_{11,t},\alpha_{12,t})$ escapes from
${\mathcal{N}}_{\mu_{K}}(0,0)$ starting from the stable stationary point
$(0,0)$ of the mean dynamics of $(\alpha^{1}_{11,t},\alpha_{12,t})$. By the
definition of the rate function, we know that $S^{*}(\mu_{K},\sigma^{2}_{K})$
is an increasing function of $\mu_{K}$ with

$\lim_{\mu_{K}\rightarrow 0}S^{*}(\mu_{K},\sigma^{2}_{K})=0.$

and for a fixed $\mu_{K}$,

$\limsup_{\sigma^{2}_{K}\rightarrow 0}S^{*}(\mu_{K},\sigma^{2}_{K})<\infty.$

Therefore,

$S^{*}(\mu_{K},\sigma^{2}_{K})\downarrow 0$

as $K\rightarrow\infty$. For each $K\in\\{1,2,\ldots\\}$, choose $t_{K}$
according to

$t_{K}=\left\lceil-\frac{\log\nu^{\prime}}{S^{*}(\mu_{k},\sigma^{2}_{K})}\right\rceil.$

so that

$e^{-t_{K}S^{*}(\mu_{k})}=\nu^{\prime}$

ignoring the integer problem. As $K\rightarrow\infty$,
$t_{K}\rightarrow\infty$. Since ${\lambda_{t}}=1/t$,
$m(t_{K}+\tau)-t_{K}\rightarrow\infty$ as $K\rightarrow\infty$.

Let us consider random variable $\Pi^{1}_{i,t}$. The probability that
$(\alpha^{1}_{11,t},\alpha^{1}_{12,t})$ exists ${\mathcal{N}}_{\mu_{K}}$
between $t_{K}$ and $m(t_{K}+\tau)$ converges to
$e^{-t_{K}S^{*}(\mu_{K},\sigma^{2}_{K})}$ (Dupuis and Kushner (1989)). Upon
exiting ${\mathcal{N}}_{\mu_{K}}(0,0)$, the mean dynamics of
$(\alpha^{1}_{11,t},\alpha^{1}_{12,t})$ is pointing away from $(0,0)$ but to
$(1,1)$ so that $\Pi^{1}_{i,t}$ strictly increases. Thus, with probability
$e^{-t_{K}S^{*}(\mu_{K},\sigma^{2}_{K})}$, $\Pi^{1}_{i,t}=\Pi^{N}+\zeta(\tau)$
where $\zeta(\tau)>0$ with $\zeta(0)=0$. Thus, $\forall
t\in\\{t_{K},\ldots,m(t_{K}+\tau)\\}$,

${\sf E}\Pi^{1}_{i,t}-\Pi^{N}\geq
e^{-t_{K}S^{*}(\mu_{K},\sigma^{2}_{K})}(\Pi^{N}+\zeta(\tau)-\Pi^{N})-{\sf
O}(\mu_{K})\left(1-e^{-t_{K}S^{*}(\mu_{K},\sigma^{2}_{K})}\right)$

under the assumption that within ${\mathcal{N}}_{\mu_{K}}$,
$\Pi^{1}_{i,t}\leq\Pi^{N}$, but the difference must be bounded by ${\sf
O}(\mu_{K})$.

Since $e^{-t_{K}S^{*}(\mu_{K},\sigma^{2}_{K})}=\nu^{\prime}$, and ${\sf
O}(\mu_{K})\rightarrow 0$ as $K\rightarrow 0$, $\exists K^{\prime}$ such that
$\forall K\geq K^{\prime}$, $\forall t\in\\{t_{K},\ldots,m(t_{K}+\tau)\\}$,

${\sf E}\Pi^{1}_{i,t}-\Pi^{N}\geq\frac{1}{2}\nu^{\prime}\zeta(\tau).$

Thus, $\forall\nu\in\left(0,\frac{1}{4}\nu^{\prime}\zeta(\tau)\right)$,
$\exists K(\nu,\tau)$ such that

${\sf
P}\left(\frac{1}{m(t_{K}+\tau)-t_{K}}\sum_{t=t_{K}}^{m(t_{K}+\tau)}\Pi^{1}_{i,t}-\Pi^{N}>\nu\right)>1-\nu$

from which the conclusion follows. ∎

##  Appendix C Convergence and Stability Calculations

###  C.1. Convergence and Stability under $\mathcal{M}^{0}$

In the specification $\mathcal{M}^{0}$, each firm $i$ forecasts its opponent’s
price $p_{j,t}$ by forming a discounted average of past prices. We denote the
current estimate $\alpha^{0}_{i,t}$, and the best response function which
determines the expected price is

$b^{0}(\alpha^{0}_{i})=\frac{A+C\alpha^{0}_{i}}{2B}.$

Everything is symmetric in the model, so the best response functions are the
same, only the beliefs differ. We stack the beliefs into the vector
$\alpha^{0}_{t}=[\alpha^{0}_{1,t},\alpha^{0}_{2,t}]^{\prime}$ whose evolution
follows:

$\displaystyle\left[\begin{matrix}\alpha^{0}_{1,t}\\\
\alpha^{0}_{2,t}\end{matrix}\right]$ $\displaystyle=$
$\displaystyle\left[\begin{matrix}\alpha^{0}_{1,t-1}\\\
\alpha^{0}_{2,t-1}\end{matrix}\right]+\lambda_{t}\left[\begin{matrix}p_{2,t}-\alpha^{0}_{1,t-1}\\\
p_{1,t}-\alpha^{0}_{2,t-1}\end{matrix}\right]$ (C.28) $\displaystyle=$
$\displaystyle\left[\begin{matrix}\alpha^{0}_{1,t-1}\\\
\alpha^{0}_{2,t-1}\end{matrix}\right]+\lambda_{t}\left[\begin{matrix}b^{0}(\alpha^{0}_{2,t-1})-\alpha^{0}_{1,t-1}+\epsilon_{2,t}\\\
b^{0}(\alpha^{0}_{1,t-1})-\alpha^{0}_{2,t-1}+\epsilon_{1,t}\end{matrix}\right]$

This last equation says that the increment in beliefs
$\alpha^{0}_{t}-\alpha^{0}_{t-1}$ is equal to the gain $\lambda_{t}$
multiplied by a stochastic update term. We can then think of $\lambda_{t}$ as
the notional time between observations and analyze the limit as
$\lambda_{t}\rightarrow 0$. Along this limit the increment between
observations converges to the time derivative, and since the impact of the
shocks $\epsilon_{i,t}$ is of order $\lambda$ they become asymptotically
negligible. Thus as $\lambda_{t}\rightarrow 0$ the stochastic belief process
$\\{\alpha^{0}_{t}\\}$ converges to the stable stationary solution of the
ordinary differential equation:

$\dot{\alpha}^{0}(t)=g(\alpha^{0}(t))\equiv\left[\begin{matrix}b^{0}(\alpha^{0}_{2}(t))-\alpha^{0}_{1}(t)\\\
b^{0}(\alpha^{0}_{1}(t))-\alpha^{0}_{2}(t)\end{matrix}\right]$

This linear differential equation has a unique equilibrium point
$\bar{\alpha}^{0}$ which is symmetric and where beliefs are the Nash
equilibrium prices:

$\dot{\alpha}^{0}(t)=0\Rightarrow\left[\begin{matrix}b^{0}(\bar{\alpha}^{0}_{2})-\bar{\alpha}^{0}_{1}\\\
b^{0}(\bar{\alpha}^{0}_{1})-\bar{\alpha}^{0}_{2}\end{matrix}\right]=0\Rightarrow\bar{\alpha}^{0}_{1}=\bar{\alpha}^{0}_{2}\Rightarrow\bar{\alpha}^{0}_{i}=b(\bar{\alpha}^{0}_{i})=\frac{A}{2B-C}=p^{N}.$

Moreover, since the differential equation is linear, the global stability of
the equilibrium is determined by the eigenvalues of the Jacobian matrix:

$g^{\prime}(\bar{\alpha})=\left[\begin{array}[]{rr}-1&\frac{C}{2B}\\\
\frac{C}{2B}&-1\end{array}\right],$

which has eigenvalues equal to $-1\pm\frac{C}{2B}$. Since we have already
assumed that $C<B$, both eigenvalues are negative, and the vector $\bar{a}$ is
globally stable equilibrium point of the ODE.

##  Appendix D Convergence and Stability under $\mathcal{M}^{1}$

The analysis of beliefs under specification $\mathcal{M}^{1}$ is conceptually
very similar, but now the dimensionality of the problem grows. Moreover, the
analysis becomes slightly more complex because the dependence of the key
equations on beliefs and shocks is nonlinear. In particular, under
$\mathcal{M}^{1}$ each firm estimates a vector
$\alpha^{1}_{i,t}=[\alpha^{1}_{0i,t},\alpha^{1}_{1i,t}]^{\prime}$ of the
intercept and slope parameters in the reaction function (2.4). Furthermore, in
the recursive least squares algorithm (3.9), each firm also estimates the
second moment matrix $R_{i,t}$. This matrix is symmetric, and so we can
economize by only tracking only the two distinct time-varying elements, which
we collect in a vector $r_{it}=[R_{i,t}(1,2),R_{i,t}(2,2)]^{\prime}$. Thus for
each firm, we can stack the beliefs into the $4\times 1$ column vector

$\theta_{i,t}=[(\alpha^{1}_{i,t})^{\prime},r_{i,t}^{\prime}]^{\prime},$

and similarly can stack the beliefs of the two firms as

$\alpha^{1}_{t}=[(\alpha^{1}_{1,t})^{\prime},(\alpha^{1}_{2,t})^{\prime}]^{\prime}$

and

$\theta_{t}=[\theta_{1,t}^{\prime},\theta_{2,t}^{\prime}]^{\prime}.$

As above, we can write the best response of a firm given its current beliefs
$\alpha^{1}_{i}$ as:

$b(\alpha^{1}_{i})=\frac{A+C\alpha^{1}_{0i}}{2(B-C\alpha^{1}_{1i})},$

which is now nonlinear in $\alpha^{1}_{i}$.

Using the best response functions the price realizations, we can rewrite the
dynamics of each firm’s beliefs from (3.9) as:

$\displaystyle\alpha^{1}_{i,t}$ $\displaystyle=$
$\displaystyle\alpha^{1}_{i,t-1}+\lambda
R^{-1}_{i,t-1}\left[\begin{matrix}b(\alpha^{1}_{j,t-1})-\alpha^{1}_{0i,t-1}+\epsilon_{j,t}-\alpha^{1}_{1i,t-1}(b(\alpha^{1}_{i,t-1})+\epsilon_{i,t})\\\
\left[b(\alpha^{1}_{j,t-1})-\alpha^{1}_{0i,t-1}+\epsilon_{j,t}-\alpha^{1}_{1i,t-1}(b(\alpha^{1}_{i,t-1})+\epsilon_{i,t})\right](b(\alpha^{1}_{i,t-1})+\epsilon_{i,t})\end{matrix}\right]$
$\displaystyle R_{i,t}$ $\displaystyle=$ $\displaystyle
R_{i,t-1}+\lambda\left(\left[\begin{matrix}1&b(\alpha^{1}_{i,t-1})+\epsilon_{i,t}\\\
b(\alpha^{1}_{i,t-1})+\epsilon_{i,t}&(b(\alpha^{1}_{i,t-1})+\epsilon_{i,t})^{2}\end{matrix}\right]-R_{i,t-1}\right).$
(D.29)

In addition to being nonlinear, the belief dynamics are now a quadratic
function of the shocks.

For the calculations below, it will be convenient to define a vector function
capturing the update terms in the $\alpha^{1}_{i,t}$ dynamics:

$G_{i}(\alpha^{1},\epsilon_{i,t},\epsilon_{j,t})=\left[\begin{matrix}G_{0i}(\alpha^{1})+\epsilon_{j,t}-\alpha^{1}_{1i}\epsilon_{i,t}\\\
G_{0i}(\alpha^{1})b(\alpha^{1}_{i})+\left[G_{0i}(\alpha^{1})-\alpha^{1}_{1i}b(\alpha^{1}_{i})\right]\epsilon_{i,t}+b(\alpha^{1}_{i})\epsilon_{j,t}+\epsilon_{i,t}\epsilon_{j,t}-\alpha^{1}_{1i}\epsilon_{i,t}^{2}\end{matrix}\right]$

where

$G_{0i}(\alpha^{1})=b(\alpha^{1}_{j})-\alpha^{1}_{0i}-\alpha^{1}_{1i}b(\alpha^{1}_{i}).$

Then the first equation in the belief updating can be written:

$\alpha^{1}_{i,t}=\alpha^{1}_{i,t-1}+\lambda
R^{-1}_{i,t-1}G_{i}(\alpha^{1}_{t},\epsilon_{i,t},\epsilon_{j,t}).$

Everything is symmetric for firm $j$, appropriately switching the roles of own
and opponent’s beliefs and shocks. Using the independence of the shocks and
that $E\epsilon_{it}^{2}=\sigma^{2}$, we can then define the expected update
function as:

$g_{i}(\alpha^{1})=E[G_{i}(\alpha^{1},\epsilon_{i,t},\epsilon_{j,t})]=\left[\begin{matrix}G_{0i}(\alpha^{1})\\\
G_{0i}(\alpha^{1})b(\alpha^{1}_{i})-\alpha^{1}_{1i}\sigma^{2}\end{matrix}\right]$

We can then use the same logic as above to study the small gain limit as
$\lambda_{t}\rightarrow 0$. Relying on the same general stochastic
approximation results, as the gain converges to zero the firms’ beliefs
converge weakly to the solution of the differential equations:

$\displaystyle\dot{\alpha}^{1}_{i}(t)$ $\displaystyle=$ $\displaystyle
R_{i}(t)^{-1}g_{i}(\alpha^{1}(t))$ $\displaystyle\dot{R}_{i}(t)$
$\displaystyle=$ $\displaystyle\left[\begin{matrix}1&b(\alpha^{1}_{i}(t))\\\
b(\alpha^{1}_{i}(t))&b(\alpha^{1}_{i}(t))^{2}+\sigma^{2}\end{matrix}\right]-R_{i}(t).$

It is straightforward to see that the equilibrium of this specification leads
to the same outcomes as the case of ${\mathcal{M}}^{0}$. In particular, since
$R_{i}(t)$ is nonsingular, an equilibrium point $\bar{\alpha}^{1}$ satisfies:

$\dot{\alpha}^{1}_{i}=0\Rightarrow g_{i}(\bar{\alpha}^{1})=0\Rightarrow
G_{0i}(\bar{\alpha}^{1})=0\text{ and
}G_{0i}(\bar{\alpha}^{1})b(\bar{\alpha}^{1}_{i})-\bar{\alpha}^{1}_{1i}\sigma^{2}=0.$
(D.30)

The only way to satisfy both of the last two conditions is to have
$\alpha^{1}_{1i}=0$. Since this holds for $i=1,2$, we can then reduce
$G_{0i}(\bar{\alpha}^{1})=b(\bar{\alpha}^{1}_{j})-\bar{\alpha}^{1}_{0i}$, so
$[G_{01}(\bar{\alpha}^{1}),G_{02}(\bar{\alpha}^{1})]=g([\bar{\alpha}^{1}_{01},\alpha^{1}_{02}]^{\prime})$,
the same function as in $\mathcal{M}^{0}$ above that defines an equilibrium in
that specification. Thus the unique equilibrium is symmetric and satisfies