Full text of Working Papers (Federal Reserve Bank of Chicago) : Simple Markov-Perfect Industry Dynamics, Working Paper 2010-21

View original document
The full text on this page is automatically extracted from the file linked above and may contain errors and inconsistencies.
Federal Reserve Bank of Chicago

Simple Markov-Perfect Industry
Dynamics
Jaap H. Abbring, Jeffrey R. Campbell,
and Nan Yang

November 30, 2010
WP 2010-21

Simple Markov-Perfect Industry Dynamics∗
Jaap H. Abbring†

Jeffrey R. Campbell‡

Nan Yang§

November 30, 2010

Abstract
This paper develops a tractable model for the computational and empirical analysis
of infinite-horizon oligopoly dynamics. It features aggregate demand uncertainty, sunk
entry costs, stochastic idiosyncratic technological progress, and irreversible exit. We
develop an algorithm for computing a symmetric Markov-perfect equilibrium quickly
by finding the fixed points to a finite sequence of low-dimensional contraction mappings. If at most two heterogenous firms serve the industry, the resuilt is the unique
“natural” equilibrium in which a high profitability firm never exits leaving behind a
low profitability competitor. With more than two firms, the algorithm always finds a
natural equilibrium. We present a simple rule for checking ex post whether the calculated equilibrium is unique, and we illustrate the model’s application by assessing how
price collusion impacts consumer and total surplus in a market for a new product that
requires costly development. The results confirm Fershtman and Pakes’ (2000) finding
that collusive pricing can increase consumer surplus by stimulating product development. A distinguishing feature of our analysis is that we are able to assess the results’
robustness across hundreds of parameter values in only a few minutes on an off-the-shelf
laptop computer.

∗

We thank R. Andrew Butters and Xiye Yang for their expert research assistance.
CentER, Department of Econometrics & OR, Tilburg University. E-mail: J.H.Abbring@uvt.nl
‡
Federal Reserve Bank of Chicago. E-mail: jcampbell@frbchi.org
§
VU University Amsterdam and Tinbergen Institute. E-mail: yang@tinbergen.nl
JEL Code: L13
Keywords: Sunk costs, Demand uncertainty, Markov-perfect equilibrium, Learning-by-doing, Technology
innovation
†

1

Introduction

This paper supplies fast, effective, and simple computational methods for important special
cases of Ericson and Pakes’ (1995) model of dynamic oligopoly. These cases feature aggregate
uncertainty, sunk entry costs, and stochastic firm-specific technological progress; but they
exclude investment decisions other than entry and exit. This simplification facilitates a range
of equilibrium characterization, existence, and uniqueness results that are not available for the
more general framework. Moreover, it enables the development of algorithms that calculate
equilibria by finding the fixed points of a finite sequence of low-dimensional contraction
mappings. These results can be used to explore some key aspects of Ericson and Pakes’
model with very low computational cost. This is often useful in itself, and can serve as a first
stage of a richer analysis with a more complex specification.
Substantial methodological progress in the computation of Markov-perfect equilibria followed Ericson and Pakes’ original presentation of their framework. Nevertheless, Doraszelski
and Pakes (2007) note that these methodological developments are only in their infancy
and applications remain rare. This paper contributes to this literature by developing relatively rich analytical results and effective computational methods for a comparatively simple
model. It shares this approach with Abbring and Campbell’s (2010) analysis of last-in firstout oligopoly dynamics. They consider a dynamic extension of Bresnahan and Reiss’ (1990)
static entry model that can naturally be applied to the empirical analysis of market level entry
and exit data (Abbring, Campbell, and Yang, 2010). Timing and expectational assumptions
simplify its equilibrium analysis: Otherwise homogeneous firms move sequentially, oldest
first; and older firms never exit expecting to leave a younger firm behind. The present paper
contributes more directly to the analysis of Ericson and Pakes’ framework and its potential applications, because it allows for idiosyncratic technological progress in a model with
simultaneously moving incumbent firms.
Our results leverage one key insight into the structure of payoffs in a symmetric Markovperfect equilibrium: If any firm chooses to exit with positive probability, then all identically
situated firms must have an expected continuation value of zero. This allows us to calculate firms’ expected continuation values at some nodes of the game tree without knowing
everything about how the game will proceed thereafter. Our results demonstrate how to use
these initial calculations to recover all equilibrium payoffs and actions. For this task, it is
very helpful to know beforehand that adding an active firm to an industry weakly reduces
all other firms’ continuation values. We prove that this intuitive property must hold if at
most two firms can serve the industry at one time. For the more general oligopoly case, we
show that if a Markov-perfect equilibrium with such monotonicity exists, then it is essentially
unique. In this case, the algorithm we propose always computes it. If no such equilibrium

1

exists, then our algorithm can be easily adapted to find all equilibria satisfying a desirable
property we call “one-shot renegotiation proofness”.
The remainder of this paper proceeds as follows. The next section presents the model’s
primitives. It also discusses the equilibrium concept used, natural Markov-perfect equilibrium. As in Cabral (1993), the restriction to “natural” equilibrium requires no firm with
high flow profits to exit leaving a lower-profitability rival in the market.
Section 3 covers the special case of a market that can support at most two active firms.
The proofs of equilibrium existence and uniqueness are constructive, and so they naturally
generate an algorithm for equilibrium computation. Its central steps find the fixed points of a
finite number of low-dimensional contraction mappings. We apply the results to a numerical
analysis of the effects of relaxing short-term price competition on welfare-enhancing product
development, earlier explored by Fershtman and Pakes (2000).
Section 4 begins with extending the algorithm from duopoly model to accommodate three
or more potentially heterogeneous firms. We then show that if a natural equilibrium in which
adding incumbent firms weakly lowers continuation values exists, then it is essentially unique
and the algorithm computes it. Next, we illustrate with an example that it is possible for
entry to increase an incumbent’s expected discounted payoff. This counterintuitive effect
of entry arises from the entry deterring effects of competition. Our analysis identifies two
sources of equilibrium multiplicity, both of which require entry to raise an incumbent’s equilibrium payoff at some point. One arises from the failure of incumbent firms to coordinate on
survival when this is mutually beneficial. We propose to exclude such coordination failures
by requiring equilibria to be “one-shot renegotiation proof”. The other occurs when multiple
mixed strategies leave incumbents indifferent between exit and continuation.

2

The Model

In Ericson and Pakes (1995), a countable number of firms with heterogeneous productivity
levels serve a single industry. Entry requires the payment of a sunk cost, and exit allows
firms to avoid per-period fixed costs of production. Surviving incumbent firms choose investments that stochastically improve their technologies. Exogenous stochastic increases in
the knowledge stock outside the industry increase the quality of an outside good and, this
way, decrease all incumbent firms’ profits simultaneously. These outside knowledge shocks
are embodied in potential entrants to the industry, and therefore do not affect their profits.
Two main changes to Ericson and Pakes’ primitive assumptions facilitate our demonstration of Markov-perfect equilibrium uniqueness and our algorithm for its rapid computation.
First, we assume that productivity evolves exogenously, instead of allowing firms to make
costly investments in accelerating technological progress. Second, we replace the common
2

Start with
(Ct , Nt )

Firm f gets
π(Nt , Ct , Ktf ) if active

Entry
decision
(t, 1)
a = 0; Pass & earn 0

a = 1; Pay ϕ & enter

a ∈ [0, 1]

Entry
decision
(t, 2)

Entry
decision
(t, Jt + 1)

Simultaneous
continuation
decisions

f
Nature chooses Kt+1
using
Π if firm f is active and
chooses Ct+1 ∼ Q(·|Ct ).

Go to next period
with (Ct+1 , Nt+1 )

Figure 1: The Sequence of Events and Actions within a Period
negative shocks to the incumbents’ profits by general aggregate demand shocks that equally
affect the profits of incumbent firms and potential entrants.

2.1

Primitive Assumptions

The model consists of a single oligopolistic market in discrete time t ∈ Z? ≡ {0, 1, . . .}. A
countable number of firms potentially serve the market. These are indexed by f ∈ Z? × N.
Below we refer to f as the firm’s name. At a given time t, some of the firms are active, and
the remaining producers are inactive. Each active firm f has an idiosyncratic productivity
type Ktf that takes values in K ≡ {1, . . . , ǩ}. Stack the numbers of active firms with each
productivity level at time t into the ǩ × 1 vector Nt , the market structure. Initially, no firms
serve the market: N0 equals a vector of zeros. Subsequently; entry, stochastic productivity
improvement, and exit determine its evolution.
3

Figure 1 illustrates the sequence of events and actions within a period t. It begins with
the inherited values of two state variables, Nt and a scalar index of demand Ct ∈ [ĉ, č], with
č < ∞. With these in place, the active participants receive their profits from serving the
market. For a type Kt firm facing the market structure Nt , these equal π(Nt , Ct , Kt ). 1
We assume that a firm’s flow profit decreases with the number and productivity of its
competitors and increases with its own productivity. For this assumption’s formal statement,
we use ιk to denote a ǩ × 1 vector with a one in its kth position and zeros elsewhere, and set
ι0 ≡ 0. This allows us to denote a market structure with at least one type k firm with n + ιk .
Assumption 1 (Monotone Producer Surplus). For all productivity types k ∈ K, demand
states c ∈ [ĉ, č], and market structures n ∈ Zǩ? :
1. π(ιk + n, c, k) ≤ π̌ < ∞ for all c ∈ [ĉ, č]
2. π(ιk + n, c, k) ≤ π(ιk + n, d, k) for all c, d ∈ [ĉ, č] such that c < d.
3. π(ιk + n + ιl , c, k) < π (ιk + n + ιl−1 , c, k) for all l ∈ K;
4. π(ιk + n, c, k) → −κ(k) < 0 as the number of firms in n goes to infinity; and
5. π(ιk + ιl + n, c, k) ≤ π(ιk + ιl + n, c, l) for all k, l ∈ K such that k < l, with strict
inequality hold for some c ∈ [ĉ, č].
In item 4, κ(k) represents a type k firm’s per-period fixed cost. After production, firms
with names in {t} × N make entry decisions sequentially in the order of their names, starting
with (t, 1). These continue until a firm chooses to remain out of the industry. We denote the
number of entrants in period t with Jt , so the name of the first potential entrant choosing
to stay out of the market and thereby ending its entry stage is (t, Jt + 1). The cost of entry
is ϕ > 0. After paying this cost, the entrant immediately joins the set of active firms with
productivity type 1.2 A firm with an entry opportunity cannot delay its choice, so the payoff
to staying out of the industry is zero.
After the entry decisions, all active firms— including those that just entered the market—
decide simultaneously between survival and exit. Exit is irreversible but otherwise costless.
It allows firms to avoid future periods’ fixed production costs. Firms’ entry and exit decisions
maximize their expected profit streams discounted with a factor β < 1.
In the period’s final stage, Ct and the firms’ productivity types evolve. The demand index
evolves exogenously according to a nonnegative first-order Markov process bounded between
1

We leave this undefined if the Kt ’th element of Nt equals zero.
Since entrants’ productivity types evolve before their first period of production, we can use the distrif
bution of Kt+1
given Ktf = 1 to distribute new firms’ types nontrivially. That is, the assumption that all
entrants have Ktf = 1 is not overly restrictive.
2

4

ĉ and č. We denote the conditional distribution of Ct+1 with Q (c Ct ) ≡ Pr (Ct+1 ≤ c Ct ),
and the corresponding probability density function with q(· Ct ). Each firm’s idiosyncratic
productivity type follows an independent Markov
chain with a common
(ǩ × ǩ) transition


f
f
0
matrix Π. Its typical element is Πk,k0 ≡ Pr Kt+1 = k Kt = k . Following Ericson and
Pakes (1995), we assume that the idiosyncratic productivity types never regress:
Assumption 2 (No Productivity Regress). Π is upper diagonal.
f
We further assume that Kt+1
(weakly) stochastically increases with Ktf .

Assumption 3 (Monotone Productivity Dynamics). For all k 0 , k, l ∈ K such that k < l,




f
f
≥ k 0 Ktf = l .
Pr Kt+1
≥ k 0 Ktf = k ≤ Pr Kt+1
This assumption gives high technology firms no worse advancement opportunities than low
technology firms have.

2.2

Markov-Perfect Equilibrium

A Markov-perfect equilibrium is a subgame-perfect equilibrium in strategies that are only
contingent on payoff-relevant variables. For a potential participant f = (t, j) contemplating
entry these are Ct and the market structure Mtf just after f ’s possible entry. The latter is
period t’s initial market structure Nt augmented with j type 1 entrants: Mtf ≡ Nt + jι1 .
Denote the market structure after the period’s final entry with ME,t ≡ Nt + ι1 Jt . If firm f
is contemplating survival in period t, the payoff-relevant variables are this market structure,
the current demand index (Ct ), and its productivity type (Ktf ).
A Markov strategy for firm f is a pair (afE , afS ) of functions
afE : Zǩ? × [ĉ, č] −→ [0, 1]

and

afS : Zǩ? × [ĉ, č] × K −→ [0, 1].

This strategy’s entry rule afE assigns a probability of becoming active given an entry opportunity to each possible value of (Mtf , Ct ). Similarly, its exit rule afS assigns a probability of
being active in the next period given that the firm is currently active to each possible value
of its payoff-relevant state (ME,t , Ct , Ktf ). Since calendar time is not payoff-relevant, we hereafter drop the t subscript from all variables. A symmetric equilibrium is an equilibrium in
which all firms follow the same strategy (aE , aS ). In the remainder of the paper, we focus on
symmetric equilibria and drop the superscript f from the firms’ common strategy.
Throughout the paper, we will focus on equilibria in which a high productivity firm never
exits when a low productivity competitor survives. Such equilibria are natural, because a
high productivity firm earns strictly higher flow profit in each period than a low productivity
firm. Formally, we define a natural Markov-perfect equilibrium as follows:
5

Definition 1. A natural Markov-perfect equilibrium is a symmetric Markov-perfect equilibrium in a strategy (aE , aS ) such that for all k, l ∈ K such that k < l; mk ≥ 1, ml ≥ 1, and
aS (m, c, k) > 0 together imply that aS (m, c, l) = 1.
Cabral (1993) restricts attention to similar natural equilibria in a model with deterministic
productivity progression.
Firms’ expected discounted profits at each node of the game depend on that node’s
payoff-relevant state variables when they all use Markov strategies. The payoffs in two of
each period’s nodes are of particular interest, the post-entry value and the post-survival value.
The post-entry value vE (ME , C, K) equals the expected discounted profits of a type K firm
in a market with demand index C and market structure ME just after all entry decisions
have been sequentially realized. Since it gives the payoffs to a potential producer from
entering in each possible market structure that could arise from other players subsequent
entry decisions, it determines optimal entry choices. The post-survival value vS (MS , C, K)
equals the expected discounted profits of a type K firm facing demand index C and market
structure MS just after all survival decisions have been realized. It gives the payoffs to a
surviving firm in each possible market structure following firms’ simultaneous continuation
decisions, so it is central to the analysis of exit.
The value functions vE and vS satisfy
vE (mE , c, k) = aS (mE , c, k)E [vS (MS , c, k) ME = mE ]

(1)

vS (mS , c, k) = βE [π(N 0 , C 0 , K 0 ) + vE (ME0 , C 0 , K 0 ) MS = mS , C = c, K = k] .

(2)

and

Here and throughout, we denote the variable corresponding to X in the next period with X 0 .
The conditional expectation in (1) is computed given that the firm of interest continues, and
embodies the use of aS by all other active firms. In fact, the only nontrivial randomness it
embodies arises from firms’ possible use of mixed strategies. The conditional expectation in
(2) accounts for the use of aE by all potential participants with entry opportunities in the
next period as well as the exogenous evolutions of C and the firms’ productivity types.3
For (aE , aS ) to form a symmetric Markov-perfect equilibrium, it is necessary and sufficient
that no firm can gain from a one-shot deviation from (aE , aS ) (e.g. Fudenberg and Tirole,
1991, Theorem 4.2):
aE (m, c) ∈ arg max a {E [vE (ME , c, 1) M = m] − ϕ} and

(3)

a∈[0,1]

aS (mE , c, k) ∈ arg max a E [vS (MS , c, k) ME = mE ] .

(4)

a∈[0,1]

3

Section ?? of this paper’s online appendix presents the two conditional distributions underlying the
conditional expectations in (1) and (2) in detail.

6

The conditional expectations in (3) and (4) are computed like those in (1) and (2). For
example, E [vE (ME , c, 1) M = m] is the payoff, gross of the entry cost ϕ, that a potential
participant in state (m, c) expects from entering if all firms with entry opportunities later in
the period use the entry rule aE and the value of ending up as a type 1 firm in a market with
structure mE and c consumers equals vE (mE , c, 1).
Together, conditions (1)–(4) are necessary and sufficient for a strategy (aE , aS ) to form a
symmetric Markov-perfect equilibrium with payoffs vE and vS .
Before proceeding to examine the set of natural Markov-perfect equilibria, consider one
uninteresting source of equilibrium multiplicity. With an equilibrium in hand, change one
player’s action at a particular node of the game. If this change gives the same payoff to the
player in question and all other player’s equilibrium actions at that node remain optimal,
then this change forms a second equilibrium. In our model, this situation can arise when
the payoff to entry equals zero and when the payoff to survival as the only firm of your
type equals zero. To eliminate this difficulty, we require firms in such a situation to choose
inactivity.
Definition 2. A Markov strategy (aS , aE ) with corresponding payoff vE defaults to inactivity
if
• aS (m − mk × ιk + ιk , c, k) = 0 if vS (m, c, k) = 0
• aE (m, c) = 0 if vE (m, c, 1) = ϕ,
for all k ∈ K and all c.
The remainder of the paper restricts attention to equilibria with strategies that default
to inactivity, unless otherwise mentioned.4

3

Duopoly

It is helpful to begin the model’s analysis with one additional restriction: At most two firms
can be active at once. Throughout this section, we represent duopoly market structures with
ιk + ιl with k, l ∈ K ∪ {0}. The following lemma arises from this simplification.
Lemma 1 (Monotone Payoffs in the Heterogenous-Duopoly Model). In a natural Markovperfect equilibrium, for all c ∈ [ĉ, č] and k ∈ K, vE (2ιk , c, k) ≤ vE (ιk , c, k) and vS (2ιk , c, k) ≤
vS (ιk , c, k).
Proof. See Appendix A.
4

Note that we do not restrict the game’s strategy space to include only strategies that default to inactivity.

7

Figure 2: Reduced-form Representation of the Duopoly Continuation Game
Survive
Survive

vS (2, c)

Exit
vS (1, c)

vS (2, c)
0

0
0

Exit
vS (1, c)

0

Note: In each cell, the upper-left expression gives the row player’s payoff. Please see the text for further
details.

Lemma 1 states that a duopolist facing a rival of the same type always has a lower value
than it would have without the rival present. With its help, we develop the duopoly model’s
analysis in three stages. First, we examine the special case without heterogeneity, ǩ = 1.
This introduces the model’s most important moving parts without undue complication. We
then generalize this slightly in Section 3.2 by adding a second productivity type and walking
through the procedure for equilibrium calculation. Section Section 3.3 formalizes this procedure into an algorithm and then establishes equilibrium existence and uniqueness results.
Finally, Section 3.4 uses this algorithm for numerical analysis of the effects of technological
progress and demand uncertainty on industry dynamics. This illustration demonstrates that
the natural Markov-perfect equilibrium of this model can be easily computed.

3.1

One Productivity Type

When firms have identical productivity types by assumption, the restriction to a natural
equilibrium merely requires symmetry of players’ strategies. Here, we construct a symmetric
Markov-perfect equilibrium for this case in three steps. The type distribution is trivial, so
we write π(N, C, 1) as π(N, C) and make the analogous substitution for the value functions
throughout this example’s development.
Step 1: Calculation of vE (2, ·), vS (2, ·), and aE (2, ·) The equilibrium construction begins
with a characterization of the duopoly payoffs vE (2, ·) and vS (2, ·). In a Markov-perfect
equilibrium, the survival rule aS (2, c) satisfies (4): Given c, it is a Nash equilibrium of
the static simultaneous-move game with payoffs given by the expected continuation values.
Figure 2 gives the reduced-form representation of this game with the two pure strategies
“Survive” and “Exit”. The upper-left expression in each cell is the row player’s payoff. Both
firms receive the duopoly post-survival payoff vS (2, c) following joint survival. This payoff
8

adds the discounted duopoly flow payoff π(2, C 0 ) to the the discounted duopoly post-entry
payoff vE (2, C 0 ). Consequently, it satisfies a special case of Equation (2):
vS (2, c) = βE [π(2, C 0 ) + vE (2, C 0 ) C = c] .
A firm that survives while its rival exits earns the monopoly post-survival value vS (1, c).
Suppose that vS (2, c) > 0. Lemma 1 guarantees that vS (1, C) > 0, so in this case
“Survive” is a dominant strategy. If instead vS (2, c) < 0, then a symmetric equilibrium
strategy must put positive probability on “Exit”. That pure strategy’s payoff always equals
zero. Since vE (2, c) equals the symmetric equilibrium payoff to this game, these facts together
yield the following special case of Equation (1):
vE (2, c) = max {0, vS (2, c)}
o
n
= max 0, βE [π(2, C 0 ) + vE (2, C 0 ) C = c] .

(5)

The right-hand side defines a contraction mapping, so this necessary condition uniquely
determines vE (2, ·) and, using (2), vS (2, ·). This is the key technical insight that makes the
calculation of the model’s Markov-perfect industry dynamics simple. Although duopoly is not
an absorbing state for the industry, we can calculate the equilibrium duopoly payoffs without
knowledge of the firms’ payoffs in possible future market structures. This is because firms’
common post-entry value in a symmetric equilibrium equals zero unless joint continuation is
individually profitable.
With the duopoly post-entry value in hand, we can proceed to the problem of a potential
entrant facing a single incumbent. By Equation (3), this firm enters if vE (2, c) > ϕ and stays
out of the market if vE (2, c) ≤ ϕ. For all c,
aE (2, c) = I {vE (2, c) > ϕ} .
Note that strategy defaults to inactivity. When C has an atomless distribution, this strategy
almost surely prescribes the same action as any other entry strategy consistent with profit
maximization that does not default to inactivity. For this reason, our requirement that the
potential entrant default to inactivity has no substantial economic content.
Step 2: Calculation of vE (1, ·), vS (1, ·), aE (1, ·), and aS (1, ·) We proceed to consider the
monopoly payoffs, a potential entrant’s decision to enter an empty market, and an incumbent
monopolist’s survival decision. Because an incumbent monopolist choosing to survive will
earn vS (1, c), the post-entry value to a monopolist in (1) reduces to
vE (1, c) = max {0, vS (1, c)}
n
h
io
0
0
0
0
0
= max 0, βE π(1, C ) + aE (2, C )vE (2, C ) + (1 − aE (2, C )) vE (1, C ) C = c .
9

Given vE (2, ·) and aE (2, ·) from Step 1, the right-hand side defines a contraction mapping
that uniquely determines vE (1, ·) and, using Equation (2), vS (1, ·). It is not difficult to
demonstrate that the vE (1, c) and vS (1, c) so constructed always weakly exceed, respectively,
vE (2, c) and vS (2, c) from Step 1; so that the constructed value functions are consistent with
the requirements of Lemma 1.
Just as with a potential duopolist, we select the unique entry rule for a potential monopolist that defaults to inactivity. Since vE (2, c) ≤ vE (1, c), this is
aE (1, c) = I {vE (1, c) > ϕ} .
By (4), a monopolist chooses survival in demand states c such that vS (1, c) > 0 and exit
if vS (1, c) < 0. Our equilibrium construction uses the unique monopoly survival rule that
defaults to inactivity:
aS (1, c) = I {vS (1, c) > 0} .
Step 3: Calculate aS (2, ·) The first two steps have determined the only possible postentry and post-survival values, as well as an entry rule and a monopoly survival rule that
are consistent with them. This last step completes the equilibrium strategy’s construction
by determining a duopoly survival rule that satisfies (4).
As we noted above in Step 1, equilibrium requires aS (2, c) = 1 if vS (2, c) > 0. All that
remains undetermined is the survival rule when vS (2, c) ≤ 0. If profit maximization would
require even a monopolist to exit (i.e. vS (1, c) ≤ 0), then both duopolists exit for sure and
aS (2, c) = 0. If instead vS (1, c) > 0, then the reduced-form continuation game above has
no pure strategy equilibrium. In its unique mixed-strategy equilibrium, each firm’s survival
probability leaves its rival indifferent between exiting (and getting a payoff of zero for sure)
and surviving. That is, in demand states c such that vS (2, c) ≤ 0 and vS (1, c) > 0, the
indifference condition
aS (2, c)vS (2, c) + (1 − aS (2, c)) vS (1, c) = 0
uniquely determines aS (2, c).5
Illustration of the Constructed Equilibrium The entry and survival rules so calculated
form our equilibrium. Figure 3 plots the payoffs for a particular numerical example. In it
π(c, n) = c$(n) − κ with κ > 0 and $(2) < $(1). We also choose the stochastic process for
C so that its current value has no influence on the equilibrium probability of a firm entering
5

The mixed-strategy so derived prescribes that both firms exit for sure if vS (1, c) = 0, as the required by
our restriction to strategies that default to inactivity.

10

Figure 3: Equilibrium Payoffs in the Homogeneous Duopoly Example

Expected Monopoly Payoff vE (1, c)

Expected Duopoly Payoff vE (2, c)

ϕ

ĉ

c1

( A )(

c1
B

c2

c2

č

)(

C

)

or exiting in any future period. Specifically, C 0 = c with probability 1 − λ and equals a
draw from a uniform distribution over [ĉ, č] with the complementary probability. This and
the affine specification of π(c, n) together guarantee that vE (1, c) and vE (2, c) are piecewise
linear in c.
The lower (continuous) function in grey gives the duopoly post-entry value, vE (2, c). By
construction, this is identical to the expected discounted profits of a duopolist facing a rival
that will never exit first. It equals zero for c ≤ c2 . Thereafter it rises π(2)/(1 − β(1 − λ)) for
each extra consumer. For c > c2 , entry into a market with one incumbent is optimal.
The monopoly post-entry value vE (1, c) equals zero for demand levels c ≤ c1 , and it
increases π(1)/(1 − β(1 − λ)) with each extra consumer until reaching c2 . . When c > c2 , the
period’s entry stage always ends with two firms, so the equilibrium payoff to a firm that began
the period as a monopolist drops to the grey expected duopoly payoff. The disconnected line
segment above this gives the expected payoff to a firm that finds itself as a monopolist after
11

the period’s entry stage is complete.6 Given this value function, the equilibrium strategy for
a potential entrant facing an empty market is aE (1, c) = I {vE (1, c) > ϕ} ≡ I {c > c1 }, and
the analogous continuation rule for an incumbent monopolist is aS (1, c) = I {vE (1, c) > 0} =
I {vS (1, c) > 0} ≡ I {c > c1 }.
Duopolists’ common continuation strategy corresponds to the unique Nash equilibrium
of the game in Figure 2. Exit is a dominant strategy when c ∈ A, and survival is dominant
when c ∈ C. When c ∈ B the firms mix over survival and exit.

3.2

Two Productivity Types

We now proceed to adapt the basic ideas presented above to the case with productivity
heterogeneity. In the interest of expositional clarity, we denote the higher productivity type
with the intuitive H (instead of 2) and the lower type with L (instead of 1). We construct this
case’s unique natural Markov-perfect equilibrium in six steps. Just as before, these steps take
us through a finite partition of the state space. In each of the first five steps, we compute the
equilibrium payoffs in the states considered by finding the unique fixed point of a contraction
mapping. The results from the completed steps are used as inputs in the following steps.
Figure 4 illustrates this sequence of computations. The construction ends by specifying the
unique strategy that supports the equilibrium payoffs in the sixth step.7
Step 1: Calculation of vE (2ιH , ·, H) and vS (2ιH , ·, H) As depicted by the upper-left
panel in Figure 4, we start the equilibrium construction by considering a market populated
by two type H firms. The analysis in this step is a carbon copy of the first step of the previous
example. The simultaneous-move survival game between two type H firms is analogous to
the one in Figure 2, and Lemma 1 guarantees that “Survive” is the dominant strategy if
joint continuation gives both firms positive payoffs. Therefore, finding the fixed point of a
contraction mapping analogous to that in (1) yields vE (2ιH , ·, H). The continuation payoff
vS (2ιH , ·, H) immediately follows.
Step 2: Calculation of vE (ιL +ιH , ·, L), vS (ιL +ιH , ·, L), aE (ιL +ιH , ·), and aS (ιL +ιH , ·, L).
A type L firm that chooses to survive advances to H with probability ΠLH and remains
unchanged with probability ΠLL ≡ 1 − ΠLH . In a natural MPE, the survival of the type L
firm guarantees survival of any type H rival, so the continuation value vE (ιL + ιH , C, L) must
6

This would require some potential entrant to deviate from the equilibrium strategy.
The Atari 400 computer appearing in the illustration went on sale in November 1979 and had 8K of
RAM. It has more than enough computing power to calculate the unique equilibrium.
7

12

Figure 4: Equilibrium Computation for a Duopoly with Two Productivity Types
Number of type L firms

START

0
2

1
1

0
1

1
1

1
0

0
2

1
1

0
1

2
0

1
0

0
2

1
1

0
1

2
0

1
0

0
2

1
1

0
1

2
0

1
0

Number of type H firms

Value functions calculated

0
2

2
0

Market structure with one firm of each type

0
1

2
0

1
0

0
1

2
0

1
0

Value functions in hand

0
2

1
1

STOP

Note: There are five possible duopoly market structures. Each divided rectangle represents one of them, and
each collection of five rectangles displays the value functions being calculated (in red) and the value functions
already in hand (in blue) at one stage of the algorithm (which is Section 3.3’s Algorithm 1 with ǩ = 2).

satisfy
n

o
vE (ιL + ιH , c, L) = max 0, vS (ιL + ιH , c, L)
n
=β max 0, ΠLL E [π(ιL + ιH , C 0 , L) + vE (ιL + ιH , C 0 , L)|C = c]
o
+ ΠLH E [π(2ιH , C , H) + vE (2ιH , C , H)|C = c] .
0

0

Since vE (2ιH , ·, ιH ) is in hand from Step 1, this defines a contraction mapping in the desired
value function. With its fixed-point in hand, we can then easily compute vS (ιL + ιH , ·, L) and
aE (ιL + ιH , c) = I{vE (ιL + ιH , c, L) > ϕ},
aS (ιL + ιH , c, L) = I{vS (ιL + ιH , c, L) > 0}.
Step 3: Calculation of vE (ιH , ·, H), vS (ιH , ·, H), aS (ιH , ·, H), vE (ιL + ιH , ·, H), vS (ιL +
ιH , ·, H), and aS (ιL +ιH , ·, H). A market with a monopolist incumbent with type H attracts
an entrant next period if and only if aE (ιL + ιH , C 0 ) = 1, so vE (ιH , ·, H) and vE (ιH + ιL , ·, H)

13

together satisfy
n
o
vE (ιH , c, H) = max 0, vS (ιH , c, H)
n
=β max 0, E[π(ιH , C 0 , H) + aE (ιL + ιH , C 0 )vE (ιL + ιH , C 0 , H)

(6)

o
+ {1 − aE (ιL + ιH , C 0 )} vE (ιH , C 0 , H)|C = c] .
Step 2 determined aE (ιL +ιH , ·), so the only unknowns in (6) are the value functions. Since
a type H duopolist facing a type L rival becomes a monopolist if and only if aS (ιL +ιH , ·, L) =
0, these value functions must also satisfy
vE (ιL + ιH , c, ιH )
= aS (ιL + ιH , c, L)vS (ιL + ιH , c, ιH ) + {1 − aS (ιL + ιH , c, L)} vE (ιH , c, H)
n
= aS (ιL + ιH , c, L)β ΠLL E[π(ιH + ιL , C 0 , H) + vE (ιL + ιH , C 0 , H)|C = c]
o
0
0
+ ΠLH E[π(2ιH , C , H) + vE (2ιH , C , H)|C = c]

(7)

+ {1 − aS (ιL + ιH , c, L)} vE (ιH , c, H).
We have vE (2ιH , ·, H) from Step 1 and aS (ιL + ιH , ·, L) from Step 2, so together, (6) and
(7) determine vE (ιH , ·, H) and vE (ιL + ιH , ·, H). Obtaining vS (ιH , ·, H) and vS (ιL + ιH , ·, H)
from these is straightforward. Since we seek a natural equilibrium, the survival strategies of
interest must satisfy
aS (ιH , c, H) = aS (ιL + ιH , c, H) = I{vS (ιH , c, H) > 0}.
Step 4: Calculation of vE (2ιL , ·, L), aE (2ιL , ·), and vS (2ιL , ·, L). Next, we consider a
duopoly market with two type L firms. If both firms choose survival, then their idiosyncratic
shocks could change the market structure to either of the duopoly structures considered in
Steps 1-3 or leave it unchanged. Lemma 1 guarantees that if the value of simultaneous
survival to either incumbent is positive, then joint continuation is the only Nash equilibrium
outcome of their survival game. Therefore, vE (2ιL , ·, L) satisfies
n
o
vE (2ιL , c, L) = max 0, vS (2ιL , c, L)
n
=β max 0, Π2LL E [π(2ιL , C 0 , L) + vE (2ιL , C 0 , L)|C = c]
+ ΠLL ΠLH E [π(ιL + ιH , C 0 , L) + vE (ιL + ιH , C 0 , L)|C = c]
+ ΠLH ΠLL E [π(ιL + ιH , C 0 , H) + vE (ιL + ιH , C 0 , H)|C = c]
o
+ Π2LH E [π(2ιH , C 0 , H) + vE (2ιH , C 0 , H)|C = c] .

14

The only unknown on its righthand side is vE (2ιL , ·, L), so we can use this Bellman
equation to calculate it. With this in hand, we construct the rule for entry into a market
with one type L incumbent as
aE (2ιL , c) = I{vE (2ιL , c, L) > ϕ}.
Moreover, it is straightforward to determine vS (2ιL , ·, L).
Step 5: Calculation of vE (ιL , ·, L), vS (ιL , ·, L), aE (ιL , ·), and aS (ιL , ·, L). If a type L
monopolist chooses survival, then one of four market structures will prevail in the next period,
depending on the incumbent’s idiosyncratic shock and on the decision of a potential entrant:
n
o
vE (ιL , c, L) = max 0, vS (ιL , c, L)
n
h
= max 0, ΠLL E π(ιL , C 0 , L) + aE (2ιL , C 0 )vE (2ιL , C 0 , L)
0

0

i

+ {1 − aE (2ιL , C )} vE (ιL , C , L)|C = c
h
+ ΠLH E π(ιH , C 0 , H) + aE (ιL + ιH , C 0 )vE (ιL + ιH , C 0 , H)
+ {1 − aE (ιL + ιH , C 0 )} vE (ιH , C 0 , H)|C = c

(8)

io

.

Given the quantities calculated in Steps 1–4, the righthand side of (8) defines a contraction
mapping with vE (ιL , ·, L) as its fixed point. With this, it is straightforward to compute
vS (ιL , ·, L), which gives the survival rule

aS (ιL , c, L) = I{vS (ιL , c, L) > 0}.
Since vE (2ιL , c, L) ≤ vE (ιL , c, L), the entry rule for a potential monopolist can be written
as

aE (ιL , c) = I {vE (ιL , c) > ϕ}
Step 6: Calculation of aS (2ιH , ·, H) and aS (2ιL , ·, L). Steps 1–5 have determined all
equilibrium continuation values, entry strategies, and survival strategies for firms facing no
identical rival. All that remains is to determine the exit strategies for duopolies of identical
firms. Their construction parallels that from the case with homogeneous firms: Unless either
survival or exit is a dominant strategy, both firms mix between the two pure actions to leave

15

each other indifferent between them.


 1
vS (ιL ,c,L)
aS (2ιL , c, L) =
vS (ιL ,c,L)−vS (2ιL ,c,L)


0


 1
vS (ιH ,c,H)
aS (2ιH , c, H) =
v
(ι
,c,H)−v
S
H
S (2ιH ,c,H)


0

if vS (2ιL , c, L) > 0,
if vS (2ιL , c, L) ≤ 0 and vS (ιL , c, L) > 0
otherwise.
if vS (2ιH , c, H) > 0,
if vS (2ιH , c, H) ≤ 0 and vS (ιH , c, H) > 0
otherwise.

This concludes the equilibrium construction. Although adding productivity heterogeneity
increased the number of steps required, calculating the fixed point of a contraction mapping
on a low-dimensional function space remains the most computationally intensive required
task.

3.3

Equilibrium Existence, Uniqueness, and Computation

We next extend the six-step calculation of duopoly equilibrium with ǩ = 2 to allow for arbitrary ǩ.The resulting algorithm consists of two procedures, which we present as flow charts
in Procedures 1 and 2. The first computes all payoffs, survival strategies for duopolists facing
strictly higher productivity types, and strategy for a potential entrant facing an incumbent.
The second procedure calculates the survival strategies for duopoly incumbents with weakly
higher productivity types and the strategy for a potential entrant facing an empty market.
In Procedure 1’s flow chart, h indexes the productivity type for the weakly better firm,
and l for the weakly worse firm. In the course of its execution, h decreases from ǩ to 1. For
each level of h, l decreases from h to 1. For any pair of (h, l); the post-entry value wE to the
type l firm that faces a type h rival is computed as the fixed point of Th,l . This functional
operator is defined by the recursive condition for wE (ιl + ιh , ·, l). The type l firm has weakly
lower productivity type and rationally expects its rival to remain whenever it continues with
positive probability, so this firm’s payoffs only depend on future states in which both firms
survive. That is, evaluating Th,l only requires the continuation value being calculated and
on wE (ιi + ιj , ·, j) for all (i, j) 6= (h, l) such that i ≥ h, j ≥ l. Since Procedure 1 proceeds
in descending order of (h, l), these post-entry values are in hand for the computation of
wE (ιl + ιh , ·, l).

16

No

h = 1?

No
START

h ←
h−1

l = 1?

{wS (ιh + ιk , ·, h); 0 ≤ k < h} ← 2nd term of Th (wE )
αE (ιh + ι1 , ·) ← I {wE (ιh + ι1 , ·, 1) > ϕ}

No

fixed point of Th,l
l←h

l < h?

wS (ιh + ιl , ·, l) ←

Yes

αS (ιh + ιl , ·, l) ←
I {wE (ιh + ιl , ·, l) > 0}

2nd term of Th,l (wE )

17
Required Functional Operators

X
Πhi Πlj π(ιi + ιj , C 0 , j) +
Th,l (f )(c) = max 0, βE 

)

(

i,j

(

X

0

0

Πhi Πlj wE (ιi + ιj , C , j) + Πhh Πll f (C ) C = c

(i,j)6=(h,l)

"

!

Th (f )(c, k) = max 0, βE αS (ιh + ιk , c, k)

X

0

Πhi Πkj π(ιi + ιj , C , i) +

i,j

+ {1 − αS (ιh + ιk , c, k)}

X

XX

0

Πhh Πkj f (C , j) +

j

X

i>h

0

Πhi Πkj wE (ιi + ιj , C , i)

j


Πhi π(ιi , C 0 , i) + Πhh 1 − αE (ιh + ι1 , C 0 ) f (C 0 , 0)

i

+

X

+

X


Πhi 1 − αE (ιi + ι1 , C 0 ) wE (ιi , C 0 , i) + Πhh αE (ιh + ι1 , C 0 )f (C 0 , 1)

i>h

!
0

STOP

{wE (ιh + ιk , ·, h); 0 ≤ k < h} ← fixed point of Th

Yes

l ←l−1

wE (ιh + ιl , ·, l) ←
h ← ǩ

Return wE , wS ,
αE , and αS (ιh +
ιl , ·, l) for l < h.

Yes

0

Πhi αE (ιi + ι1 , C )wE (ιi + ι1 , C , i)

#)
C=c

, αS (ιh + ι0 , ·, 0) ≡ 0, Π00 ≡ 1

i>h

Procedure 1: Initial Equilibrium Calculations for the Heterogeneous Duopoly Model

When l reaches 1, the next step is to compute simultaneously the monopoly payoff for a
type h firm and the duopoly payoff for a type h firm facing a type k (for all k < h) rival as the
fixed point of Th . Evaluating its right-hand side requires the value function being computed,
the entry rule of a potential entrant facing an incumbent with productivity type no less than
h ,the corresponding post-entry values for the incumbent, the survival strategies for rivals
with types k < h, and the corresponding post-survival values. Again, previous computations
using higher values of h, l determined these before this computation begins.
Procedure 2 complements Procedure 1 by determining the entry strategy for a potential
monopolist; and the survival strategy for a firm with weakly better productivity type. All but
one of these strategies are pure and refelct the values of entry and continuation as expcted.
The survival strategy is mixed when both firms have the same type, the payoff to joint
continuation is negative, and the payoff isolated continuation is positive. By construction,
the resulting probability of survival lies in (0, 1].
Algorithm 1 (Duopoly Equilibrium Calculation). Compute a candidate equilibrium strategy
(αS , αE ) and payoffs wS and wE in two steps:
1. Use Procedure 1 to compute wE , wS , αS (ιh + ιl , c, l) and αE (ιh + ι1 , c) for all h, l ∈
K, l < h and c ∈ [ĉ, č].
2. Use Procedure 2 to compute αE (ι1 , c) for all c ∈ [ĉ, č] and to compute αS (ιh + ιl , c, h)
for all h ∈ K, l ∈ {0, . . . , h}, and c ∈ [ĉ, č];
We can use Lemma 1 to prove that the constructed equilibrium is unique among all
equilibria that default to inactivity.
Proposition 1 (Equilibrium in Heterogeneous Duopoly Model). There exists a unique natural Markov-perfect equilibrium. Algorithm 1 computes its payoffs and strategy. The equilibrium payoffs vS = wS and vE = wE . The equilibrium strategy (aS , aE ) = (αS , αE ).
Proof. See Appendix A.

3.4

Application

We apply our heterogenous-duopoly model to the welfare analysis of an R&D race game.
Consider a market for some new good. In period t, Ct consumers populate the market. All of
these consumers have the same utility function, which is quadratic in the quantity of the new
good consumed. Consequently, total demand for the new good at time t and price p equals
Ct (a − p)/b, for some parameters a, b > 0. A firm supplying q units of this good receives a
surplus Ct pq.
18

START

Specify c ∈ [ĉ, č], h ∈ K, and l ∈ {0, 1, . . . , h}

Get wE and wS from Procedure 1

h>l?

Yes

αS (ιh + ιl , c, h) ←
I {wS (ιh + ιl , c, h) > 0}

No

αS (2ιh , c, h) ← 1

Yes

wS (2ιh , c, h)
> 0?

No

αS (2ιh , c, h) ← 0

Yes

h=1?

No

Yes

wS (ιh , c, h)
= 0?

αE (ι1 , c) ←
I {wE (ι1 , c, 1) > ϕ}

No
wS (ιh , c, h)
αS (2ιh , c, h) ←
.
wS (ιh , c, h) − wS (2ιh , c, h)

(9)

STOP

Procedure 2: Calculation of Candidate Survival Rule for the Heterogeneous Duopoly Model

19

Firms must invent the good before they can supply it to the market. This requires that
they enter the market, incurring an entry cost ϕ, and subsequently invest in R&D, at a fixed
cost κ(k). There are several milestone stages in the invention process, marked by 1, 2, . . . , ǩ.
New entrants start in stage 1 and, as long as they stay in the market and pay the fixed
cost κ(k) according to their current stage k, progress through the successive R& D stages
according to a Markov chain with transition matrix Π. Once a firm reaches the final stage
ǩ, it has invented the product and can start selling it in the market. The fixed cost κ(ǩ) still
needs to be paid to produce the good.8 An active firm may exit the market in any stage of
the R&D race to avoid paying future fixed costs.
We assume that at most two firms are active in the market at any give time. If only one
firm is active in stage ǩ, it sells the good at the monopoly price. If two firms are selling
the good, they set symmetric quantities to maximize q o p + λq r p, where q o and q r denote the
quantities set by the firm and its rival, respectively, and λ indexes the level of collusion. If
λ = 0, these two firms are Cournot competitors. At higher values of λ, they collude more.
If λ = 1, then they operate as if they are branches of a monopoly firm that split their joint
monopoly revenues evenly.
This game embodies Fershtman and Pakes’ (2000) key “semi-collusion” assumption that
firms may collude in setting quantities (or prices) but not when choosing R&D investment.
Unlike Fershtman and Pakes, we take the level of collusion as exogenously given and ignore the
intensive margin of the firms’ strategic R&D investments. This focus on the (entry and exit)
decisions to participate in the R&D race allow us to apply the heterogenous-duopoly model
to analyze industry dynamics and welfare under different levels of collusion. We find that the
model is sufficiently rich to replicate one of Fershtman and Pakes’ main findings: Consumers
may benefit from collusion, unlike in static models that take the industry structure as given.
Intuitively, the direct negative effect of collusion on consumer welfare through weakened
competition in the product market, well known from static models, is counteracted by a
positive effect on R&D participation that increases product availability and product market
competition.
To obtain this result, we first compute the model’s unique natural Markov-perfect equilibrium for each value of λ between 0 and 1, with a 0.01 increment. Throughout, we specify
Q(·|C) to approximate a random walk in the logarithm of C with innovation variance 0.32 ,
reflected off of the state space’s upper and lower boundaries, ln ĉ = −1.5 and ln č = 1.5. Also,
we specify ǩ = 4, β = 0.95, κ(k) = 20 for all k, ϕ = 470, demand parameters a = 20 and
b = 2, and the Markov transition matrix Π for the R&D stages so that firms either progress
one stage or remain put: Πk,k = Πk,k+1 = 0.5 for all k < ǩ and Πǩ,ǩ = 1.
8

Alternatively, we can let the fixed cost decline with k. This only requires a minor adjustment of the
model.

20

Subsequently, for each value of λ, we use the equilibrium strategy to simulate the market’s
evolution over 100 periods, starting from a fixed c0 = 2.718, drawn from the demand process’s
ergodic distribution, and an empty market. We repeat the simulation 10,000 times, drawing
new demand and type transitions in each simulation, but using the same random draws across
the different values of λ. To analyze the impact of collusion on welfare, we compute, for each
level of collusion λ, the discounted sum F P (λ) of all firms’ revenues net of all firms’ fixed
costs and entry costs over the 100 periods, and the discounted sum CS(λ) of the consumer
surplus over the 100 periods, both averaged over the 10,000 simulation runs. We assume that
consumers have the same discount factor as firms. The total surplus T S(λ) ≡ F P (λ)+CS(λ).

Consumer Surplus
0.7

0.8

0.6

0.7

0.4

1

0

0.5
λ

1

0.5

0.5
1
λ
Average Number of
Periods before Success
6.5
#Periods

#Firms

0.5
1
λ
Average Number of
Active Firms
2

1.5

0.6

0.4

0

1.2
TS(λ)/TS(0)

0.5

Total Surplus

Firm Profit
FP(λ)/TS(0)

CS(λ)/TS(0)

Figure 5: Welfare Analysis for Various Levels of Collusion

0

1.1
1
0.9

0

0.5
λ

1

6
5.5
5
4.5

0

0.5
λ

1

The upper-left and upper-middle panels of Figure 5 show CS(λ) and F P (λ) for each value
of λ, as a proportion of the competitive market’s total surplus T S(0). First, if λ increases
from 0, CS(λ) gradually increases and F P (λ) gradually decreases. Then, CS(λ) jumps up
and F P (λ) jumps down. At higher levels of collusion, increases in λ decrease the consumer
surplus and increase firms’ profits.
Clearly, for low values of λ, the positive effect of increasing collusion on R&D investment
dominates its direct weakening effect on product market competition. Figure 5’s bottom-left
panel sheds further light on this. It plots the number of active firms for each λ, averaged
over the 100 periods and all the simulation runs. We observe a gradual increase and then
21

an upward jump in the number of firms, paralleling the increase and jump in the consumer
surplus. If λ is low; that is, with little or no collusion; no entrant facing a monopoly market
can recover the sunk cost of entry, even when demand is at its highest level. Therefore,
markets with little collusion are often monopoly markets. If λ increases, firms expect higher
payoffs from a duopoly product market, and are more willing to participate in the R&D race,
even if one firm is already in this race. The value of λ at which the number of firms and
welfare jump is the level of collusion above which two firms enter immediately, in the initial
demand state c0 .
This increase in the number of firms improves the consumer surplus in two ways. First,
it improves product availability. Specifically, in this example, on average the first product
reaches the market faster with higher levels of collusion (see Figure 5’s bottom-middle panel).
Second, it mitigates the anticompetitive effects of collusion, by ensuring that consumers are
more often charged the (collusive) duopoly price, which, for all λ < 1, is lower than the
monopoly price. At low levels of λ, the consumer welfare enhancing effects dominate the
direct negative effects of increased collusion.
In contrast, as is clear from Figure 5’s bottom panels, at higher levels of collusion, the
market is often served by the maximum number of two firms. Consequently, further increases
in λ have only small effects on the number of firms serving the market and the speed at which
the good becomes available. Therefore, at higher levels of collusion, the direct effects of
collusion dominate, and the consumer surplus gradually falls if λ increases. Nevertheless, the
benefits from earlier consumption under full collusion (λ = 1) ensure that CS(1) > CS(0).
The variation of F P (λ) with λ mirrors the variation of CS(λ). If λ crosses the level at
which two firms immediately enter the market, instead of one, the total fixed cost incurred
is doubled, but the total revenue is not. Consequently, F P (λ) jumps down. For similar
reasons, F P (λ) falls gradually if λ increases at lower levels of collusion. In contrast, at
higher levels of collusion, the market is usually a duopoly and the market structure does not
change much with increases in λ. Consequently, the positive effects of such increases on the
collusive duopoly price dominate, and F P (λ) increases. Finally, F P (1) < F P (0), because
of scale savings: The monopoly price is usually charged at either collusive extreme, but two
firms, instead of one, often incur fixed costs under full collusion.
Figure 5’s upper-right panel plots the total surplus as a fraction of the competitive market’s total surplus. At low levels of collusion, an increase in λ increases T S(λ). In particular,
the upward jump in the number of firms leads to an upward jump in the total surplus. At
these levels of collusion, the positive effects of increased product market competition and
earlier consumption on consumer welfare dominate its negative effects on firms through price
decreases and fixed cost increases. At higher levels of collusion, the total surplus falls with
increases in λ, because R&D activity is hardly affected and the negative welfare effects of

22

collusion familiar from static models dominate.
In this specific example, as in static models that take the market structure as given,
full collusion in the product markets lowers welfare below that in a competitive market:
T S(1) < T S(0). However, unlike in such static models, the competitive market is often
served by only one firm and monopolistic pricing is common under both levels of collusion.
Consequently, the result that full collusion lowers total welfare cannot be explained by the
usual negative welfare effects of collusive pricing. Instead, it is due to the waste of fixed
costs caused by excess entry of producers, which is not offset by the gains from earlier
consumption.9
It is worth stressing that these results are obtained at a very low computational cost.
For any particular value of λ, with 301 grid points for C and the parameter values of this
section’s experiment, we can solve the model within one second using Matlab on a PC.
Even with β = 0.995 (monthly data) and ǩ = 10, which implies a state space with over
33,000 points, we can solve the model in about 5–30 seconds on a PC.10 This feature of our
framework makes it a very useful complement to existing richer, but computationally more
forbidding, frameworks for the analysis of industry dynamics. For example, Fershtman and
Pakes’ framework allows for a more detailed study of collusion dynamics by modeling, among
other things, the intensive margin of R&D investment and endogenizing collusion. However,
their framework’s comparative richness comes at a substantial computational cost: It makes
the replication of their results across different parameter values very hard. In contrast, our
framework allows us to quickly examine the welfare implications of collusion for a wide range
of parameter values.

4

The General Model

We now turn to the general model, with arbitrary finite m̌ and ǩ. The central difficulty of
the equilibrium analysis is that the equilibrium payoff function does not necessarily satisfy a
monotonicity property analogous to the ones in Lemmas 1. In Section 4.1, we first analyze
a type of equilibrium in which the payoffs still retain the monotonicity property: Adding an
active firm into the industry weakly decreases other firms’ payoffs. We can straightforwardly
extend Algorithm 1 and use a sequence of contraction mappings to efficiently compute such an
equilibrium, if it does exist. This monotonicity property is the key to establish the essential
9

Obviously, this result can be reversed if consumers are impatient and/or have much larger weight in the
total surplus than producers do.
10
We use value function iteration to compute the fixed points of the contraction mappings, which simplifies
our code, but results in a (slow) linear convergence rate in β. To cope with this issue, one can turn to more
sophisticated approaches (see Judd, 1998, for a brief survey). For example, Ferris, Judd, and Schmedders’s
(2007) Newton-based method ensures global convergence with a quadratic convergence rate.

23

uniqueness of this type of equilibrium. However, since the monotonicity property does not
always hold in the general model, this type of equilibrium may not exist. In Section 4.2,
we discuss a simple example in which the monotonicity of equilibrium payoffs is violated
and multiple equilibria emerge. In one class of those equilibria, if firms were allowed to
renegotiate, they could strictly improve their payoffs by playing another equilibrium. We
continue to focus on the type of equilibria that are renegotiation-proof and establish their
existence. An extension of our algorithm can compute all such equilibria, if C has a discrete
distribution.

4.1

Payoff-Monotone Equilibrium

We define an equilibrium to be payoff-monotone if the equilibrium payoffs satisfy conditions
analogous to the ones in Lemma 1.
Definition 3. A Markov-perfect equilibrium is payoff-monotone if its equilibrium payoff functions satisfies vS (m, c, k) ≥ vS (m + ιk , c, k) and vE (m, c, k) ≥ vE (m + ιk , c, k) for all (m, c, k).
We showed in Section 3 that duopoly firms of the same type choose to continue if continuation guarantees a positive payoff, because the heterogenous duopoly model’s equilibrium
payoffs satisfy Lemma 1. This property allows us to construct a sequence of contraction mappings in Algorithm 1 to compute the unique natural Markov-perfect equilibrium. Similarly, in
the general model, suppose that, for some parameter values, there exists a payoff-monotone
natural Markov-perfect equilibrium. Then, if continuation renders the payoff to all firms of
the same type positive, continuation is the dominant strategy for these firms. Following the
argument leading to condition (5) in Section 3.1, we can establish similar necessary conditions
on equilibrium payoffs. For instance, in the market with m̌ type ǩ firms, the payoff-monotone
equilibrium payoff vE (m̌ιǩ , c, ǩ) necessarily satisfies
vE (m̌ιǩ , c, ǩ) = max{0, βE[π(m̌ιǩ , c0 , ǩ) + vE (m̌ιǩ , c0 , ǩ)|C = c]}.

(10)

The right hand side of (10) defines a Bellman operator that uniquely determines vE (m̌ιǩ , ·, ǩ).
Note that the heterogeneous duopoly model and the general model only differ in the
number of firms and share essentially the same dynamic specification. Therefore, Algorithm 1
can be naturally extended to solve for the payoff-monotone natural equilibrium, by computed
the fixed points of a sequence of contraction mappings. Similarly to Algorithm 1, we partition
the state space, order the parts, and compute the equilibrium in a corresponding sequence
of steps. Each step covers the computation on a single part of the state space. We order the
steps so that all results that are needed in later steps are passed on from earlier steps.
The partition and its order are defined using an oriental lexicographic order.
24

Definition 4. Oriental lexicographical superiority (OLS)  is a relation over Rn . For any
pair of vectors x, y ∈ Rn , x  y if xn > yn , or (xn = yn and xn−1 > yn−1 ), or , . . . , or (xn =
yn and xn−1 = yn−1 and . . . and x1 > y1 ).
We use the phrase “oriental” because the vectors x, y are read from right to left when
being compared, as in Arabic and Hebrew. In the previous sections, we have implicitly used
an ordering based on OLS; the equilibrium payoff for an OLS market structure is always
computed before the payoffs in any state it is superior to. For example, in Section 3.1’s
one productivity type example,  is equivalent to > on R and the payoff to a duopolist
is computed first, followed by the payoff to a monopolist. In Section 3.2, the sequence of
market structures considered was {2ιH , ιH + ιL , ιH , 2ιL , ιL }. Thus, we partitioned the state
space into five parts and ordered them in decreasing OLS to compute the equilibrium payoffs
and strategy. Furthermore, this ordering extends to Algorithm 1 as well; the index pair (h, l)
in Procedure 1 is decreasing in OLS. This ordering ensures that equilibrium payoffs and
entry/survival rules necessary for computation in later steps are calculated in earlier steps.
We construct the algorithm for the general model following the same ordering. For any

ǩ)!
ǩ
− 1 possible non-empty markets. First, we partition
(m̌, ǩ) pair, there are m̌+
− 1 = (m̌+
ǩ
ǩ!m̌!
ǩ)!
− 1 parts, with each step of the algorithm computing the payoff on
the state space into (m̌+
ǩ!m̌!
one of these parts. In step i, to see what the states in this part are, suppose the i-th ranked
market structure in the OLS sequence is mi . Let k i = min{k ∈ K; mik > 0} be the lowest
type of active firm in mi and let a set Mmi collect all the market structures that share the
same number of type-k i , k i + 1, . . . , ǩ firms as mi . The part of the state space considered in
this step is then {(m, c, k i ); m ∈ Mmi , c ∈ [ĉ, č]}. In other words, in the i-th step, we compute
a type-k i firm’s payoff in every market structure in Mmi for all c. Since this part of the state
space are constructed from mi , we say that it is indexed by mi , and hence name mi as the
indexing market structure.
The first step of the algorithm is indexed by the most superior market structure, m̌ιǩ .
Then, we proceed the algorithm and sequentially determine the payoffs and strategy for
market structures in the order of decreasing OLS.

25

Algorithm 2 (Calculation of a Candidate Equilibrium for the General Model).
START

m̌ ← max{n ∈ N; π(ιǩ + (n − 1)ι1 , č, ǩ) +
αS (·) ← 1,

αE (·) ← 0,

βπ(ιǩ , č, ǩ)
> 0}
1−β

wE (·) ← 0

Order all elements from the set {m ∈ Zǩ ; 1 ≤ |m| ≤
m̌} by . Index the obtained sequence by m1 , m2 , . . ..

i←

(m̌+ǩ)!
ǩ!m̌!

−1

k i ← min{k ∈ K; mik > 0}


i −1
i −1
kX
kX


i
i
Mmi ←
mk ≤ m̌
m +
ιk mk ; |m | +


k=1
k=1

HiS ← (m, c, k); m ∈ Mmi , k = k i
For all HSi ∈
(T f )(HSi ) =
)
and wS (HSi

g(HSi0 ) =


HiS , compute wE (HSi ) as the fixed point of
max {0, βE [π(N 0 , C 0 , K 0 ) + g(HSi0 ) HSi ]} ,
= βE [π(N 0 , C 0 , K 0 ) + g(HSi0 ) HSi ] , with
if HSi0 ∈ HiS
f (HSi0 )
ǩ)!
S S (m̌+
−1
. . . HS ǩ!m̌!
wE (HSi0 ) if HSi0 ∈ Hi+1
S

miki = 1?
or k i = 1?

No

i ← i−1

Yes
Compute survival/entry rule.

i = 1?

Yes
STOP

26

No

In Algorithm 2, when computing the candidate post-entry payoff wE as the fixed point of
the Bellman equation, the expectation relies on the relevant parts of other firms strategy11 .
Because of the algorithm’s OLS ordering, for the firms with lower productivity types than
the firm of interest and the potential entrants, these values have been computed in previous
steps. The survival rules for firms with productivity types at least as good as the firm of
interest are set to continuation. Also, the OLS ordering of the algorithm helps to ensure
that the current states that the firm of interest is facing only evolves to states that have
been covered in previous computation, providing that this firm continues. Hence, all relevant
values of future post-entry payoff have been computed in previous steps. Then, T is always
a contraction mapping with unique fixed point wE (HS ).
Procedure 3 is devoted to computing the survival/entry strategy. In this procedure, when
firms are randomizing between survival and exit, the mixing probability is chosen to be one
of possible probabilities that solves the indifference condition (11). If it is not profitable to
unilaterally deviate from exit to survival given all other firms of the same type opt for exit,
the mixing probability can also be set to 0.
Note that Algorithm 2 does not require wE to be monotone as in Definition 3. After computing wE with Algorithm 2, we can check whether it satisfies this monotonicity condition. If
it does, we can show that the candidate equilibrium strategy (αS , αE ) is unique. We can also
verify that (αS , αE ) forms a natural Markov-perfect equilibrium. Since the Bellman equation for wE defines the necessary condition for any payoff-monotone natural Markov-perfect
equilibrium payoff, if one such equilibrium exists, not only we are able to compute it using
Algorithm 2, but also we can prove its essential uniqueness.
Proposition 2 (Payoff-Monotone Equilibrium in the General Model). If there exists a payoffmonotone natural Markov-perfect equilibrium, it is the unique such equilibrium and Algorithm
2 computes it. The post-entry equilibrium payoff function is wE and the equilibrium strategy
is (αS , αE ).
Proof. See Appendix B.

4.2

Renegotiation-Proof Equilibrium

Proposition 2 implies that a payoff-monotone natural Markov-perfect equilibrium does not
exist if wE is not monotone as in Definition 3.
In Appendix C, we present a simple example in which equilibrium payoffs are not monotone and there are multiple natural Markov-perfect equilibria. In this example, we consider
an industry with at most three active firms. We assume that firms can be type H or type
11

Computing the market structure transition matrix conditional on firms’ strategy is conceptually straightforward, but practically involved. We describe the details in Section ?? of the online appendix.

27

mi , k i

Specify c ∈ [ĉ, č] and m ∈ Mmi +jιki , ∀0 ≤ j ≤ m̌ − |mi |

mk i = 1 ?

Yes

αS (m, c, k i ) ←
I[wE (m, c, k i ) > 0]

No
wE (m, c, k i )
> 0?

Yes

αS (m, c, k i ) ← 1

No
Find all p’s ∈ [0, 1) satisfying,


mk i − 1
(1−p)mki −1−j pj
wS (m−(mki −1−j)ιki , c, k i ) = 0. (11)
j

mki −1

X
j=0

No

wS (mi , c, k i )
> 0?

αS (m, c, k i ) ← 0
or one of the p’s

αE (m, c) ← I{w(m +
jι1 , c, 1) − ϕ >
0, ∀0 ≤ j ≤ m̌ − |m|}

Yes

Yes

αS (m, c, k i ) ←
one of the p’s

ki = 1 ?

No
CONTINUE

Procedure 3: Calculation of Candidate Entry/Survival Rule for the General Model

28

L. For two type H duopoly firms contemplating survival, we create a situation that if these
two firms jointly continue to next period, any type L potential entrant will never find it
profitable to enter this market. This way, the type H duopolists deter any future entry by
joint survival and enjoy a high duopoly surplus forever. Otherwise, if one of the firms exits,
then two type-L firms will enter the market and remain active onwards. The survived type-H
firm will only receive a low triopoly surplus thereafter. Connecting this example to the static
survival game depicted in Figure 2, we construct the payoff matrix such that, for some c,
the post-survival value satisfies vS (2ιH , c, H) > 0 > vS (ιH , c, H). Therefore, although “Survive, Survive” remains an equilibrium in this static game, “Exit, Exit” emerges as another
equilibrium. Also, there could be equilibria involving mixed strategies. Indeed, we show in
Appendix C that we do have three possible equilibrium actions at this particular point of the
game tree. Namely, to survive for sure, to exit for sure, and to survive with some probability.
We further demonstrate that when three firms are randomizing between survival and exit
because joint survival is not profitable, the mixing probability can be multiple.
We distinguish two sources of equilibrium multiplicity using this example. One comes
from the incumbents’ failure to jointly continue if this is profitable. If the two type-H
firms can coordinate on continuation, they can strictly improve their equilibrium payoffs.
Since these two firms repeatedly interact, it seems reasonable to assume that they are able
to “renegotiate” to joint continuation whenever this is profitable. Henceforth, we restrict
attention to equilibria with the desirable property that firms cannot improve their payoffs by
one-shot change of action. We call this property renegotiation-proofness.
Definition 5. A natural Markov-perfect equilibrium is (one-shot) renegotiation-proof if, for
any (m, c) pair, no one-shot agreement satisfying the following properties can be negotiated:
• all firms in the agreement change their survival actions once;
• the agreement is self-enforcing, so no firm in the agreement has incentive to unilaterally
change the agreed action;
• if one type k firm is in the agreement, all type k firms are; and
• the payoffs to all firms in the agreement are strictly improved.
In any equilibrium, a firm earns positive payoffs only when continuing for sure. Therefore,
if all firms of a certain type can strictly improve their payoff by changing their actions, it must
be the case that (i) the actions must be changed from exiting with non-negative probability to
surviving with probability one (ii) the actions of joint continuation must give all firms in the
agreement positive payoff. Therefore, this refinement has bite only when all incumbents of
certain type(s) could coordinate on sure joint continuation and earn positive payoffs, but will
29

not unilaterally continue if others do not. Note that in the duopoly model, Lemma 1 ensures
that both incumbents of the same type continue for sure if joint continuation renders payoff
positive. Therefore, no further improvement is possible via renegotiation. Consequently, the
natural equilibrium in Section 3 is renegotiation-proof. Since the monotonicity in Definition
3 essentially functions in the same way as the monotonicity in Lemma1, the payoff-monotone
equilibrium in the general model is also renegotiation-proof.
Recall that in Algorithm 2, αS (m, c, k) is set to its initial value of one when computing
wE (m, c, k). This implies that all type-k firms are “forced” to jointly continue if positive
payoff is expected. Therefore, the Bellman equation for wE is a necessary condition on wE
for a renegotiation-proof natural Markov-perfect equilibrium. When verifying that (αS , αE )
forms a natural equilibrium, we also verify that it is a renegotiation-proof one. We can
further show that Algorithm 2 always delivers some (αS , αE ) as its outcome, which proves
the existence of a renegotiation-proof natural Markov-perfect equilibrium.
Proposition 3 (Renegotiation-proof Equilibrium in the General Model). Algorithm 2 always computes some (αS , αE ) and this strategy (αS , αE ) forms a renegotiation-proof natural
Markov-perfect equilibrium. So, a renegotiation-proof natural Markov-perfect equilibrium always exists.
Proof. See Appendix B.
The renegotiation-proof property helps to eliminate the equilibria involving exit and mixing actions when joint continuation is profitable. However, the other source of the multiplicity persists. As we have illustrated in the example in Appendix C, when joint survival
is not profitable and more than two firms are randomizing between survival and exit, there
can be multiple equilibrium mixing probabilities. The property of renegotiation-proofness is
silent on which probability to select. Therefore, each distinct equilibrium mixing probability leads to a different equilibrium survival rule. Different combinations of the equilibrium
survival rules result in different renegotiation-proof natural Markov-perfect equilibria. Since
the Bellman equation for wE defines the necessary condition for renegotiation-proof natural
Markov-perfect equilibrium payoff, any such equilibrium should be an outcome of Algorithm
2, if the mixing probabilities that correspond to this equilibrium are used in the computation.
Recall that we do have proven in Proposition 2 that if a payoff-monotone equilibrium
exists, the mixing probability is always unique, and such equilibrium is the unique outcome
of Algorithm 2. This implies the following corollary to Proposition 2.
Corollary 1. If there exists a payoff-monotone natural Markov-perfect equilibrium, it is also
the unique renegotiation-proof natural Markov-perfect equilibrium.

30

If there is no payoff-monotone equilibrium, the possible multiplicity of mixing probabilities
may challenge our equilibrium computation. After all, each step of Algorithm 2 requires the
unique input of payoffs and rules computed in the previous steps. (In Section 4.1, Algorithm
2 simply selects an arbitrary mixing probability to continue when the multiplicity arises.) In
Section ?? of the online appendix, we prove that the number of renegotiation-proof natural
Markov-perfect equilibria is finite if C is discrete. We also extend Algorithm 2 so that
it computes all renegotiation-proof natural Markov-perfect equilibria, by creating parallel
branches of Algorithm 2 every time the multiplicity arises, with each branch corresponding
to a distinct choice of mixing probability.

References
Abbring, J. H., and J. R. Campbell (2010): “Last-In First-Out Oligopoly Dynamics,”
Econometrica, 78(5), 1491–1527. 1
Abbring, J. H., J. R. Campbell, and N. Yang (2010): “Sunk Costs, Entry and Exit
in Dynamic Oligopoly,” Mimeo, CentER, Department of Econometrics & OR, Tilburg
University. 1
Bresnahan, T. F., and P. C. Reiss (1990): “Entry in Monopoly Markets,” Review of
Economic Studies, 57(4), 531–553. 1
Cabral, L. M. (1993): “Experience Advantages and Entry Dynamics,” Journal of Economic Theory, 59, 403–416. 2, 6
Doraszelski, U., and A. Pakes (2007): “A Framework for Applied Dynamic Analysis
in IO,” in Handbook of Industrial Organization, ed. by M. Armstrong, and R. H. Porter,
vol. 3, chap. 4. Elsevier Science, Amsterdam. 1
Ericson, R., and A. Pakes (1995): “Markov-Perfect Industry Dynamics: A Framework
for Empirical Work,” Review of Economic Studies, 62, 53–82. 1, 2, 5
Ferris, M., K. Judd, and K. Schmedders (2007): “Solving Dynamic Games with Newton’s Method,” Discussion paper, University of Wisconsin, Madison. 23
Fershtman, C., and A. Pakes (2000): “A Dynamic Oligopoly with Collusion and Price
Wars,” RAND Journal of Economics, 31(2), 207–236. 0, 2, 20, 23
Fudenberg, D., and J. Tirole (1991): Game Theory. MIT Press, Cambridge, MA. 6
Judd, K. L. (1998): Numerical Methods in Economics. MIT Press. 23
31

Appendices
A

Proofs for Section 3

Proof of Lemma 1. First, we verify a property of the post-entry payoff function.
Property 1. For a given k ∈ K, and for all x such that 0 ≤ x ≤ ǩ, if vE (ιk + ιx , ·, k) is
weakly decreasing in x, we say that vE satisfies Property 1 for k.
Intuitively, Property 1 requires that a type-k firm’s post-entry payoff is weakly decreasing
in its opponent’s type. A sufficient condition for Lemma 1 is that in any natural equilibrium,
vE satisfies Property 1 for all k ∈ K. In order to prove this sufficient condition, we also need
to verify vE satisfies three other interdependent properties for all k ∈ K.
Property 2. For a given k ∈ K, and for all x such that 0 ≤ x ≤ ǩ, if vE (ιk + ιx , ·, x) is
weakly increasing in x, we say that vE satisfies Property 2 for k.
Property 3. For a given k ∈ K, and for all x such that 1 ≤ x ≤ k − 1, if vE (ιk + ιx , ·, x) ≤
vE (ιk−1 + ιx , ·, x), we say that vE satisfies Property 3 for k.
Property 4. For a given k ∈ K, if vE (ιk , ·, k) ≥ vE (ιk−1 , ·, k − 1), we say that vE satisfies
Property 4 for k 12 .
To prove the three properties for all k, we first show that given any equilibrium strategy
(aS , aE ), vE is computed as the unique fixed point of a contraction mapping. Then, we prove
in turn that vE satisfies Property 2, 1, 3, and 4 for k = ǩ. Therefore, if we have a Banach
space in which all elements are functions that satisfy the properties for ǩ, the contraction
maps this space into itself. Next, we iterate on k = ǩ − 1, . . . , 1. In each step, we start with a
Banach space in which all elements are functions that satisfy the properties for k + 1, . . . , ǩ.
We know from the previous steps that the contraction maps the space into itself. Then,
we construct a smaller Banach space by requiring all its elements to additionally satisfy the
properties for k. We further show that the contraction maps the smaller Banach space into
itself. This procedure gives us a sequence of shrinking spaces, with the smallest one contains
all functions that satisfy Properties 1-4 for all k. Because vE is the unique fixed point of the
contraction, it must be in the smallest space and satisfy these properties for all k. We leave
all the algebraic details to Section ?? of the online appendix.
After Property 1 is verified for all k, vE (2ιk , c, k) ≤ vE (ιk , c, k) for any k ∈ K follows
immediately. Using the definition in equation (2) and Property 1, we can prove vS (2ιk , c, k) ≤
vS (ιk , c, k) for any k ∈ K. The details are in the online appendix.
12

For completeness, vE (ι0 , ·, 0) ≡ 0.

32

Proof of Proposition 1. We prove the proposition in two steps. First, we establish a lemma
verifying that the candidate equilibrium computed by Algorithm 1 is indeed a natural
Markov-perfect equilibrium. Then, we use Lemma 1 to prove that the constructed equilibrium is essentially unique.
Lemma 2. The strategy (αS , αE ) and payoff function wE constructed by Algorithm 1 form
a natural Markov-perfect equilibrium.
Proof. The proof for Lemma 2 has two parts. First, note that Algorithm 1 already embodies
the requirement in Definition 1, i.e., for k 1 > k 2 , holding αS (ιk1 + ιk2 , c, k 1 ) = 1 when
computing the payoff and strategy for k 2 firm. We then need to verify that the candidate
equilibrium payoff function wE supports this heuristic, i.e., wE (ιk1 + ιk2 , c, k 1 ) > 0 whenever
αS (ιk1 +ιk2 , c, k 2 ) > 0. Second, we show that (αS , αE ) forms a natural equilibrium by proving
that it is one-shot-deviation-proof.
Prove wE (ιk1 + ιk2 , ·, k 1 ) ≥ wE (ιk1 + ιk2 , ·, k 2 ). Given any (αS , αE ), wE is computed as
the fixed points of the contraction mappings in Algorithm 1. This enables us to use the
same trick as in the proof for Lemma 1. We focus on a Banach space in which all elements
are functions that satisfy f (ιk1 + ιk2 , ·, k 1 ) ≥ f (ιk1 + ιk2 , ·, k 2 ). Then we prove that all the
contractions computing wE map the space into itself. The algebraic details are in the online
appendix, Section ??.
Verify one-shot deviation proofness. To verify one-shot deviation proofness for αS , we
need to show that for any k 1 , k 2 , c, 1 ≤ k 1 ≤ ǩ and 0 ≤ k 2 ≤ ǩ,
αS (ιk1 + ιk2 , c, k 1 ) ∈ arg max aE[wS (M 0 , c, k 1 )|M = ιk1 + ιk2 ]

(12)

a∈[0,1]

where

1
2

 aS (ιk1 + ιk2 , c, k )wS (ιk1 + ιk2 , c, k )
E[wS (M 0 , c, k 1 )|M = ιk1 +ιk2 ] =
+(1 − aS (ιk1 + ιk2 , c, k 2 ))wS (ιk1 , c, k 1 )


wS (ιk1 + ιk2 , c, k 1 )

if k 1 ≥ k 2
if k 1 < k 2

(13)

and wS is defined analogously as vS by equation 2. To verify (12), consider the following
cases
1. For all c such that αS (ιk1 + ιk2 , c, k 1 ) = 1, we know wE (ιk1 + ιk2 , c, k 1 ) > 0. Then, we
show that E[wS (M 0 , c, k 1 )|M = ιk1 + ιk2 ] > 0.
(a) If k 1 ≤ k 2 , then wE (ιk1 + ιk2 , c, k 1 ) is computed by Tk2 ,k1 and wE (ιk1 + ιk2 , c, k 1 ) =
max {0, wS (ιk1 + ιk2 , c, k 1 )} > 0. Then, from (13), E[wS (M 0 , c, k 1 )|M = ιk1 +ιk2 ] =
wS (ιk1 + ιk2 , c, k 1 ) > 0.
33

(b) If k 1 > k 2 , then wE (ιk1 + ιk2 , c, k 1 ) is computed by Tk1 and wE (ιk1 + ιk2 , c, k 1 ) =
max {0, E[wS (M 0 , c, k 1 )|M = ιk1 + ιk2 ]} > 0, so E[wS (M 0 , c, k 1 )|M = ιk1 +ιk2 ] > 0.
So, arg maxa∈[0,1] aE[wS (M 0 , c, k 1 )|M = ιk1 + ιk2 ] = {1} 3 αS (ιk1 + ιk2 , c, k 1 ) = 1.
2. For all c such that αS (ιk1 + ιk2 , c, k 1 ) = 0, we know wE (ιk1 + ιk2 , c, k 1 ) = 0. Then, we
show that E[wS (M 0 , c, k 1 )|M = ιk1 + ιk2 ] = 0.
(a) If k 1 < k 2 , then wE (ιk1 + ιk2 , c, k 1 ) is computed by Tk2 ,k1 and wE (ιk1 + ιk2 , c, k 1 ) =
max {0, wS (ιk1 + ιk2 , c, k 1 )} = 0. Then, from (13), E[wS (M 0 , c, k 1 )|M = ιk1 +ιk2 ] =
wS (ιk1 + ιk2 , c, k 1 ) ≤ 0.
(b) If k 1 ≥ k 2 , then in natural equilibrium it must be that αS (ιk1 + ιk2 , c, k 2 ) = 0, and
hence (13) gives E[wS (M 0 , c, k 1 )|M = ιk1 + ιk2 ] = wS (ιk1 , c, k 1 ). Because wE (ιk1 +
ιk2 , c, k 1 ) is computed by Tk1 and wE (ιk1 + ιk2 , c, k 1 ) = max {0, wS (ιk1 , c, k 1 )} = 0,
E[wS (M 0 , c, k 1 )|M = ιk1 + ιk2 ] ≤ 0.
So, arg maxa∈[0,1] aE[wS (M 0 , c, k 1 )|M = ιk1 + ιk2 ] 3 αS (ιk1 + ιk2 , c, k 1 ) = 0. Note that if
we require default to inactivity, arg maxa∈[0,1] aE[wS (M 0 , c, k 1 )|M = ιk1 + ιk2 ] = {0}.
3. For all c such that αS (2ιk1 , c, k 1 ) is determined by (9), then k 1 = k 2 and
E[wS (M 0 , c, k 1 )|M = ιk1 +ιk2 ] = αS (2ιk1 , c, k 1 )wS (2ιk1 , c, k 1 )+(1−αS (2ιk1 , c, k 1 ))wS (ιk1 , c, k 1 ) = 0.
The last equality is due to equation (9). So, arg maxa∈[0,1] aE[wS (M 0 , c, k 1 )|M = ιk1 +
ιk2 ] = [0, 1] 3 αS (2ιk1 , c, k 1 ).
To verify one-shot-deviation-proofness for αE , we need to show that for any k, c, 0 ≤ k ≤
ǩ,
αE (ιk + ι1 , c) ∈ arg max a(E[wE (M 0 , c, 1)|M = ιk + ι1 ] − ϕ)

(14)

a∈[0,1]

where
(
E[wE (M 0 , c, 1)|M = ιk +ι1 ] =

wE (ιk + ι1 , c, 1)
(1 − αE (2ι1 , c))wE (ι1 , c, 1) + αE (2ι1 , c)wE (2ι1 , c, 1)

if k > 0
if k = 0

By construction, αE (ιk + ι1 , c) satisfies (14) except for k = 0. Thus, at this moment, we
can assert that αE (ιk + ι1 , c) is a natural Markov-perfect equilibrium strategy for all k > 0.
Since no operator T in Algorithm 1 depends on αE (ι1 , c), this result is sufficient to ensure
that the fixed points, wE is the natural Markov-perfect equilibrium payoff corresponding to
(αS , αE ). Lemma 1 then guarantees that wE also exhibits wE (2ι1 , c, 1) ≤ wE (ι1 , c, 1). Thus,

34

1. when αE (2ι1 , c) = 1, it must be the case that wE (ι1 , c, 1) ≥ wE (2ι1 , c, 1) > ϕ so
αE (ι1 , c) = 1. The right-hand-side of (14) is
arg max a(E[wE (M 0 , c, 1)|M = ιk +ι1 ]−ϕ) = arg max a(wE (2ι1 , c, 1)−ϕ) = {1} 3 αE (ι1 , c).
a∈[0,1]

a∈[0,1]

2. when αE (2ι1 , c) = 0, E[wE (M 0 , c, 1)|M = ιk + ι1 ] = wE (ι1 , c, 1). So αE (ι1 , c) =
I[wE (ι1 , c, 1) > ϕ] satisfies (14).
So, we conclude that (αS , αE ) forms a natural Markov-perfect equilibrium and wE , wS are
the associated payoffs.
With Lemma 2 in hand, we can prove the uniqueness of natural Markov-perfect equilibrium following the order of Procedure 1, starting from k11 = ǩ. First, observe that in a
symmetric equilibrium, if vS (2ιǩ , c, ǩ) ≤ 0, then vE (2ιǩ , c, ǩ) = 0. Then, if vS (2ιǩ , c, ǩ) > 0,
Lemma 1 ensures that in any equilibrium, vS (ιǩ , c, ǩ) ≥ vE (2ιǩ , c, ǩ) > 0 for any n < m̌. This
means that continuation dominates any other action when vS (2ιǩ , c, ǩ) > 0. Therefore, any
equilibrium post-entry payoff must be a fixed point of Tǩ,ǩ in Algorithm 1, vE (2ιǩ , ·, ǩ) =
wE (2ιǩ + ιk , ·, k). Consequently, for any k < ǩ, wE (ιǩ + ιk , ·, k) is determined as the unique
natural Markov-perfect equilibrium payoff. Recall that in the proof for Lemma 2, the optimal
strategy sets for type-k firm are singletons. Therefore, αS (ιǩ + ιk , ·, k) and αE (ιǩ + ι1 , ·) is the
unique natural Markov-perfect equilibrium strategy, which guarantees that wE (ιǩ + ιk , ·, ǩ) is
the unique post-entry equilibrium payoff. The uniqueness of wS (ιǩ + ιk , ·, ǩ) readily follows
and the uniqueness of aS (2ιǩ , ·, ǩ) is ensured by equation (9).
In the i-th steps in Procedure 1, suppose the pair of types considered is (h, l) = (k1 , k2 ).
When k 1 = k 2 , Lemma 1 and equilibrium symmetry again ensure that any equilibrium
post-entry payoff vE (2ιk1 , ·, k 1 ) must be a fixed point of Tk1 ,k1 . Hence, vE (2ιk1 , ·, k 1 ) =
wE (2ιk1 , ·, k 1 ) is the unique natural Markov-perfect equilibrium payoff. Then, for any k 2 < k 1 ,
since Tk1 ,k2 does not depend on any strategy, wE (ιk1 + ιk2 , ·, k 2 ) is determined as the unique
post-entry equilibrium payoff and αS (ιk1 + ιk2 , ·, k 2 ), αE (ιk1 + ι1 , ·) as the unique natural
Markov-perfect equilibrium strategy that is consistent with payoff-maximization. Because
Tk1 only depends on natural Markov-perfect equilibrium strategy that has been verified to be
unique, wE (ιk1 + ιk2 , ·, k 1 ) is then uniquely determined as the post-entry equilibrium payoff.
The uniqueness of wS (ιk1 +ιk2 , ·, k 1 ) and wS (ιk1 +ιk2 , ·, k 2 ) are then straightforwardly verified.
Equation (9) ensures the uniqueness of aS (2ιk1 , ·, k 1 ).

B

Proofs for Section 4

To prove Propositions 3 and 2, we prove a useful lemma first.
35

Lemma 3. Algorithm 2 always delivers some (αS , αE ) as outcome. Furthermore, (αE , αS )
forms a natural Markov-perfect equilibrium, with payoffs wE and wS .
Proof. We follow four steps to prove this lemma. We first show that Algorithm 2 computes
wE , wS , αS , and αE for all (m, c, k). Second, we prove that Algorithm 2 always delivers some
well-defined (αS , αE ) as outcome. This is a nontrivial step. Because we need to show that
wE as the fixed point of T always exist, and αS is well defined when Procedure 3 assigns p
from equation (11) to it.
After proving the first part of the lemma, we verify in the third step of the proof that αS
satisfies the requirement in Definition 1. Eventually, we prove that in each step of Algorithm
2, wE is constructed as an equilibrium post-entry value, and the corresponding wS gives the
equilibrium post-survival payoff. Along the way, we also show that (αS , αE ) is an natural
equilibrium strategy.
First, note that the set of all indexing market structures is M ≡ {m ∈ Zǩ ; 1 ≤ |m| ≤
m̌}, which is also the set of all payoff-relevant market structures. Consider any (m, k) pair
such that m ∈ M and mk > 0, wE (m, ·, k) and wS (m, ·, k) are computed in the step with
indexing market structure (0, . . . , 0, mk , mk+1 , . . . , mǩ ). For any (m, k) pair such that m ∈ M,
αS (m, ·, k) is computed in the step with indexing market structure (0, . . . , 0, 1, mk+1 , . . . , mǩ ).
For any m such that m ∈ M and m1 > 0, αE (m, k) is computed in the step with indexing
market structure m. Therefore, wE , wS , αS , αE for all payoff-relevant (m, c, k) are computed
in Algorithm 2.
Second, because all αS , αE , wE , wS required to compute the fixed point of T in each
step have been either initialized or determined in previous steps, T is always a well-defined
contraction mapping with a unique fixed point. Then, wE is always uniquely determined,
as well as wS and αE . It remains to show that αS is also always well-defined, in particular
when it is determined from equation (11). Note that for any (m, c, k) such that k = k(m) ≡
min{j; mj > 0}, when computing wE (m, c, k) using T , we always use the initialized value
αS (m, c, k + ) = 1 for all k + ≥ k, which leads to the condition that
wE (m, c, k) = max{0, wS (m, c, k)}.
This implies that when wE (m, c, k) = 0, wS (m, c, k) ≤ 0. Recall that tn Procedure 3, when
determining p using equation (11) in step i, it is indeed the case that wE (m, c, k i ) = 0 and
wS (m, c, k i ) ≤ 0. Then, (i) if wS (mi , c, k i ) = wS (m − (mki − 1)ιki , c, k i ) > 0, then the
right hand side of equation (11) changes continuously from wS (m − (mki − 1)ιki , c, k i ) > 0
to wS (m, c, k) ≤ 0 when p changes from 0 to 1. This means that there exists at least one
p ∈ [0, 1) to satisfy equation (11); (ii) if wS (mi , c, k i ) ≤ 0, 0 can be assigned if no p is found
to satisfy equation (11). Therefore, we conclude that αS is always well-defined (although it
can take multiple values if multiple p solve equation (11)).
36

Next, we show that αS satisfies the requirement in Definition 1 by proving wE (m, c, k 1 ) ≥
wE (m, c, k 2 ) for all m, c and k 1 ≥ k 2 . To this end, for any computed
wiE , define a functional
h
βπ(ιǩ ,č,ǩ)
N
such that gE ≤ wE ,
space G containing all functions gE : M × [ĉ, č] × K → 0, 1−β
1
2
1
2
and gE (m, c, k ) ≥ gE (m, c, k ) for all (m, c) and k = k + 1, with equality holds only when
gE (m, c, k 1 ) = gE (m, c, k 2 ) = 0. We aim to prove T : G N → G N .
Let gS denote the analogous post-exit value computed by equation (2) using gE . Under
Assumptions 1, for all gE ∈ G N , gS (m, c, k 1 ) > gS (m, c, k 2 ) for all m, c and k 1 = k 2 + 1.
Consider the following cases when (T gE )(m, c, k 1 ) is being computed in Algorithm 2, noting
that by the OLS ordering of the algorithm, at this moment, αS (m, c, k 1 ) remains at its initial
value 1 and αS (m, c, k 2 ) has been determined in previous computation by Procedure 3.
1. If αS (m, c, k 2 ) = 1, since both type-k 1 , k 2 firms survive with probability one, they
expect same post-exit market structure, denoted by MS .




(T gE )(m, c, k 1 ) = E gS (MS , c, k 1 ) ME = m > E gS (MS , c, k 2 ) ME = m = (T gE )(m, c, k 2 ).
2. If 0 < αS (m, c, k 2 ) < 1, then αS (m, c, k 2 ) = p with p ∈ [0, 1) solving
mk2 −1

X
j=0

2 −1


kX
2 − 1
m
k
pmk2 −1−j (1 − p)j
gS (m − jιk2 −
mi ιi , c, k 2 ) = 0.
j
i=1

The right hand side is nothing but (T gE )(m, c, k 2 ). Therefore, (T gE )(m, c, k 2 ) = 0.
Since gS ∈ G N , we have


2 −1


kX
k2 −1

 mX
mk2 − 1
pmk2 −1−j (1 − p)j
gS (m − jιk2 −
mi ιi , c, k 1 ) > 0.
(T gE )(m, c, k 1 ) = max 0,


j
j=0

i=1

3. If αS (m, c, k 2 ) = 0, then gE (m, c, k 2 ) ≤ wE (m, c, k 2 ) = 0 for gE ∈ G N . Since wE (m, c, k 2 ) =
(T ∞ gE )(m, c, k 2 ) and T is a monotone operator, 0 = wE (m, c, k 2 ) ≥ (T gE )(m, c, k 2 ) for
all gE ∈ G N . Thus, (T gE )(m, c, k 1 ) ≥ 0 ≥ (T gE )(m, c, k 2 ).
By point-wise comparison, we conclude that T : G N → G N , hence wE (m, c, k 1 ) ≥
wE (m, c, k 2 ) for all m, c and k 1 = k 2 + 1. The proof also verifies that (T gE )(m, c, k 1 ) > 0
whenever αS (m, c, k 2 ) > 0. Since T is a monotone operator, it means that wE (m, c, k 1 ) =
(T ∞ gE )(m, c, k 1 ) > 0. Given that in Algorithm 2 αS is set to be 1 if and only if wE (m, c, k 1 ) >
0, αS (m, c, k 1 ) = 1 whenever αS (m, c, k 2 ) > 0. So αS satisfies the requirement in Definition
1.
Finally, we prove that (αS , αE ) forms an Markov-perfect equilibrium. To this end, we first
show that wE constructed by Algorithm 2 is the post-entry payoff under strategy (αS , αE ).
Then, we show that given wE as payoff, (αS , αE ) satisfies one-shot deviation proofness.
37

We begin with showing that wE is the post-entry payoff under (αS , αE ) in the first step
of Algorithm 2, where m1 = m̌ιǩ . In this step, H1S = {(m1 , c, ǩ)|c ∈ [ĉ, č]}. When computing
wE (HS1 ), we use αS (HS1 ) = 1 for all H1S , αE (·) = 0, and wE (·) = 0. According to equation
(1), if wE is the post-entry payoff under strategy (αS , αE ), then it satisfies


wE (HS1 ) = αS (HS1 )E wS (MS , c, ǩ) ME = m1 , C = c, K = ǩ .
The construction of αS in Procedure 3 implies that αS (m1 , c, ǩ) = 1 if and only if
wE (m1 , c, ǩ) > 0, and αS (m1 , c, ǩ) < 1 if and only if wE (m1 , c, ǩ) = 0. Also, note that


E wS (MS , c, ǩ) ME = m1 , C = c, K = ǩ = wS (m1 , c, ǩ) if αS (m1 , c, ǩ) = 1. Then, the
above condition for wE (HS1 ) under the constructed αS is equivalent to
wE (HS1 ) = max{0, I(wE (HS1 ) > 0)wS (HS1 )} = max{0, wS (HS1 )}.
By setting αS (HS1 ) = 1, the right hand side of T is identical to this condition. Therefore,
setting αS (HS1 ) = 1 is computationally equivalent to using αS (HS1 ) determined by Procedure
3, i.e., both give the same wE (HS1 ). Also, under αE (·) = 0, no firm will further enter. This
means that wE (HS1 ) computed as the fixed point of T is the post-entry payoff under strategy
(αS , αE ).
Consequently, for all c, wS (m1 , c, ǩ) computed by equation (2) using wE (m1 , ·, ǩ) is the
post-survival payoff under strategy (αS , αE ).
Then suppose that the 1, . . . , i−1-step of Algorithm 2 have computed the wE (m, c, k) and
S
Mmj × {k(mj )} and all c as the payoffs under (αS , αE ).
wS (m, c, k) for all (m, k) ∈ j=i−1
j=1
Then, Procedure 3 in the first i − 1-step computes the following part of (αS , αE ) for all c,
S
Mmj ×{k(mj )}, m−nιki 6= mi , ∀n ∈
• αS (m, c, k) for all (m, k) ∈ {(m, k); (m, k) ∈ j=i−1
j=1
N}.
• αE (m, c) for all m ∈ {m; m ∈

Sj=i−1
j=1

Mmj with k(mj ) = 1}.

Recall that k(m) ≡ min{j; mj > 0}. Now, in the i-th step of the algorithm, HSi ∈
{(m, c, k); m ∈ Mmi , c ∈ [ĉ, č] , k = k i }. To make sure that wE (HSi ) and wS (HSi ) take their
values under (αS , αE ), we need to use in the construction of T the strategy αS (m, ·, k) for
all m ∈ Mmi and k such that mk > 0, αE (n0 + jι1 , ·) for all j ∈ N and all possible n0 , and
wE (HSi,0 ) for (m0 , k 0 ) such that m0 ∈
/ Mmi and k 0 6= k i , conditional on type-k i firms having
positive payoff.
We check if the required values are in place.
1. From the argument for step-1 computation, the initialized value αS (m, c, k i ) = 1 leads
to the same condition for wE (m, c, k i ) as the αS (m, c, k i ) computed by Procedure 3.
So, although αS (m, c, k i ) has not been obtained, we can set it to 1.
38

2. For any (m, k + ) such that m ∈ Mmi and k + > k i , as we have shown, αS (m, c, k + ) = 1
conditional wE (m, c, k i ) > 0, which is the same as the initialized value. For any (m, k − )
such that m ∈ Mmi and k − < k i , note that m 6= mi because mik− = 0. By the definition
of Mmi , for all m ∈ Mmi \{mi }, m  mi (so there is some j < i-step such that its
indexing market structure mj = m) and m − bιik 6= mi , ∀b ∈ N. Therefore, αS (m, c, k − )
for all k − < k i have been computed.
3. Since according to αS , all firms with type equal or better than k i survive, which,
together with non-regressive type evolution, implies that n0  mi and n0 + bι1  mi
for all n0 and all b ∈ N. Therefore, for |n0 + bι1 | ≤ m̌, there is some j < i-th step with
indexing market structure mj = n0 + bι1 . So, these αE (n0 + bι1 )’s values have been
computed in the j-th step by Procedure 3. For any n0 such that |n0 + ι1 | > m̌, we use
the initialized value αE (n0 + ι1 ) = 0.
4. Based on the above argument, for any (m0 , k 0 ) following the transition governed by
(αS , αE ), m0  mi and k 0 ≥ k i . If m0 ∈
/ Mmi and k 0 6= k i , define m0 (k 0 ) = (0, . . . , 0, m0k0 , . . . , m0ǩ ),
the market structure which has exactly the same number of type-k 0 or better firms as
m0 does, but no type-k 0 −1 or worse firm. Then, m0 (k 0 )  mi , which means that there is
some j < i-th step such that its indexing market structure mj = (0, . . . , 0, m0k0 , . . . , m0ǩ ).
Since m0 ∈ Mmj , wE (m0 , ·, k 0 ) is then computed in the j-th step. So, all necessary wE ’s
values have been computed.
Since all the required values of wE , αS , αE have been obtained in earlier steps, wE (HSi ) is
computed as the payoff under (αS , αE ), so as wS (HSi ).
Then, we verify that (αS , αE ) is an equilibrium strategy corresponding to wE , wS . To this
end, we show that αS (m, c, k) satisfies (4) for all (m, c, k), if all other firms follow αS as well.
For any (m, c, k), consider the following cases
1. If wE (m, c, k) > 0, the algorithm sets αS (m, c, k) = 1. The right-hand-side of (4) is
arg max awE (m, c, k) = {1} 3 αS (m, c, k).
a∈[0,1]

2. If wE (m, c, k) = 0, then the algorithm sets αS ∈ [0, 1). Since any αS computed by
Algorithm 2 satisfies the requirement in Definition 1, it is implied that αS (m, c, k − ) = 0
P
for all k − < k. Hence, wE (m, c, k) = wE (m − k−1
i=1 mi ιi , c, k) = max{0, wS (m −
Pk−1
Pk−1
i=1 mi ιi , c, k)} and wS (m −
i=1 mi ιi , c, k) ≤ 0. We look at three subcases,
Pk−1
(a) If wS (m − (mk − 1)ιk − i=1
mi ιi , c, k) > 0, the algorithm sets αS (m, c, k) = p ∈
[0, 1) to satisfy


m
k−1
k −1
X
X
mk −1−j
j mk − 1
p
(1 − p)
wS (m − jιk −
mi ιi , c, k) = 0,
j
j=0
i=1
39

The right-hand-side of (4)


m
k−1
k −1
X
X
mk −1−j
j mk − 1
wS (m−jιk −
mi ιi , c, k) = [0, 1] 3 αS (m, c, k).
p
(1−p)
arg max a
a∈[0,1]
j
i=1
j=0
P
(b) If wS (m − (mk − 1)ιk − k−1
i=1 mi ιi , c, k) > 0 and αS (m, c, k) ∈ [0, 1) solves the same
polynomial as above, same result holds for αS (m, c, k).
P
(c) If wS (m − (mk − 1)ιk − k−1
i=1 mi ιi , c, k) ≤ 0 and αS (m, c, k) = 0. All other type-k
firms will exit from the market, so the right-hand-side of (4) is
arg max awS (m − (mk − 1)ιk −
a∈[0,1]

k−1
X

mi ιi , c, k) = {0} 3 αS (m, c, k).

i=1

For any (m, c, k) such that mk = 1, consider the following cases
1. If wE (m, c, k) > 0, then the algorithm sets αS (m, c, k) = 1. The right-hand-side of (4)
is arg maxa∈[0,1] awS (m, c, k) = {1} 3 αS (m, c, k).
2. If wE (m, c, k) = 0, then αS can not be 1. From the same argument as above, wE (m, c, k) =
Pk−1
Pk−1
P
wE (m− k−1
i=1 mi ιi , c, k) ≤
i=1 mi ιi , c, k)}. So wS (m−
i=1 mi ιi , c, k) = max{0, wS (m−
Pk−1
0 and the right-hand-side of (4) is arg maxa∈[0,1] awS (m − i=1 mi ιi , c, k) = {0} 3
αS (m, c, k).
Therefore, αS satisfies (4). To show that αE satisfies (3), first note that αE (m, c) is
determined in the step with indexing market structure m, while wE (m + bι1 , c, 1) is computed
in step with indexing market structure m + bι1 , which is (weakly) lexicographically superior
than m. Therefore, wE (m + bι1 , c, 1) has been determined as a post-entry payoff under αS .
Then, if all potential entrants are using αE , according to (1), post-entry payoff is wE (m +
Jι1 , c, 1) where J is the largest possible number such that wE (m+Jι1 , c, 1)−ϕ > 0. Therefore,
αE satisfies (3). So, (αS , αE ) is the equilibrium strategy.
This completes the proof for Lemma 3.
With Lemma 3 in hand, we proceed to prove Propositions 2 and 3.
Proof for Proposition 2. To prove this proposition, we again establish a lemma first.
Lemma 4. If vE is the post-entry payoff in a payoff-monotone natural Markov-perfect equilibrium, it necessarily satisfies that vE (m, c, k) > 0 if and only if E[vS (MS , c, k)|ME = m] > 0,
or
vE (m, c, k) = max{0, E[vS (MS , c, k)|ME = m]},
where the expectation is computed given all equilibrium values aS (m, c, k − ) for all k − < k, a
tentative rule aS (m, c, k) = 1, and aS (m, c, k + ) = 1 for all k + > k.
40

Proof. In any symmetric equilibrium, vE (m, c, k) > 0 only if all firms with type k survive.
In any natural equilibrium, this also implies that all firms with type k + survive as well.
Therefore, the “only if” part is true.
The “if” part is true because (i) if E[vS (MS , c, k)|ME = m] > 0 and aS (m, c, k − 1) > 0,
then it must be the case that in natural equilibrium vE (m, c, k − 1) > 0. Also, according to
Definition 1, aS (m, c, k) = 1 and aS (m, c, k + ) = 1. Then, vE (m, c, k) ≥ vE (m, c, k − 1) > 0;
(ii) if E[vS (MS , c, k)|ME = m] > 0 and aS (m, c, k − 1) < 0, then in a natural equilibrium
P
aS (m, c, k − ) = 0 for all k − < k, and E[vS (MS , c, k)|ME = m] = vS (m − k−1
i=1 mi ιi , c, k) > 0.
Recall that we have shown in the proof for Proposition 1 that in the duopoly model, Lemma 1
ensures that vE (2ιk , c, k) > 0 if and only if vS (2ιk , c, k) > 0. Applying an analogous reasoning,
P
we know that in a payoff-monotone equilibrium, vE (m, c, k) > 0 if vS (m − k−1
i=1 mi ιi , c, k) >
0.
Lemma 4 gives a necessary condition for the post-entry payoff in a payoff-monotone
natural Markov-perfect equilibrium. For vE (m1 , c, ǩ), where m1 = m̌ιǩ is the indexing market
structure in the first step of Algorithm 2, this condition can be written as
vE (m1 , c, ǩ) = max{0, vS (m1 , c, ǩ)}.
In the first step of Algorithm 2, wE (m1 , c, ǩ) is uniquely computed by the contraction mapping
generated by the above condition. Thus, it is the only payoff function satisfying the necessary
condition for a payoff-monotone equilibrium. Providing that such equilibrium exists, its
post-entry payoff vE (m1 , c, ǩ) has a unique value wE (m1 , c, ǩ) for all c. Also, vS (m1 , c, ǩ) =
wS (m1 , c, ǩ) for all c.
In any succeeding step i of Algorithm 2, with αS either properly initialized or computed
in the previous steps as its equilibrium value (this is shown in Lemma 3), wE (m, c, k i ) is
computed as the unique payoff under (αS , αE ) that satisfies such necessary condition for all
c and all m ∈ Mmi .
Moreover, the (αS , αE ) constructed in Procedure 3 is also the unique equilibrium strategy
given that the wE , wS computed in previous steps are unique equilibrium payoffs vE , vS . αE ’s
uniqueness trivially follows its construction. The uniqueness of αS is due to the monotonicity
of (the previously computed part of) wS : When using (11) to compute the mixing probability
p, because wS (m − (mki − 1)ιki , c, k i ) ≥ wS (m − (mki − 2)ιki , c, k i ) ≥ . . . ≥ wS (m, c, k i ), the
right hand side (11) changes continuously and monotonically from wS (m−(mki −1)ιki , c, k i ) >
0 to wS (m, c, k i ) ≤ 0 when p changes from 0 to 1. Therefore, there is only one p ∈ [0, 1) that
satisfies (11). So, αS is single valued.
Therefore, if there exists a payoff-monotone equilibrium, (αS , αE ) forms the unique equilibrium and wE and wS are the unique equilibrium payoffs. The equilibrium is subsequently
unique.
41

Proof for Proposition 3. First, note that from the definition of a renegotiation-proof natural
Markov-perfect equilibrium, all firms with a same type survive for sure if and only if joint
continuation gives them positive post-survival payoff. This implies that (i) any such equilibrium’s post-entry equilibrium payoff must satisfy the condition in Lemma 4; (ii) if any
natural Markov-perfect equilibrium’s post-entry payoff satisfies the condition in Lemma 4,
such equilibrium is renegotiation-proof.
Since we have shown in Lemma 3 that Algorithm 2 always gives some (αS , αE ) to form a
natural Markov-perfect equilibrium. We have also shown in the proof for Proposition 2 that
wE satisfies the necessary condition in Lemma 4. Therefore, (αS , αE ) forms a renegotiationproof natural Markov-perfect equilibrium.

C

An Example of Multiple Equilibria

We construct a three-firm two-type example where the equilibrium payoff is not weakly
decreasing in the number of same-type competitors (m̌ = 3 (by setting π(n, c, k) < 0 for any
(n, c, k) if n has more than 3 firms) and ǩ = 2).
Consider the following sequence of ct : c1 = 1, c2 = 1e−6 , ct = 5, for all t ≥ 3. The number
of consumers drops to nearly zero in the second period but is boosted to a high level in the
third period, and stays high afterwards. We set β = 0.5, κ(L) = κ(H) = 4, ϕ = 1, and
ΠLH = ΠLL = 0.5. We specify π as π(n, c, k) = cπ(n, k) − κ. Some parts of the per-consumer
producer surplus π are summarized in the following table:
π(·, L)/π(·, H)
+0ιL
+1ιL
+2ιL

1ιH
/102
99/101
1.23/1.25

2ιH
/100
0.89/1.24

3ιH
/1

One feature of this surplus structure is that a duopoly market promises much higher per
consumer surplus than a triopoly market does. The duopoly-triopoly surplus difference overwhelmingly dominates the L, H-type difference in surplus. Since from period 3 onwards, the
model is essentially an infinitely repeated game, we can use backward induction to compute
the equilibrium payoffs13 . Unlike the results stated in Lemma 1, vS is not always monotonic
in the number of firms,
vS (ιH , c1 , H) = −1.1821,

vS (2ιH , c1 , H) = 246,

vS (3ιH , c1 , H) = −1.5

Not surprisingly, the low triopoly surplus implies a low payoff if continuing as one of three
type-H firms. What is counter-intuitive is that the payoff to continuing as a duopolist is
13

We provide the details of such computation in an online appendix.

42

better than the payoff to continuing as a monopolist under c1 . This is because in period 2,
under a low c2 , a duopoly firm and a monopoly firm make similar flow profit and similar
large losses. However, duopoly firms can, by jointly remaining active, preempt any further
entrants and enjoy a high duopoly profit after demand increases to a high level in period 3.
The future duopoly payoff compensates the loss in period 2, and make vS (2ιH , c1 , H) positive.
In contrast, a monopoly market attracts two entrants for sure in period 2, which results in a
triopoly market from period 3 onwards. Because demand increases to a high level in period
3, none of these firms will exit and, given the per consumer surplus structure, they will all
earn a substantially lower payoff than duopoly firms, which can not compensate the loss in
period 2. Consequently, vS (ιH , c1 , H) is negative.
Given the computed non-monotone equilibrium payoff, (aS , aE ) with aS (2ιH , c1 , H) = 1 is
still an natural equilibrium. However, if one duopoly firm chooses to exit with probability 1,
the rival firm receives -1.1821 if continuing alone and hence will choose to exit with probability
−1.1821
= 4.782e−3 , the
1 as well. Similarly, if one firm chooses to survive with probability −1.1821−246
other firm is indifferent between exiting and survival. Therefore, two other natural equilibria
with aS (2ιH , c1 , H) = 0 and aS (2ιH , c1 , H) = 4.782e−3 exist.
Note that when both firms choose aS (2ιH , c1 , H) = 0 or aS (2ιH , c1 , H) = 4.782e−3 , they
receive zero payoffs. By ”renegotiating” on jointly choosing aS (2ιH , c1 , H) = 1, they can
strictly improve their equilibrium payoffs. Henceforth, we only restrict attention to equilibria
in which there is no room for this type of one-shot joint improvement.
Unfortunately, this type of equilibria may not be unique. Since joint continuation and
continuing as monopolist both render payoffs negative, in a one-shot renegotiation-proof
equilibrium, a triopoly firm either chooses aS (3ιH , c1 , H) = 0 or set aS (2ιH , c1 , H) = p, where
p solves
 
2
2
p v̄(3ιH , c1 , H) +
p(1 − p)v̄(2ιH , c1 , H) + (1 − p)2 v̄(ιH , c1 , H) = 0.
1
This quadratic equation has two roots, p1 = 0.0024 and p2 = 0.997, both between 0 and
1. Hence, there are three one-shot renegotiation-proof equilibria with aS (3ιH , c1 , H) equal to
0, p1 and p2 , respectively.

43

Online Appendix for
Simple Markov-Perfect Industry Dynamics
Jaap H. Abbring∗

Jeffrey R. Campbell†

Nan Yang‡

November 30, 2010

Contents
I

Details of Proofs
I.1 Details for the Proof of Lemma 1 . . . . . . . . . . . . . . . . . . . . . . . .
I.2 Details for the Proof of Proposition 1 . . . . . . . . . . . . . . . . . . . . . .

II Computational Techniques
II.1 Computing A Firm’s Beliefs about Next Period’s State . . . . . . . . .
II.2 Constructing the Type Transition Matrices in Matlab . . . . . . . . . .
II.2.1 The Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . .
II.2.2 The Dimensionality . . . . . . . . . . . . . . . . . . . . . . . . .
II.2.3 Recursive Construction of Πm . . . . . . . . . . . . . . . . . . .
II.2.4 The typetransition.m Function . . . . . . . . . . . . . . . . . . .
II.3 Computing All Renegotiation-proof Natural Markov-Perfect Equilibria

1
1
9

.
.
.
.
.
.
.

10
10
11
11
12
12
21
21

III Computational Details
III.1 Pencil-and-Paper Computation behind Figure 3 . . . . . . . . . . . . . . . .
III.2 Computing the Example of Multiple Equilibria in Section 4.2 . . . . . . . . .

23
23
30

∗

.
.
.
.
.
.
.

.
.
.
.
.
.
.

CentER, Department of Econometrics & OR, Tilburg University. E-mail: J.H.Abbring@uvt.nl
Federal Reserve Bank of Chicago and NBER. E-mail: jcampbell@frbchi.org
‡
VU University Amsterdam and Tinbergen Institute. E-mail: yang@tinbergen.nl
JEL Code: L13
†

I

Details of Proofs

I.1

Details for the Proof of Lemma 1

Proof. We prove that, in any natural Markov-Perfect Equilibrium, vE satisfies the following
properties for all k.
Property 1. For a given k ∈ K, and for all x such that 0 ≤ x ≤ ǩ, if vE (ιk + ιx , ·, k) is
weakly decreasing in x, we say that vE satisfies Property 1 for k.
Property 2. For a given k ∈ K, and for all x such that 0 ≤ x ≤ ǩ, if vE (ιk + ιx , ·, x) is
weakly increasing in x, we say that vE satisfies Property 2 for k.
Property 3. For a given k ∈ K, and for all x such that 1 ≤ x ≤ k − 1, if vE (ιk + ιx , ·, x) ≤
vE (ιk−1 + ιx , ·, x), we say that vE satisfies Property 3 for k.
Property 4. For a given k ∈ K, if vE (ιk , ·, k) ≥ vE (ιk−1 , ·, k − 1), we say that vE satisfies
Property 4 for k.
First, we prove these properties for k = ǩ. Then, for any k < ǩ, suppose that those
properties hold good for k + 1, k + 2, . . . , ǩ, we prove that they also hold for k. In this way,
we prove that these properties hold for all k ∈ K. Eventually, we proof Lemma 1 using
Property 1.
Now suppose (aS , aE ) forms a natural equilibrium with equilibrium payoff vS , vE . Define
F to be the space of all functions




ǩ


X
βπ(ιǩ , č, ǩ)
fE : (n1 , . . . , nǩ ) :
ni ≤ 2 × [ĉ, č] × K → 0,
,


1
−
β
i=1
and T a : F → F with
For any k 1 , k 2 ∈ {0, 1, . . . , ǩ}, if k 1 ≥ k 2 ,
(
a

2

1

(T fE )(ιk1 + ιk2 , c, k ) = max 0, aS (ιk1 + ιk2 , c, k )

ǩ
ǩ X
X

Πk1 ,i Πk2 ,j f˜E (ιi + ιj , c, i)

i=k1 j=k2

+(1 − aS (ιk1 + ιk2 , c, k 2 ))

ǩ
X

)
Πk1 ,i f˜E (ιi , c, i)

i=k1
0

= max 0, aS (ιk1 + ιk2 , c, k )E[E[f˜E (ιK 10 + ιK 20 , c, K 1 )|K 2 = k 2 ]|K 1 = k 1 ]
0
+(1 − aS (ιk1 + ιk2 , c, k 2 ))E[f˜E (ιK 10 , c, K 1 )|K 1 = k 1 ] .
(1)
2



1

If k 1 < k 2 ,


ǩ X
ǩ
 X

(T a fE )(ιk1 + ιk2 , c, k 1 ) = max 0,
Πk1 ,i Πk2 ,j f˜E (ιi + ιj , c, i)


i=k1 j=k2
n
o
10
2
2
1
1
˜
0
0
= max 0, E[E[fE (ιK 1 + ιK 2 , c, K )|K = k ]|K = k ] .(2)
With f˜E (ιk1 + ιk2 , c, k 1 ) denoting the post-type-transition payoff associate with post-entry
payoff fE when current demand is c, the firm of interest has progressed to type-k 1 , and its
rival has progressed to type-k 2 .
f˜E (ιk1 + ιk2 , c, k 1 ) ≡ βE[π(ιk1 + ιk2 , C 0 , k 1 ) + aE (ιk1 + ιk2 + ι1 , C 0 )fE (ιk1 + ιk2 + ι1 , C 0 , i)
+ [1 − aE (ιk1 + ιk2 + ι1 , C 0 )] fE (ιk1 + ιk2 , C 0 , i)|C = c]
where, for definiteness, aE (ιk1 + ιk2 + ι1 , c) ≡ 0 if k 1 , k 2 > 0.
The space F is a Banach space (complete with the supremum norm). T a satisfies Blackwell’s sufficient properties for a contraction mapping. The equilibrium payoff vE is the unique
fixed point of T a . We prove that vE satisfies Properties 1–4 for all k by showing that the
fixed point of T a lies in the space in which all functions satisfy these properties. To this end,
we gradually narrow down the space that this fixed point is in, to eventually reach the space
of all functions that satisfy Properties 1–4 for all k.
First, denote a subspace of F in which any functions fE satisfy fE ≥ vE as F 0 . Because
F 0 is also a non-empty Banach space and vE ∈ F 0 , T a : F 0 → F 0 . We henceforth focus on
F 0.
Before proceeding to verify the properties, we introduce a Lemma which we will use repeatedly. Recall that firm types’ evolution has the first-order stochastic dominance property,
as stated in Assumption 3. The following Lemma exploits this property
Lemma 1. X, Y are random variables with densities F and G respectively. If X first-order
stochastically dominates Y , then E[h(X)] ≥ E[h(Y )] for all weakly increasing function h.
Prove Property 2 for k = ǩ. We take two steps to prove Property 2 for k = ǩ.
(i). Consider Fǩ1 , a subspace of F 0 in which any function fE satisfies (T a fE )(2ιǩ , ·, ǩ) =
vE (2ιǩ , ·, ǩ) and fE (2ιǩ , ·, ǩ) ≤ fE (ιǩ + ιx , ·, ǩ) for 0 ≤ x ≤ ǩ. This is also a complete
metric space. Since at least the function fE∗ which satisfies fE∗ (2ιǩ , ·, ǩ) = vE (2ιǩ , ·, ǩ)
and fE∗ (2ιǩ , ·, ǩ) = fE∗ (ιǩ + ιx , ·, ǩ) for 0 ≤ x ≤ ǩ is in Fǩ1 , this subspace is nonempty.

2

We aim to prove that T a : Fǩ1 → Fǩ1 . Since vE is the unique fixed point of T a , this
result ensures that vE ∈ Fǩ1 and thus vE (2ιǩ , ·, ǩ) ≤ vE (ιǩ , ·, ǩ).
In a symmetric equilibrium, any rival’s exit implies that both firms expect non-positive
payoffs from continuing. Therefore, firms earn positive expected payoffs only when
both firms continue with probability 1. So
vE (2ιǩ , c, ǩ) ≤ max{0, βE[π(2ιǩ , C 0 , ǩ)+vE (2ιǩ , C 0 , ǩ)|C = c]} = max{0, f˜E (2ιǩ , c, ǩ)}.
Note that for all fE ∈ Fǩ1 , we have for any (aS , aE ), f˜E (ιǩ + ιx , ·, ǩ) ≥ f˜E (2ιǩ , ·, ǩ) for
0 ≤ x ≤ ǩ. Therefore, E[f˜E (ιǩ + ιX 0 , ·, ǩ)|X = x] ≥ f˜E (2ιǩ , ·, ǩ), and f˜E (ιǩ , ·, ǩ) ≥
f˜E (2ιǩ , ·, ǩ). Then, for any 0 ≤ x ≤ ǩ, we have
(T a fE )(ιǩ + ιx , c, ǩ)
n
o
= max 0, aS (ιǩ + ιx , c, x)E[f˜E (ιǩ + ιX 0 , c, ǩ)|X = x] + (1 − aS (ιǩ + ιx , c, x))f˜E (ιǩ , c, ǩ)
≥ max{0, f˜E (2ιǩ , c, ǩ)}
≥ vE (2ιǩ , c, ǩ)
= (T a fE )(2ιǩ , c, ǩ)
Therefore, T a : Fǩ1 → Fǩ1 and vE (2ιǩ , ·, ǩ) ≤ vE (ιǩ + ιx , ·, ǩ) for 0 ≤ x ≤ ǩ. This further
ensures that vS (2ιǩ , ·, ǩ) ≤ vS (ιǩ , ·, ǩ) for any aS , aE . Then, an analogous argument to
the one on the simultaneous-move survival game in Section ?? leads to




vE (2ιǩ , c, ǩ) = max 0, βE π(2ιǩ , C 0 , ǩ) + vE 2ιǩ , C 0 , ǩ C = c .

(3)

The right-hand-side of (3) defines a contraction mapping with a unique fixed point
vE (2ιǩ , ·, ǩ). So
(T a fE )(2ιǩ , c, ǩ) = max{0, f˜E (2ιǩ , c, ǩ)}.
(ii). We move on to a subspace of Fǩ1 , which we denote by Fǩ2 . In this subspace, any function
fE satisfies that fE (ιǩ + ιx , ·, x) is weakly increasing in x for 0 ≤ x ≤ ǩ. We will further
show that T a : Fǩ2 → Fǩ2 . Note that for fE ∈ Fǩ2 , f˜E (ιǩ + ιx , ·, x) is weakly increasing
0
0
in x as well. For any k 1 , k 2 such that 1 ≤ k 1 ≤ k 2 ≤ ǩ, we use K 1 , K 2 to denote
0
the random variables for the types succeeding K 1 = k 1 , K 2 = k 2 respectively. K 2
0
stochastically dominates K 1 . So, according to Lemma 1, f˜E shares the monotonicity
3

0
0
property as fE in Fǩ2 , E[f˜E (ιǩ + ιK 10 , ·, K 1 )|K 1 = k 1 ] ≤ E[f˜E (ιǩ + ιK 20 , ·, K 2 )|K 2 = k 2 ].
Therefore,

o
n
0
(T a fE )(ιǩ + ιk1 , c, k 1 ) = max 0, E[f˜E (ιǩ + ιK 10 , c, K 1 )|K 1 = k 1 ]
o
n
20
2
2
˜
≤ max 0, E[fE (ιǩ + ιK 20 , c, K )|K = k ]
= (T a fE )(ιǩ + ιk2 , c, k 2 )
This result guarantees that T a : Fǩ2 → Fǩ2 . Therefore, vE (ιǩ + ιx , ·, x) is weakly increasing in x and Property 2 is satisfied for k = ǩ. Because in natural equilibrium,
vS (ιǩ + ιx , c, x) = βE [π(ιǩ + ιX 0 , C 0 , X 0 ) + vE (ιǩ + ιX 0 , C 0 , X 0 ) C = c, X = x] .
together with Assumption 1, it is also true that vS (ιǩ + ιx , ·, x) is weakly increasing in
x, and so is the survival rule aS (ιǩ + ιx , ·, x).
Prove Property 1 for k = ǩ. Next, we focus on a subspace of Fǩ2 , denoted by Fǩ3 . In this
subspace any function fE must satisfy that fE (ιǩ + ιx , ·, ǩ) is weakly decreasing in x for any
0 ≤ x ≤ ǩ. Note that for fE ∈ Fǩ3 , f˜E (ιǩ +ιx , ·, ǩ) is weakly decreasing in x as well. Therefore,
for any 0 ≤ k 1 ≤ k 2 ≤ ǩ, E[f˜E (ιǩ + ιK 20 , ·, ǩ)|K 2 = k 2 ] ≤ E[f˜E (ιǩ + ιK 10 , ·, ǩ)|K 1 = k 1 ]. Then,
using the monotonicity of survival rule that we derived above,
(T a fE )(ιǩ + ιk2 , c, ǩ)
n
o
= max 0, aS (ιǩ + ιk2 , c, k 2 )E[f˜E (ιǩ + ιK 20 , c, ǩ)|K 2 = k 2 ] + (1 − aS (ιǩ + ιk2 , c, k 2 ))f˜E (ιǩ , c, ǩ)
n
o
1
2
2
1
˜
˜
≤ max 0, aS (ιǩ + ιk1 , c, k )E[fE (ιǩ + ιK 20 , c, ǩ)|K = k ] + (1 − aS (ιǩ + ιk1 , c, k ))fE (ιǩ , c, ǩ)
n
o
≤ max 0, aS (ιǩ + ιk1 , c, k 1 )E[f˜E (ιǩ + ιK 10 , c, ǩ)|K 1 = k 1 ] + (1 − aS (ιǩ + ιk1 , c, k 1 ))f˜E (ιǩ , c, ǩ)
= (T a fE )(ιǩ + ιk1 , c, ǩ)
Therefore, T a : Fǩ3 → Fǩ3 and vE (ιǩ + ιx , ·, ǩ) is weakly decreasing in x, so Property 1 is
satisfied for k = ǩ.
Prove Property 3 for k = ǩ. Before proving this property, we need to prove Properties 2
and 1 for k = ǩ − 1. We skip the details because later we will demonstrate how to do so for
3
any k. Now suppose that we have verified these two properties for k = ǩ − 1, then vE ∈ Fǩ−1
3
where Fǩ−1
is defined analogously to Fǩ3 . Hence, for 0 ≤ x ≤ ǩ, vE (ιǩ−1 + ιx , ·, ǩ − 1) is
weakly decreasing in x and vE (ιǩ−1 + ιx , ·, x) is weakly increasing in x. Then, denote the
4

3
subspace of Fǩ−1
in which any fE functions such that fE (ιǩ + ιx , ·, x) ≤ fE (ιǩ−1 + ιx , ·, x) for
4
all x such that 0 ≤ x ≤ ǩ − 1 by Fǩ−1
.
4
, by Lemma 1, we have
Then, f˜E (ιǩ + ιx , ·, x) ≤ f˜E (ιǩ−1 + ιx , ·, x) holds for fE ∈ Fǩ−1
o
n
(T a fE )(ιǩ + ιx , c, x) = max 0, E[f˜E (ιǩ + ιX 0 , c, X 0 )|X = x]
n
o
0
˜
≤ max 0, E[E[fE (ιK 0 + ιX 0 , c, X )|X = x]|K = ǩ − 1]

= (T a fE )(ιǩ−1 + ιx , c, x)
4
4
and vE (ιǩ + ιx , ·, x) ≤ vE (ιǩ−1 + ιx , ·, x) for all x such that
→ Fǩ−1
Therefore, T a : Fǩ−1
0 ≤ x ≤ ǩ − 1. In particular, this result ensures that aE (ιǩ + ι1 , ·) ≤ aE (ιǩ−1 + ι1 , ·).
4
Prove Property 4 for k = ǩ. Define a subspace of Fǩ−1
in which any function fE satisfies
5
fE (ιǩ−1 , ·, ǩ − 1) ≤ fE (ιǩ , ·, ǩ), as Fǩ−1
. Because aE (ιǩ + ι1 , ·) ≤ aE (ιǩ−1 + ι1 , ·), we have
˜
˜
fE (ιǩ−1 , ·, ǩ − 1) ≤ fE (ιǩ , ·, ǩ) and then (T a fE )(ιǩ−1 , ·, ǩ − 1) ≤ (T a fE )(ιǩ , ·, ǩ). Therefore,
5
5
T a : Fǩ−1
→ Fǩ−1
and hence vE (ιǩ , ·, ǩ) ≥ vE (ιǩ−1 , ·, ǩ − 1).
Now suppose that for any k ≤ ǩ, we have established the following results

Result 1. vE satisfies Property 1 for k + 1, k + 2, . . . , ǩ. That is, vE (ιk+1 + ιx , ·, x), vE (ιk+2 +
ιx , ·, x), . . . , vE (ιǩ + ιx , ·, x) are all weakly increasing in x, 0 ≤ x ≤ ǩ.
Result 2. vE satisfies Property 2 for k + 1, k + 2, . . . , ǩ. That is, vE (ιx + ιk+1 , ·, k + 1), vE (ιx +
ιk+2 , ·, k + 2), . . . , vE (ιx + ιǩ , ·, ǩ) are all weakly decreasing in x, 0 ≤ x ≤ ǩ.
Result 3. vE satisfies Property 3 for k + 1, k + 2, . . . , ǩ. That is, vE (ιk+1 + ιx , ·, x) ≥
vE (ιk+2 + ιx , ·, x) ≥ . . . ≥ vE (ιǩ + ιx , ·, x) for all 1 ≤ x ≤ k.
Result 4. vE satisfies Property 4 for k + 1, k + 2, . . . , ǩ. That is, vE (ιk+1 , ·, k + 1) ≤
vE (ιk+2 , ·, k + 2) ≤ . . . ≤ vE (ιǩ , ·, ǩ).
We then need to prove that vE satisfies Properties 1-4 for k.
Prove Property 2 for k. We follow three steps to achieve this end.
5
(i). First, consider Fk1 , the subspace of Fk+1
in which any function f satisfies that (T a fE )(2ιk , ·, k) =
vE (2ιk , ·, k), fE (ιx + ιk , ·, k) is weakly decreasing in x, k ≤ x ≤ ǩ, and fE (2ιk , ·, k) ≤
fE (ιk + ιx , ·, k), for all 0 ≤ x ≤ k. Note that at least a function fE∗ with fE∗ (2ιk , ·, k) =
vE (2ιk , ·, k) = fE∗ (ιk + ιx , ·, k) for all x is in Fk1 , so Fk1 is nonempty. For any fE ∈ Fk1 ,
f˜E shares the properties with fE and hence also has the properties stated in Results

5

1–4. To prove that (T a fE )(ιx + ιk , ·, k) is weakly decreasing in x, k ≤ x ≤ ǩ, consider
the following cases for any k 1 , k 2 such that k ≤ k 1 < k 2 ≤ ǩ.
(a) If k < k 1 < k 2 , according to Lemma 1, E[E[f˜E (ιK 10 +ιK 0 , ·, K 0 )|K = k]|K 1 = k 1 ] ≥
E[E[f˜E (ιK 20 + ιK 0 , ·, K 0 )|K = k]|K 2 = k 2 ]. Thus, from equation (2), (T a fE )(ιk2 +
ιk , c, k) ≤ (T a fE )(ιk1 + ιk , c, k).
(b) If k = k 1 < k 2 , first observe that
n
o
0
2
2
˜
0
(T fE )(ιk2 + ιk , c, k) = max 0, E[E[fE (ιK 2 + ιK 0 , c, K )|K = k]|K = k ]
n
o
≤ max 0, E[E[f˜E (ιK 10 + ιK 0 , c, K 0 )|K = k]|K 1 = k]
a

Then, because (i) for all fE ∈ Fk1 , f˜E (2ιk , ·, k) ≤ f˜E (ιk , ·, k) and f˜E (2ιk , ·, k) ≤
f˜E (ιk + ι1 , ·, k), and (ii) Result 2, we obtain that E[f˜E (ιk + ιK 0 , ·, K 0 )|K = k] ≤
E[f˜E (ιK 0 , ·, K 0 )|K = k], and further E[E[f˜E (ιK 10 + ιK 0 , ·, K 0 )|K = k]|K 1 = k] ≤
E[f˜E (ιK 0 , ·, K 0 )|K = k]. Then,
(T a fE )(ιk2 + ιk , c, k) ≤ max{0, aS (2ιk , c, k)E[E[f˜E (ιK 10 + ιK 0 , c, K 0 )|K = k]|K 1 = k 1 = k]
+(1 − aS (2ιk , c, k))E[f˜E (ιK 0 , c, K 0 )|K = k]}
= (T a fE )(ιk1 + ιk , c, k)
To prove that (T a fE )(2ιk , ·, k) ≤ (T a fE )(ιk + ιx , ·, k), for all 0 ≤ x ≤ k, note that,
(T a fE )(2ιk , c, k) = vE (2ιk , c, k)
≤ max {0, vS (2ιk , c, k)}
n
o
≤ max 0, E[E[f˜E (ιK 10 + ιK 0 , c, K 0 )|K = k]|K 1 = k]
≤ max{0, aS (ιk + ιx , c, x)E[E[f˜E (ιX 0 + ιK 0 , c, K 0 )|K = k]|X = x]
+(1 − aS (ιk + ιx , c, x))E[f˜E (ιK 0 , c, K 0 )|K = k]}
= (T a fE )(ιk + ιx , c, k)
The first inequality is due to equilibrium symmetric; for two type-k firm, either firm’s
equilibrium payoff is bounded by payoff from joint continuation. The second inequality
is because fE ∈ F 0 so fE ≥ vE . These results show that T a : Fk1 → Fk1 . An familiar
argument on the simultaneous-move survival game leads to
vE (2ιk , c, k) = max {0, vS (2ιk , c, k)} .
6

(4)

The right-hand-side of (4) defines a contraction mapping with a unique fixed point
v(2ιk , ·, k),
n
o
a
0
1
˜
0
(T fE )(2ιk , c, k) = max 0, E[E[fE (ιK 1 + ιK 0 , c, K )|K = k]|K = k] .
(ii). We move on to a subspace of Fk1 , which we denote by Fk2 . Any function fE in this
subspace satisfy that fE (ιk +ιx , ·, x) is weakly increasing with x. Note that for fE ∈ Fk2 ,
f˜E (ιk + ιx , ·, x) is weakly increasing in x as well. Combine it with Result 1, and then
we have that f˜E (ιd + ιx , ·, x) is weakly increasing in x for all d such that k ≤ d ≤ ǩ.
Therefore, E[f˜E (ιK 0 + ιx , ·, x)|K = k] is weakly increasing in x. For any k 1 , k 2 such that
1 ≤ k 1 ≤ k 2 ≤ ǩ, according to Lemma 1,
0
0
[E[f˜E (ιK 0 + ιK 10 , ·, K 1 )|K = k]|K 1 = k 1 ] ≤ [E[f˜E (ιK 0 + ιK 20 , ·, K 2 )|K = k]|K 2 = k 2 ].

(5)
We then consider the following cases.
(a) For k 1 ≤ k 2 ≤ k, from equation (2), we can observe that equation (5) leads to
(T a fE )(ιk + ιk1 , c, k 1 ) ≤ (T a fE )(ιǩ + ιk2 , c, k 2 ).
(b) For k < k 1 ≤ k 2 ≤ ǩ, from Result 3, we have aS (ιk + ιk1 , ·, k) ≥ aS (ιk + ιk2 , ·, k).
Also, from Result 2 and Lemma 1,
0
0
[E[f˜E (ιK 0 + ιK i0 , ·, K i )|K = k]|K i = k i ] ≤ E[f˜E (ιK i0 , ·, K i )|K i = k i ], i = 1, 2.

From Result 4 and Lemma 1,
0

0

E[f˜E (ιK 20 , ·, K 2 )|K 2 = k 2 ] ≤ E[f˜E (ιK 10 , ·, K 1 )|K 1 = k 1 ].
Using equation (1), we can show (T a fE )(ιk + ιk1 , c, k 1 ) ≤ (T a fE )(ιk + ιk2 , c, k 2 ) by
exploiting the inequalities.
(c) For k 1 ≤ k ≤ k 2 ≤ ǩ, similarly we can show (T a fE )(ιk + ιk1 , c, k 1 ) ≤ (T a fE )(ιk +
ιk2 , c, k 2 ) with the above results.
This result guarantees that T a : Fk2 → Fk3 . Therefore, any equilibrium payoff must
satisfy that vE (ιk + ιx , ·, x) is weakly increasing in x for all 1 ≤ x ≤ ǩ, which leads to
the same monotonicity for vS and the equilibrium survival rule.

7

Prove Property 1 for k. Next, we focus on a subspace of Fk3 , denoted by Fk3 . In this
subspace, any function fE satisfies that fE (ιx + ιk , ·, k) is weakly decreasing in x, 0 ≤ x ≤ k.
Note that for fE ∈ Fk3 , f˜E (ιx + ιk , ·, k) is also weakly decreasing in x, 0 ≤ x ≤ k. Combine it
with Result 2, and then we have that f˜E (ιx + ιd , ·, d) is weakly decreasing in x, 0 ≤ x ≤ ǩ and
for all d such that k ≤ d ≤ ǩ. Therefore, E[f˜E (ιK 0 + ιx , ·, K 0 )|K = k] is weakly decreasing in
x. For any k 1 , k 2 such that 0 ≤ k 1 ≤ k 2 ≤ ǩ, Lemma 1 implies that
[E[f˜E (ιK 0 + ιK 10 , ·, K 0 )|K = k]|K 1 = k 1 ] ≥ [E[f˜E (ιK 0 + ιK 20 , ·, K 0 )|K = k]|K 2 = k 2 ].
Also, we have aS (ιk +ιk1 , ·, k 1 ) ≤ aS (ιk +ιk2 , ·, k 2 ). Therefore, it must be true that (T a fE )(ιk +
ιk2 , c, k) ≤ (T a fE )(ιk + ιk1 , c, k). So T a : Fk3 → Fk3 and the equilibrium payoff vE (ιx + ιk , ·, k)
is weakly decreasing in x, 0 ≤ x ≤ ǩ.
Prove Property 3 for k. Next, we further look into a subspace of Fk3 , denoted by Fk4 , in
which any function fE satisfies that fE (ιk + ιx , ·, x) ≤ fE (ιk+1 + ιx , ·, x) for all x < k. Note
that Result 2 and Property 1 ensure that fE (ιk + ιx , ·, x) ≤ fE (ιk+1 + ιx , ·, x) for all x ≥ k,
so for any fE ∈ Fk3 , f˜E (ιk+1 + ιx , ·, x) ≤ f˜E (ιk + ιx , ·, x) for all x. Combine it with Result
3, and then we have E[f˜E (ιk1 + ιX 0 , ·, X 0 )|X = x] is weakly decreasing in k 1 for k ≤ k 1 ≤ ǩ.
According to Lemma 1,
E[E[f˜E (ιK 10 + ιX 0 , ·, X 0 )|X = x]|K 1 = k 1 ] ≤ E[E[f˜E (ιK 0 + ιX 0 , ·, X 0 )|X = x]|K = k].
Then using equation (2) we can show that (T a fE )(ιk1 + ιx , c, x) ≤ (T a fE )(ιk + ιx , c, x) for any
x < k. Therefore, T a : Fk4 → Fk4 and vE (ιk1 + ιx , c, x) ≤ vE (ιk + ιx , c, x) for all x and all k 1
such that k ≤ k 1 ≤ ǩ. In particular, this result ensures that aE (ιk+1 + ι1 , ·) ≤ aE (ιk + ι1 , ·).
Prove Property 4 for k. Finally, define a subspace of Fk4 , in which any function fE
satisfies fE (ιk , ·, k) ≤ fE (ιk+1 , ·, k + 1), as Fk5 . Because aE (ιk+1 + ι1 , ·) ≤ aE (ιk + ι1 , ·), we
have f˜E (ιk , ·, k) ≤ f˜E (ιk+1 , ·, k + 1) as well. Combine it with Result 4, and then we have
that f˜E (ιk1 , ·, k 1 ) is weakly increasing in k 1 for k ≤ k 1 ≤ ǩ. Using Lemma 1, we have
(T a fE )(ιk , c, k) ≤ (T a fE )(ιk+1 , c, k + 1) so T a : Fk5 → Fk5 and Property 4 is verified for k.
This completes the verification for the sufficient properties for any arbitrary k. Since
(aS , aE ) is also arbitrarily chosen, any natural equilibrium payoff function vE must satisfy
Properties 1, 2, and 4. Then we can prove Lemma 1.

8

Prove Lemma 1. For any strategy (aS , aE ), as a special case of Property 1, vE (2ιk , c, k) ≤
vE (ιk , c, k) for any k ≤ ǩ. To prove vS (2ιk , c, k) ≤ vS (ιk , c, k), note that
vS (2ιk , c, k) = E[E[ṽEa (ιK 0 + ιK 10 , c, K 0 )|K = k]|K 1 = k]
vS (ιk , c, k) = E[ṽEa (ιK 0 , c, K 0 )|K = k],
where ṽEa is defined analogously as f˜S . For any k 1 , k 2 ≥ k, Property 1 ensures that vE (ιk1 +
ιk2 , c, k 1 ) ≤ vE (ιk1 + ι1 , c, k 1 ) ≤ vE (ιk1 , c, k 1 ), and ṽEa (ιk1 + ιk2 , c, k 1 ) ≤ ṽEa (ιk1 + ι1 , c, k 1 ) ≤
ṽEa (ιk1 , c, k 1 ). Therefore E[E[vS (ιK 0 + ιK 10 , c, K 0 )|K = k]|K 1 = k] ≤ E[vS (ιK 0 , c, K 0 )|K].

I.2

Details for the Proof of Proposition 1

Proof. We provide here the details to prove wE (ιk1 + ιk2 , ·, k 1 ) ≥ wE (ιk1 + ιk2 , ·, k 2 ). Define
F to be the space of all functions




ǩ


X
βπ(ιǩ , č, ǩ)
,
fE : (n1 , . . . , nǩ ) :
ni ≤ 2 × [ĉ, č] × K → 0,


1−β
i=1

and T α : F → F with
(
(T α fE )(ιk1 + ιk2 , c, k 1 ) =

(Tk1 ,k2 f )(C), f (C) ≡ g(ιk1 + ιk2 , c, k 2 )
(Tk1 f )(C, k 2 ), f (C, k 2 ) ≡ g(ιk1 + ιk2 , c, k 2 )

Thus, T α is exactly assembled by Tk1 ,k2 and Tk1 in Algorithm 1, and wE
Algorithm 1 is the unique fixed point of T α . Now consider a subspace of
denote as F N . In this space, any function fE satisfies that fE ≤ wE , fE (ιk1
fE (ιk1 + ιk2 , ·, k 2 ) for all k 1 > k 2 .
We aim to prove T α : F N → F N . For all fE ∈ F N , f˜E ∈ F N as well.
following cases

if k 1 ≤ k 2
if k 1 > k 2

)
.

computed by
F, which we
+ ιk2 , ·, k 1 ) ≥
Consider the

(i). If Algorithm 1 computes αS (ιk1 + ιk2 , c, k 2 ) = 1, then Algorithm 1 also prescribes
αS (ιk1 + ιk2 , c, k 1 ) = 1. Substitute these survival rules into Equation (1) and use
Lemma 1 again, we obtain that (T α fE )(ιk1 + ιk2 , c, k 1 ) ≥ (T α fE )(ιk1 + ιk2 , c, k 2 ).
(ii). If Algorithm 1 computes αS (ιk1 + ιk2 , c, k 2 ) = 0, then it must be the case that wE (ιk1 +
ιk2 , c, k 2 ) = 0. For any fE ∈ F, fE (ιk1 + ιk2 , c, k 2 ) ≤ wE (ιk1 + ιk2 , c, k 2 ) = 0.
Since wE (ιk1 + ιk2 , c, k 2 ) = (T α∞ fE )(ιk1 + ιk2 , c, k 2 ) and T α is a monotone operator,
(T α fE )(ιk1 + ιk2 , c, k 2 ) ≤ wE (ιk1 + ιk2 , c, k 2 ) = 0. Thus, (T α fE )(ιk1 + ιk2 , c, k 1 ) ≥ 0 ≥
(T α fE )(ιk1 + ιk2 , c, k 2 ).
9

By point-wise comparison, we conclude that T α : F N → F N hence wE (ιk1 + ιk2 , ·, k 1 ) ≥
wE (ιk1 + ιk2 , ·, k 2 ) for all k 1 > k 2 . This means that whenever wE (ιk1 + ιk2 , ·, k 2 ) > 0, wE (ιk1 +
ιk2 , c, k 1 ) > 0 as well.

II
II.1

Computational Techniques
Computing A Firm’s Beliefs about Next Period’s State

The computation of the expectation in (1) requires the distribution of MS conditional on ME ,
given that the firm of interest survives and that all other firms use the common strategy aS .
Denote the density (with respect to the appropriate dominating measure) of this distribution
P
P
P
with pmS (·|ME = mE ). Decompose mS = i miS ≡ i mS,i ιi and mE = i mE,i ιi , with
mS,i the number of firms who have type-i in the current period and continue to next period,
and mE,i the number of firms who are active when the current period’s continuation decisions
are made. Then, because MSi ,. . . , MSǩ are independent conditional on ME and given that the
firm of interest survives, pmS (·|ME = mE ) is the convolution of the corresponding conditional
densities pmiS (·|ME = mE ) of miS ; i = 1, . . . , ǩ. Denote m̃i ≡ mE,i − I(i = k) and m̃S,i ≡
mS,i −I(i = k). Note that m̃i is the number of type-i firms active when continuation decisions
are made in the current period, excluding the firm of interest; and m̃S,i is the number of
firms who have type-i in the current period and continue to next period, excluding the firm
of interest. Then, for mS,i such that 0 ≤ mS,i ≤ mE,i , we have that


m̃i
pmiS (·|ME = mE ) =
aS (mE , c, i)m̃S,i (1 − aS (mE , c, i))m̃i −m̃S,i
m̃S,i
Computing the expectation in (2) requires the distribution of (N 0 , M 0 , C 0 , K 0 ) conditional
on MS , C, K, given that all potential entrants use the common strategy aE . Denote the
density of this distribution with p (·|MS , C, K). Conditional on (N 0 , C 0 ), M 0 is independent
of (K 0 , MS , C, K); conditional on (K 0 , MS , K), N 0 is independent of C 0 ; conditional on C, C 0 is
independent of (K 0 , MS , C, K); and conditional on K, K 0 is independent of HS . Consequently,
p (n0 , m0 , c0 , k 0 |MS = mS , C = c, K = k) =pM (m0 |N 0 = n0 , C 0 = c0 ) × pN (n0 |K 0 = k 0 , MS = mS , K = k)
× q(c0 |C = c) × Πk0 k .
Here, pM (·|N 0 , C 0 ) is the density of next period’s post-entry market structure M 0 , conditional
on next period’s pre-entry market structure N 0 and demand state C 0 . And, pN (·|K 0 , MS , K)

10

is the density of next period’s pre-entry market structure N 0 conditional on MS , given that
the firm of interest survives with productivity type K 0 .
First, note that


1 − aE (m0 + ι1 , c0 )
if M 0 = n0 ;



 (1 − a (m0 + (m0 − n0 + 1)ι , c0 )) if m0 > n0
1
E
1
1
1
1
pM (m0 |N 0 = n0 , C 0 = c0 ) =
Qm01 −n01
0
0
0

× j=1 aE (n + jι1 , c )
and m2 = n02 , . . . , m0ǩ = n0ǩ ;



 0
otherwise.
P
Next, consider pN (·|K 0 , MS , K). Decompose n0 = i ni , with ni the contribution to next
period’s pre-entry market structure by the mS,i firms who are of type-i in the previous period
and choose to continue. Then, because N 1 ,. . . , N ǩ are independent conditional on MS and
given that the firm of interest survives with productivity type K 0 , pN (·|K 0 , MS , K) is the
convolution of the corresponding conditional densities pN i (·|K 0 , MS , K) of N i ; i = 1, . . . , ǩ.
Denote ñi (k, k 0 ) ≡ ni − I(i = k)ιk0 . This is the contribution of the mS,i firms excluding
the firm of interest, to next period’s pre-entry market structure. Then, for mS such that
m̃S,i ≥ 0, we have that
k

0

0



pN i n |K = k , MS = mS , K = k =

ǩ 
Y

Pǩ

i0 =i
i
if Ñm
= 0 for all m < i, ñim ≥ 0 for all m ≥ i, and

II.2
II.2.1

0 
i
ñii0 (k,k0 )
m=i0 ñm (k, k )
Π
i0 i
Ñii0 (k, k 0 )

P

i0

ñii0 ≤ m̃i ; and zero otherwise.

Constructing the Type Transition Matrices in Matlab
The Problem

Given any finite m̌ and ǩ and a ǩ × ǩ transition matrix Π, or the triple (ǩ, m̌, Π), we need
to compute all the transition matrices for 1, 2, . . . , m̌-firm market structures, conditioning
on all realized exits and one surviving firm’s type transition. Since any single firm’s type
transition is characterized by Π, the non-trivial part of this problem is computing all the
transition matrices for 1, 2, . . . , m̌ − 1-firm market structures. W.L.O.G., we discuss how to
construct m̌ such matrices for the triple (ǩ, m̌ + 1, Π). For every ordering of all possible
market structures with m firms, m ∈ {1, . . . , m̌}, there is a representation of transition
matrix corresponding to that ordering. We henceforth focus on the transition matrices for
OL-ordered market structures. For any m, we denote the transition matrix as Πm .

11

II.2.2

The Dimensionality

For the triple (ǩ, m̌ + 1, Π), we know that if there are m surviving firms, the OL-ordered
ǩ−1)!
elements. Therefore, Πm ’s dimension
sequence of all possible market structures has (m+
m!(ǩ−1)!
is

(m+ǩ−1)!
m!(ǩ−1)!

II.2.3

×

(m+ǩ−1)!
.
m!(ǩ−1)!

Recursive Construction of Πm

We recursively construct Πm using Πm−1 and Π1 , for all 2 ≤ i ≤ m̌. Note that Π1 = Π.
To describe the construction, we very often use examples. We use Italic to distinguish the
discussion on general case and the discussion on an example.
The link between an element in Πm and the elements in Πm−1 and Π1 is explained below.
(i). The (a, b) element in Πm corresponds to a transition probability from an initial m-firm
market which has index a in the m-firm OL sequence to a destined m-firm market with
index b.
(ii). Suppose that i is the index for the highest type in the initial market a. Taking out one
type-i firm from the a leaves an initial m − 1-firm market structure. Suppose that this
market structure has index c in the m − 1-firm OL sequence.
(iii). Next, suppose that the type-i firm transits to one of the possible types j in the destined
market b. This transition has probability Πi,j . 1
(iv). Excluding this type-j firm from the destined market leaves a destined m−1-firm market.
Suppose that this market has index d in the m − 1-firm OL sequence.
(v). The transition between the initial and the destined m − 1-firm markets is characterized
m−1
by Πc,d
.
(vi). The transition from the initial m-firm market to the destined one then has the probability
Πm
a,b =

X

Πi,j Πm−1
c,d .

j:bj >0
1

Note that we also consider the impossible regression in the types here and throughout this notes. So, we
consider all j’s including those are lower than i. In such cases, Πi,j = 0.

12

Example Suppose that ǩ = 3, m̌ = 2. In slightly abused notations, we denote the types as
L, M, H. Π2 is a 6 × 6 matrix. Now, take its (2, 3) element as an example to demonstrate
the above procedure.
(i). This (2, 3) element corresponds to the transition from the market HM to HL.
(ii). Taking out the firm with the highest type H from the initial market HM leaves an
initial 1-firm market M , which has index 2 in the 1-firm OL sequence.
(iii). Suppose that the H firm transits to H in the destined market. This transition has
probability Π1,1 .
(iv). Excluding the H firm from the destined market leaves a destined 1-firm market L, which
has index 3 in the 1-firm OL sequence.
(v). The transition between the initial and the destined 1-firm market M and L is characterized by Π12,3 .
(vi). Note that H can also transit to L (with 0 probability), the transition from the initial
market HM to the destined HL then has the probability
Π22,3 = Π1,1 Π12,3 + Π1,3 Π12,1 .
P
m−1
In short-hand notations, we rewrite the equation Πm
using indices
ab =
j:bj >0 Πij Πcd
P
only: (a, b) := j:bj >0 (i, j) × (c, d), with the understanding that (a, b) always indexes the
element in Πm , (i, j) in Π, and (c, d) in Πm−1 . We connect these indices to the objects that
they index.
(i). i indexes the highest type in the market a. Therefore, for each given a, i is unique.
This implies that in each row of Πm , all entries share the same i.
(ii). All j’s indicate all possible types in market b. Therefore, in each column of Πm , all
entries share the same j’s. For any (a, b) entry, there are at most ǩ possible values of
j.
(iii). c indexes the m − 1 market structure resulted by subtracting a type-i firm from the
market a. Therefore, for each (a, b), c is unique and in each row of Πm , all entries share
the same c.

13

(iv). All d’s index all possible m − 1 market structures resulted by subtracting a type-j firm
from the market b. Therefore, in each column of Πm , all entries share the same d’s. For
any (a, b) entry, there are at most ǩ possible values of d.
Henceforth, we call i the first index, all j’s the second indices, c the third, and d’s the
fourth. One may have already developed some intuition that there are regularity patterns
in these indices, which can be used to vectorize the calculation of Πm . Next, we make the
regularity pattern visible to intellectual eyes by an example.
Example As an example, we write Π2 for ǩ = 3, m̌ = 2 using the indices representation.
Again, bear in mind that the first two indices index the element in Π while the last two index
the element in Π1 .

14

15
(3, 1) × (3, 2)
+(3, 2) × (3, 1)

(3, 1) × (3, 1)

MM (2, 1) × (2, 1)

LL

(2, 1) × (2, 2)
+(2, 2) × (2, 1)

HL

(2, 1) × (3, 2)
+(2, 2) × (3, 1)

(1, 1) × (3, 2)
+(1, 2) × (3, 1)

(1, 1) × (3, 1)

HM

(2, 1) × (3, 1)

(1, 1) × (2, 2)
+(1, 2) × (2, 1)

(1, 1) × (2, 1)

HH

ML

HM
(1, 1) × (1, 2)
+(1, 2) × (1, 1)

HH
(1, 1) × (1, 1)

+(3, 3) × (3, 1)

+(2, 3) × (3, 1)
(3, 1) × (3, 3)

+(2, 3) × (2, 1)
(2, 1) × (3, 3)

+(1, 3) × (3, 1)
(2, 1) × (2, 3)

+(1, 3) × (2, 1)
(1, 1) × (3, 3)

+(1, 3) × (1, 1)
(1, 1) × (2, 3)

HL
(1, 1) × (1, 3)

(3, 2) × (3, 2)

(2, 2) × (3, 2)

(2, 2) × (2, 2)

(1, 2) × (3, 2)

(1, 2) × (2, 2)

(1, 2) × (1, 2)

MM

LL

(3, 2) × (3, 3)
+(3, 3) × (3, 2) (3, 3) × (3, 3)

(2, 2) × (3, 3)
+(2, 3) × (3, 2) (2, 3) × (3, 3)

(2, 2) × (2, 3)
+(2, 3) × (2, 2) (2, 3) × (2, 3)

(1, 2) × (3, 3)
+(1, 3) × (3, 2) (1, 3) × (3, 3)

(1, 2) × (2, 3)
+(1, 3) × (2, 2) (1, 3) × (2, 3)

(1, 2) × (1, 3)
+(1, 3) × (1, 2) (1, 3) × (1, 3)

ML

To illustrate the regularity in the above matrix, the first trick is to introduce an auxiliary
ǩ−1)!
+1 in the OL sequence
”impossible destined market structure”, which possesses index (m+
m!(ǩ−1)!
of m-firm market structures. Its impossibility means that no m-firm market structure can
transit to it. For instance, when m = 1, this market structure has index 4. To accommodate
such impossible destined market structure, we can expand Π1 by a fourth column of zeros, so
Π1i,4 = 0, i = 1, 2, 3.
Then, we can rewrite the above matrix as

16

17

HH
HH
(1, 1) × (1, 1)
+(1, 2) × (1, 4)
+(1, 3) × (1, 4)
HM (1, 1) × (2, 1)
+(1, 2) × (2, 4)
+(1, 3) × (2, 4)
HL
(1, 1) × (3, 1)
+(1, 2) × (3, 4)
+(1, 3) × (3, 4)
MM (2, 1) × (2, 1)
+(2, 2) × (2, 4)
+(2, 3) × (3, 4)
ML
(2, 1) × (3, 1)
+(2, 2) × (3, 4)
+(2, 3) × (3, 4)
LL
(3, 1) × (3, 1)
+(3, 2) × (3, 4)
+(3, 3) × (3, 4)

HM
(1, 1) × (1, 2)
+(1, 2) × (1, 1)
+(1, 3) × (1, 4)
(1, 1) × (2, 2)
+(1, 2) × (2, 1)
+(1, 3) × (2, 4)
(1, 1) × (3, 2)
+(1, 2) × (3, 1)
+(1, 3) × (3, 4)
(2, 1) × (2, 2)
+(2, 2) × (2, 1)
+(2, 3) × (3, 4)
(2, 1) × (3, 2)
+(2, 2) × (3, 1)
+(2, 3) × (3, 4)
(3, 1) × (3, 2)
+(3, 2) × (3, 1)
+(3, 3) × (3, 4)

HL
(1, 1) × (1, 3)
+(1, 2) × (1, 4)
+(1, 3) × (1, 1)
(1, 1) × (2, 3)
+(1, 2) × (2, 4)
+(1, 3) × (2, 1)
(1, 1) × (3, 3)
+(1, 2) × (3, 4)
+(1, 3) × (3, 1)
(2, 1) × (2, 3)
+(2, 2) × (2, 4)
+(2, 3) × (2, 1)
(2, 1) × (3, 3)
+(2, 2) × (3, 4)
+(2, 3) × (3, 1)
(3, 1) × (3, 3)
+(3, 2) × (3, 4)
+(3, 3) × (3, 1)

MM
(1, 1) × (1, 4)
+(1, 2) × (1, 2)
+(1, 3) × (1, 4)
(1, 1) × (2, 4)
+(1, 2) × (2, 2)
+(1, 3) × (2, 4)
(1, 1) × (3, 4)
+(1, 2) × (3, 2)
+(1, 3) × (3, 4)
(2, 1) × (2, 4)
+(2, 2) × (2, 2)
+(2, 3) × (3, 4)
(2, 1) × (3, 4)
+(2, 2) × (3, 2)
+(2, 3) × (3, 4)
(3, 1) × (3, 4)
+(3, 2) × (3, 2)
+(3, 3) × (3, 4)

ML
LL
(1, 1) × (1, 4)
(1, 1) × (1, 4)
+(1, 2) × (1, 3) +(1, 2) × (1, 4)
+(1, 3) × (1, 2) +(1, 3) × (1, 3)
(1, 1) × (2, 4)
(1, 1) × (2, 4)
+(1, 2) × (2, 3) +(1, 2) × (2, 4)
+(1, 3) × (2, 2) +(1, 3) × (2, 3)
(1, 1) × (3, 4)
(1, 1) × (3, 4)
+(1, 2) × (3, 3) +(1, 2) × (3, 4)
+(1, 3) × (3, 2) +(1, 3) × (3, 3)
(2, 1) × (2, 4)
(2, 1) × (2, 4)
+(2, 2) × (2, 3) +(2, 2) × (2, 4)
+(2, 3) × (2, 2) +(2, 3) × (2, 3)
(2, 1) × (3, 4)
(2, 1) × (3, 4)
+(2, 2) × (3, 3) +(2, 2) × (3, 4)
+(2, 3) × (3, 2) +(2, 3) × (3, 3)
(3, 1) × (3, 4)
(3, 1) × (3, 4)
+(3, 2) × (3, 3) +(3, 2) × (3, 4)
+(3, 3) × (3, 2) +(3, 3) × (3, 3)

The second trick towards detecting the regularity is to partition the matrix into ǩ rowblocks. In each row-block, all rows correspond to initial market structures that share the
same highest type. In the above matrix, row 1-3 correspond to initial market structures
whose highest type is H, row 4-5 M , and row 6 L. Because of OL, the index of the row-block
is also the index for the highest type. So, in the above matrix, the first block connects to type
1, the second block to type 2, and the third block to type 3.
The first row-block of any Πm matrix contains all initial market structures that has one
(m−1+ǩ−1)!
such market structures.
type-ǩ firm and m−1 other firms with any type. There are (m−1)!(
ǩ−1)!
So the length of the first block is just

(m−1+ǩ−1)!
.
(m−1)!(ǩ−1)!

The second block contains all initial market

structures that has one type-ǩ − 1 firm and m − 1 other firms with type no better than ǩ − 1.
(m−1+ǩ−2)!
There are (m−1)!(
such market structures. So is the length of the second block. In total,
ǩ−2)!
(m−1+ǩ−t)!
there are ǩ such blocks. The t-th block has the length (m−1)!(
.
ǩ−t)!
Now each entry of the matrix has four columns of indices. All columns have the same
length ǩ (3 in this example). Next, we present the regularity on these columns.

(i). Recall that the first index represents the highest type in the initial market structure.
Also recall that in each row-block, all initial market structures share the same highest
type. Therefore, the column of first indices in each entry has a single value, which is
simply the index of the row-block that this entry is in. Therefore, it remains unchanged
for every row in a same block.
(ii). Recall that the second indices represent all the possible types in the destined market
structure. After the introduction of the impossible market structure, the column of the
second indices in each entry is simply (1, . . . , ǩ).
(iii). Recall that the third index represents the m−1 market structure resulted by subtracting
a highest type firm from the initial market structure. Therefore, the column of the third
indices has a single value and remains unchanged for every entry in a same row. In each
row, this value equals the index of the m − 1 market structure resulted by subtracting
a highest type from the initial market structure. In the current example, in row 1,
the 1-firm market structure resulted by subtracting H from HH is H, which has index
number 1 in 1-firm OL sequence. So, in the first row, the third index is 1. In row 2,
the 1-firm market structure resulted by subtracting H from HM is M . So, in the first
row, the third index is 2. Observing the following facts
(a) Within each block, this index increases by 1 each row.
18

(b) The last row in each block corresponds to the most inferior market structure in
the OL sense. Hence, this index in the last row of each block must equal to the
length of the OL sequence of the m − 1-firm market structures. In the current
example, the length is 3, which is the value of the third index in row 3, 5, 6.
(c) The t-th block has the length

(m−1+ǩ−t)!
.
(m−1)!(ǩ−t)!

We can conclude that in the t-th row-block, the third index grows from
(m−1+ǩ−t)!
(m−1)!(ǩ−t)!

+ 1 to

(m−1+ǩ−1)!
(m−1)!(ǩ−1)!

(m−1+ǩ−1)!
(m−1)!(ǩ−1)!

−

row by row.

(iv). Recall that the fourth indices represents the m − 1 market structure resulted by subtracting a highest type firm from the destined market structure. Therefore, the column
of the fourth indices remains unchanged for every entry in a same column. The regularity pattern of this column is more subtle than any of the above columns. We further
explore it. We write down this column in the above example
HH HM HL MM ML LL
1
2
3
4
4
4
4
1
4
2
3
4
4
4
1
4
2
3
This matrix of the fourth indices can be engineered from the following 0-1 matrix.
HH HM HL MM ML LL
1
1
1
0
0
0
0
1
0
1
0
0
0
0
1
0
1
1
We can transform the 1’s in each row of the above matrix into the ordinals of 1’s (the
first 1 stays 1, the second 1 is transformed to 2, the third to 3) and the 0’s into 4 to go
back to the matrix of the fourth indices. This transformation is unique and can always
be done for any matrix of the fourth indices. Hence we focus on constructing the later
matrix, which we simply call the indexing matrix.
Since the fourth indices are related to the destined market structures, we construct the
indexing matrix by exploring Πm from its column dimension. Now, we introduce the
third trick. We partition the Πm matrix into ǩ column-blocks. Analogously to the rowblocks, in each column-block, all columns correspond to destined market structures
that share the same highest type. In the example matrix, column 1-3 correspond to
destined market structures whose highest type is H, column 4-5 M , and column 6 L.
Again, the index of the column-block is also the index for the highest type. So, in the
19

above matrix, the first block connects to type 1, the second block to type 2, and the third
block to type 3. Observing the following facts
(a) The indexing matrix for m = 1 is a ǩ × ǩ identity matrix.
(b) The indexing matrix has ǩ rows. Its (e, f ) element indicates if the destined market
structure f has a type-e firm. If it does, then the (e, f ) element of the indexing
matrix is 1. Otherwise it is 0. In the above example, the (1, 1) element of the
indexing matrix is 1, because the market structure HH contains a type-H firm.
The (2, 1) element is 0, because the market structure HH does not contain a typeM firm.
(c) The indexing matrix can also be partitioned into ǩ column-blocks.
(d) In its t-th column-block, since the highest type in the destined market structure
is t, the first t − 1 rows of the indexing matrix in this block are all 0’s and the t-th
row is full of 1’s. In the above example, the first row is full of 1’s in block 1 and
full of 0’s in block 2.
(e) In its t-th column-block, since the m − 1-firm market structures resulted by
subtracting the highest type firm from the destined market structure are the
(m−1+ǩ−t)!
(m−1+ǩ−1)!
(m−1+ǩ−1)!
− (m−1)!(
+ 1 to (m−1)!(
destined market structures in Πm−1 ,
(m−1)!(ǩ−1)!
ǩ−t)!
ǩ−1)!
from the t + 1-th row onward, the indexing matrix is identical to the

(m−1+ǩ−1)!
(m−1)!(ǩ−1)!

−

(m−1+ǩ−t)!
(m−1)!(ǩ−t)!

(m−1+ǩ−1)!
+ 1 to (m−1)!(
columns of the indexing matrix corresponding to
ǩ−1)!
m − 1. In column-block 1 in the above example, the 1-firm market structures are
H, M , and L, which are the 1,2, and 3 destined market structures of Π1 . Hence,
from the second row onwards in block 1, the indexing matrix is identical to the
1,2, and 3 columns of the indexing matrix for m = 1, which is a 3 × 3 identity
matrix. In column-block 2 in the above example, the 1-firm market structures are
M and L, which are the 2, and 3 destined market structures of Π1 . Hence, the
third row in block 2 of the indexing matrix is identical to the third row and the 2
and 3 columns of the indexing matrix for m = 1.

With all the regularity patterns pointed out as above, we create a Matlab function to
generate all the transition matrices.

20

II.2.4

The typetransition.m Function

The matlab function typetransition.m takes the triple (ǩ, m̌, Π) as input, and produces a
(m̌+ǩ−1)!
m̌+ǩ−1)!
× ( (m̌!(
+ 1) × m̌ array, in which each page contains a transition matrix and the
m̌!(ǩ−1)!
ǩ−1)!
page number m indicates the number of firms. On each page, the first

(m+ǩ−1)!
m!(ǩ−1)!

rows and the

ǩ−1)!
first (m+
columns form the transition matrix for the m-firm market.
m!(ǩ−1)!
This function has several layers of loops. The most outside loop runs from m = 2 to
m = m̌. Within this loop, for each given m, the indexing matrix is first created and than
transformed to the matrix of the fourth indices. Then, we use the above mentioned regularity
patterns to construct the other three columns of indices and compute the transition matrix
Πm row-by-row.
Last, a few words on the computational speed. When ǩ = m̌ = 7, the transition matrix
is computed within 3 seconds. When ǩ = m̌ = 8, around 60 seconds. When ǩ = m̌ = 9, a
normal PC runs out of memory.

II.3

Computing All Renegotiation-proof Natural Markov-Perfect
Equilibria

In this appendix, we first show that when C is discrete, we can compute all renegotiationproof natural Markov-perfect equilibria. Then, we discuss how to modify Algorithm 2 to
compute all such equilibria.
We have seen in Section ?? that the multiplicity of renegotiation-proof equilibria comes
from the multiple mixing probabilities that can solve (11). Therefore, to compute any single
equilibrium using Algorithm 2, we always need to select the probability corresponding to this
equilibrium. To this end, we introduce a flexible selection mechanism which enables us to do
so.
A selection rule of such mechanism is summarized by Γ : Zǩ? × [ĉ, č] × K → {1, . . . , m̌}.
It works as follows. Suppose that a renegotiation-proof Markov-perfect equilibrium exists,
and aS (m, c, k), as a mixing probability, can take σ(m, c, k) values. Sort all these possible
values in a (weakly) descending sequence. Then, we use Γ to uniquely pin down aS (m, c, k)
by setting aS (m, c, k) = min{σ(m, c, k), Γ(m, c, k)}-th possible value in this sequence. To
give an example of Γ, if for any (m, c, k), Γ(m, c, k) = 1. Then, we always pick the first
one in the sequence or the largest probability as the survival rule. With a pre-specified Γ,
we can modify Procedure 3 to include this mechanism and compute a renegotiation-proof
Markov-perfect equilibrium.
21

mi , k i

Specify c ∈ [ĉ, č] and m ∈ mmi +jιki , ∀0 ≤ j ≤ m̌ − |mi |

mk i = 1 ?

Yes

αS (m, c, k i ) =
I[w(m, c, k i ) > 0]

No
wE (m, c, k i )
> 0?

Yes

αS (m, c, k i ) = 1

No
Find all p’s ∈ [0, 1) satisfying,


mki −1
X
mki −1−j j mki − 1
(1 − p)
p
wS (m − (mki − 1 − j)ιki , c, k i ) = 0.
j
j=0

No

wS (mi , c, k i )
> 0?

Sort p’s and 0 in
a decreasing array

Yes

Sort p’s in a decreasing array

σ(m, c, k i ) ← Length of the array, αS (m, c, k(m)) ←
the min{σ(m, c, k i ), Γ(m, c, k i )}-th element of this array

αE (m, c) = I[w(m +
jι1 , c, 1) − ϕ >
0, ∀0 ≤ j ≤ m̌ − |m|]

Yes

ki = 1 ?

No
CONTINUE

22
Procedure 3: Calculation of Candidate Entry/Survival
Rule for the General Model, NonMonotone Payoffs

Because the number of possible mixing probabilities is bounded by the number of roots
of the polynomial in equation (11), which is in turn bounded by the polynomial’s order. In
the general model, the highest order of any polynomial in equation (11) is m̌. Thus, from the
definition of Γ, it is clear that if C is a discrete variable, the number of distinct Γ mappings is
finite. Therefore, we can compute all renegotiation-proof natural Markov-perfect equilibria
for the general model by implementing Algorithm 2 repeatedly for all possible Γ’s. Although
this procedure can be completely parallelized, it is still computationally cumbersome for large
m̌, ǩ and large number of possible realizations of C.
Practically, we can reduce the computational burden by avoiding running the algorithm
for ”redundant” Γ’s. For some (m, c, k) ∈ S such that σ(m, c, k) < m̌, suppose that under
a selection rule Γ, Γ(m, c, k) = σ(m, c, k). Then any Γ̃ with Γ̃(m, c, k) > σ(m, c, k) and
Γ(n, d, g) = Γ̃(n, d, g), for all (n, d, g) 6= (m, c, k) selects the same Markov-perfect equilibrium
as Γ. Therefore, all such Γ̃ (there are m̌ − σ(m, c, k) of them) are redundant, provided
that we have run the algorithm for Γ. This suggests that to find all the renegotiation-proof
natural equilibria in a computationally efficient way, we should run the algorithm with no
pre-specified Γ but ”branch” the algorithm once multiplicity arises. To be more specific,
after starting the algorithm, once we reach a (m, c, k) such that σ(m, c, k) > 1, we create
σ(m, c, k) branches with αS (m, c, k) set differently. Different branches then can be computed
in parallel. The same branching exercise is done for each parallel session when a new state
with multiple choices emerges.

III
III.1

Computational Details
Pencil-and-Paper Computation behind Figure 3

One can compute the example graphed in Figure 3 using numerical method, such as value
function iteration. Alternatively, this example can be computed exactly using only pencil
and paper. This appendix contains the details. Begin with characterizing a duopolist’s payoff
function which satisfies
(
0
if Cc ≤ c2 ,
c
vE (2, c) =
(1−λ)( 2 π(2)−κ)+λe
v (2)
β
if c > c2 ,
1−β(1−λ)

23

where


 ĉ
c2 ≡
č


max{c|vE (2, c) = 0}

if vE (2, ĉ) > 0,
if vE (2, č) < 0,
otherwise,

and
1
ve(2) =
2



ĉ + č
2



Z

č

π(2) − κ +
c2

vE (2, c)
dC.
(č − ĉ)

We want to calculate the continuation and entry thresholds. If ĉπ(2)/2 > κ, firms always
earn positive payoff no matter which C is drawn, then vE (2, ĉ) > 0 and we settle with the
corner solution c2 = ĉ. If ĉπ(2)/2 < κ, we can normalize [ĉ, č] to [0, 1] with the transformations
C − ĉ
,
č − ĉ
π 0 (2) ≡ π(2) (č − ĉ) ,
ĉ
κ0 ≡ κ − π(2).
2
C0 ≡

We then proceed by first considering two corner solutions.
If vE (2, 0) > 0, no duopolist will ever exit the market and they expect to earn average
profit from perpetual operation if demand state switches. So ve(2) in this case is
 0

π (2)
1
0
−κ .
ve(2) =
1−β
4
Then vE (2, 0) > 0 is
β(1 − λ)
vE (2, 0) =
1 − β(1 − λ)



 0

π 0 (2)
βλ
π (2)
0
0
−κ +
−κ >0
0×
4
(1 − β(1 − λ)) (1 − β)
4

Simplify the above expression we produce the necessary and sufficient condition for the
corner solution c2 = 0 as
γ − γβ + γλβ − λ < 0,
0

with γ ≡ π4κ
0 (2) .
If vE (2, 1) < 0, it is not possible for both duopolist to always choose continuation, so
 0

 0

β(1 − λ)
π (2)
βλ
π (2)
0
0
−κ +
− κ < 0.
vE (2, 1) =
1 − β(1 − λ)
2
1 − β(1 − λ)
4
24

Simplify this expression we obtain the necessary and sufficient condition for the corner
solution c2 = 1 as
γ > 2 − λ.
Now we proceed to calculate the interior solution.
Substituting the lower branch of vE (2, c) into the expression for ve(2) produces
Z 1
π 0 (2)
−κ+
vE (2, C)dC
ve(2) =
4
c02
 0

π 0 (2)
β(1 − λ)
π (2)
βλe
v (2)
0
0 2
0
0
0
=
−κ +
(1 − (c2 ) ) − κ (1 − c2 ) +
(1 − c(6)
2 ).
4
1 − β(1 − λ)
4
1 − β(1 − λ)
In addition c02 by definition must satisfy
 0

c2 0
(1 − λ)
π (2) − κ + λe
v (2) = 0,
2
so

ve(2) =


1−λ
c02 0
.
κ − π (2)
2
λ
0

(7)

Combine (6) and (7) and then rearrange to obtain


 0

β(1 − λ) π 0 (2)
π (2) 1 − λ
β(1 − λ) π 0 (2) 0
0 2
(c2 ) +
−
c2
1 − β(1 − λ) 4
2
λ
1 − β(1 − λ) 2
 0

π (2)
β(1 − λ) π 0 (2) 1 − λ 0
0
−κ +
−
κ = 0.
+
4
1 − β(1 − λ) 4
λ

(8)

(8) is a quadratic equation in c02 of the form ax2 + bx + c = 0 with
β(1 − λ) π 0 (2)
,
1 − β(1 − λ) 2
π 0 (2) 1 − λ
β(1 − λ) π 0 (2)
b =
−
,
2
λ
1 − β(1 − λ) 4
β(1 − λ) π 0 (2) 1 − λ 0
π 0 (2)
− κ0 +
−
κ.
c =
4
1 − β(1 − λ) 4
λ

a =

Use x1,2 =

√
−b± b2 −4ac
2a

=
c01
2

1
λβ

c02
=
2

1
λβ

to calculate the roots for (8) as
!
r
(1 − λ − β + γλβ)(1 − β(1 − λ))
β−1+
, and
1−λ
!
r
(1 − λ − β + γλβ)(1 − β(1 − λ))
β−1−
1−λ
25

(9)
(10)

/ [0, 1]. The analysis above tell us that the necessary condition for
Because β < 1, c02
2 ∈
λ
an interior solution to exit is 2 − λ > γ > 1−β(1−λ)
. We use this to check that c01
2 is in the
admissible set (0, 1).
λ
Apparently c01
2 is increasing in γ. Substitute γ = 1−β(1−λ) into (9) to calculate the lower
bound for c01
2 as

p
1 
2 = 0.
c01
=
β
−
1
+
(1
−
β)
2
λβ
Substitute γ = 2 − λ into (9) to calculate the upper bound for c01
2 as

p
1 
01
2
c2 =
β − 1 + (1 − β(1 − λ)) = 1.
λβ
λ
Therefore, when 2 − λ > γ > 1−β(1−λ)
, the interior solution for c02 is given by (9). Finally,
we restore c2 by using c2 = c02 (č − ĉ) + ĉ.
Before we turn to the analysis for a monopolist, we calculate c2 which is defined as


if vE (2, ĉ) > ϕ,
 ĉ
c2 ≡
č
if vE (2, č) < ϕ,


max{c|vE (2, c) − ϕ = 0} otherwise,

After obtaining c2 , using (7), we can calculate ve(2). Then by setting vE (2, c2 ) = ϕ, we
calculate c2 as


2
ϕ(1 − β(1 − λ)) − λβe
v (2)
c2 =
+κ .
(11)
π(2)
β(1 − λ)
With this in hand, we can define a monopolist’s payoff
(
0
if c ≤ c1 ,
vE (1, c) =
(1−λ)(cπ(1)−κ)+λe
v (1)
β
if c > c1 ,
1−β(1−λ)
where


 ĉ
c1 ≡
č


max{c|vE (1, c) = 0}

if vE (1, ĉ) > 0,
if vE (1, č) < 0,
otherwise,

and

ve(1) =

ĉ + č
2



Z

č

π(1) − κ +
c2

vE (2, C)
dC +
(č − ĉ)
26

Z

c2

c1

vE (1, C)
dC.
(č − ĉ)

If ĉπ(1) > κ, firm always earns positive payoff no matter which C is drawn, then vE (1, ĉ) >
0 and we settle with the corner solution c1 = ĉ. If ĉπ(1) < κ, we can normalize [ĉ, č] to [0, 1]
with the transformations
C − ĉ
,
C0 ≡
č − ĉ
π 0 (1) ≡ π(1) (č − ĉ) ,
κ0 ≡ κ − ĉπ(1).
Because
Z 1
vE (2, C 0 )dC 0
c02

is readily computable by using the definition of vE (2, C). We hereafter denote its value by ν.
Similarly to the duopolist case, we then proceed by first considering two corner solutions.
If vE (1, 0) > 0, no monopolist will exit the market and we can calculate ve(1) in this case
as
1
(c0 )2 β(1 − λ)
β(1 − λ)c02 0
βλc02
ve(1) = π 0 (1) − κ0 + ν + 2
π 0 (1) −
κ +
ve(1).
2
2 1 − β(1 − λ)
1 − β(1 − λ)
1 − β(1 − λ)
This gives
ve(1) =

(π 0 (1)/2 − κ0 + ν) (1 − β(1 − λ)) + β(1 − λ) ((c02 )2 π 0 (1)/2 − c02 κ0 )
.
1 − β + λβ(1 − c02 )

Then vE (1, 0) > 0 is
vE (1, 0) =

β(1 − λ)
βλ
(−κ0 ) +
1 − β(1 − λ)
(1 − β(1 − λ))
0
0
(π (1)/2 − κ + ν) (1 − β(1 − λ)) + β(1 − λ) ((c02 )2 π 0 (1)/2 − c02 κ0 )
×
.
1 − β + λβ(1 − c02 )

Simplify the above expression we produce the necessary and sufficient condition for the
corner solution c1 = 0 as
(c02 )2 (1 − λ)β
+ 1,
(1 − β(1 − λ))

0
with γ 0 ≡ π02(1) κλ − ν .
If vE (1, 1) < 0, a monopolist will never remain in the market and entry will never happen,
γ0 <

so
β(1 − λ)
βλ
(π 0 (1) − κ0 ) +
vE (1, 1) =
1 − β(1 − λ)
1 − β(1 − λ)
27



π 0 (1)
− κ0
2


< 0.

Simplify this expression we obtain the necessary and sufficient condition for the corner
solution c1 = 1 as
2−λ 0
π (1) < κ0 .
2
Because ν = 0 in this case, we can add λν to the the right hand side without changing
the result. Divide both sides by π 0 (1)λ/2
γ0 >

2−λ
.
λ

Now we proceed to calculate the interior solution.
Substituting the lower branch of vE (1, c) into the expression for ve(1) produces
Z c02
π 0 (1)
0
−κ +ν+
vE (1, C)dC
ve(1) =
2
c01

 0
π 0 (1)
β(1 − λ)
π (1) 0 2
0
0 2
0 0
0
=
−κ +ν+
((c2 ) − (c1 ) ) − κ (c2 − c1 )
2
1 − β(1 − λ)
2
βλe
v (1)(c02 − c01 )
+
.
1 − β(1 − λ)

(12)

In addition c01 by definition must satisfy
v (1) = 0,
(1 − λ) (c01 π 0 (1) − κ0 ) + λe
so
ve(1) = (κ0 − c01 π 0 (1))

1−λ
.
λ

(13)

Combine (12) and (13) and then rearrange to obtain




1−λ
β(1 − λ)c02 0
β(1 − λ) π 0 (1)
0 2
0
−
π (1) c01
(c1 ) + π (1)
1 − β(1 − λ) 2
λ
1 − β(1 − λ)

 0
β(1 − λ)(c02 )2 π 0 (1) 1 − λ 0
π (1)
0
+
−κ +ν+
−
κ = 0.
2
1 − β(1 − λ) 2
λ
(14) is a quadratic equation in c01 of the form ax2 + bx + c = 0. Use x1,2 =
calculate the roots for (14) as
s
β
−
1
(ξ 2 − 2ηξc02 − η) + ηγ 0
0
−
1)
+
, and
c01
=
(c
+
2
1
λβ
η2
s
β
−
1
(ξ 2 − 2ηξc02 − η) + ηγ 0
02
0
c1 = (c2 − 1) +
+
λβ
η2
28

(14)

√
−b± b2 −4ac
2a

to

(15)
(16)

with
ξ =
η =

1−λ
,
λ
β(1−λ)
.
1−β(1−λ)

Because β < 1 and c02 < 1, c02
/ [0, 1]. The analysis above tell us that the necessary
1 ∈
(c02 )2 (1−λ)
condition for an interior solution to exit is 2−λ
> γ 0 > (1−β(1−λ))λ
+ 1. We use this to check
λ
01
that c1 is in the admissible set (0, 1).
(c02 )2 (1−λ)
0
0
Apparently c01
1 is increasing in γ . Substitute γ = (1−β(1−λ))λ + 1 to calculate the lower
bound for c01
1.
s
β−1
ξ 2 − 2ηξc02 − η + η + η 2 (c02 )2
0
−
1
+
=
c
+
c01
= 0.
2
1
λβ
η2
which can be simplified to
s
ξ
(ξ − ηc02 )2
0
+
= 0.
c01
1 = c2 −
η
η2
into (15) to calculate the upper bound for c01
1.
s
(1 − β(1 − λ) − 2λβc02 + 2λβ)(1 − β(1 − λ))
1
01
0
c1 = (c2 − 1) +
(β − 1) +
.
λβ
λ2 β 2

Substitute γ =

2−λ
λ

Remember when monopolist exit the market for sure, no duopolist will choose to survive.
So c02 = 1 and above equation simplifies to
s
1
(1 − β(1 − λ))2
c01
=
(β
−
1)
+
= 1.
1
λβ
λ2 β 2
(c0 )2 (1−λ)

2
Therefore, when 2−λ
> γ 0 > (1−β(1−λ))λ
+ 1, the interior solution for c01 is given by (15).
λ
Finally, we restore c1 by using c1 = c01 (č − ĉ) + ĉ.
Last thing is to calculate c1 , which is defined as


if vE (1, ĉ) > ϕ,
 ĉ
c1 ≡
č
if vE (1, č) < ϕ,


max{c|vE (1, c) − ϕ = 0} otherwise,

After obtaining c1 , using (13), we can calculate ve(1). Then by setting vE (1, c1 ) = ϕ, we
calculate c1 as


1
ϕ(1 − β(1 − λ)) − λβe
v (1)
c1 =
+κ .
(17)
π(1)
β(1 − λ)
Because firms’ payoffs are linear functions in C, knowing c1 , c1 , c2 , c2 is sufficient for
determining the payoffs for duopolist and monopolist. The calculation is completed.
29

III.2

Computing the Example of Multiple Equilibria in Section 4.2

Note that this model is deterministic. We compute some important equilibrium payoffs which
account for equilibrium multiplicity as below
(i). Since c3 π H (3ιH ) > κ, if three type-H firms are active in the second period, they can
always recover fixed cost and make positive profit by remaining active from the third
period onwards. Moreover, if less type-H firms are active in the second period, they
receive higher profit from the third period onward. Therefore, for t ≥ 2, aS (3ιH , ct , H)
is a dominant strategy and
vE (3ιH , ct , H) =

β(c3 π H (3ιH ) − κ)
= 1.
1−β

(ii). Since c3 π L (2ιH + ιL ) > κ, c3 π H (ιH + 2ιL ) > κ and c3 π L (ιH + 2ιL ) > κ, for the same
reason, for t ≥ 2,
vE (2ιH + ιL , ct , L) = vS (2ιH + ιL , ct , L)
β(1 − ΠLH )
=
(c3 π L (2ιH + ιL ) − κ)
1 − β(1 − ΠLH )


β(1 − ΠLH )
β
−
+
(c3 π H (3ιH ) − κ)
1 − β 1 − β(1 − ΠLH )
= 0.8167
vE (2ιH + ιL , ct , H) = vS (2ιH + ιL , ct , H)
β(1 − ΠLH )
(c3 π H (2ιH + ιL ) − κ)
=
1 − β(1 − ΠLH )


β
β(1 − ΠLH )
+
−
(c3 π H (3ιH ) − κ)
1 − β 1 − β(1 − ΠLH )
= 1.4
vE (ιH + 2ιL , ct , L) = vS (ιH + 2ιL , ct , L)
1
=
((1 − ΠLH )2 (c3 π L (ιH + 2ιL ))
1 − β(1 − ΠLH )2
+(1 − ΠLH )ΠLH (c3 π H (2ιH + ιL ) + vE (2ιH + ιL , ct+1 , H))
+(1 − ΠLH )ΠLH (c3 π L (2ιH + ιL ) + vE (2ιH + ιL , ct+1 , L))
+Π2LH (c3 π H (3ιH ) + vE (3ιH , ct+1 , L)) − κ)
= 1.2881
(iii). Since vE (2ιH + ιL , c2 , L) < ϕ and vE (ιH + 2ιL , c2 , L) > ϕ, we have that aE (2ιH +
ιL , c2 , L) = 0 and aE (ιH + 2ιL , c2 , L) = 1. This means that in the second period, two
30

type-L firms will enter a market occupied by a type-H monopoly, while no firm will
enter a market occupied by two type-H duopoly. Since demand stays constant from
the third period on, the market structures at the end of the second period will never
be changed. Therefore, for t ≥ 2,
vE (2ιH , ct , H) = vS (2ιH , ct , H)
β(c3 π H (2ιH ) − κ)
=
1−β
= 496
vE (ιH + 2ιL , ct , H) = vS (ιH + 2ιL , ct , H)
1
=
((1 − ΠLH )2 (c3 π H (ιH + 2ιL ))
1 − β(1 − ΠLH )2
+2(1 − ΠLH )ΠLH (c3 π H (2ιH + ιL ) + vE (2ιH + ιL , ct+1 , H))
+Π2LH (c3 π H (3ιH ) + vE (3ιH , ct+1 , L)) − κ)
= 1.6357
(iv). For a type-H monopolist who is active in the first period, the payoff to continuation is
vS (ιH , c1 , H) = β ((c2 π H (ιH ) − κ) + vE (ιH + 2ιL , c2 , H)) = −1.1821.
For a type-H duopolist who is active in the first period together with another type-H
rival, the payoff to continuation, given the rival also continues, is
vS (2ιH , c1 , H) = β ((c2 π H (2ιH ) − κ) + vE (2ιH , c2 , H)) = 246.
For a type-H triopolist who is active in the first period together with another two
type-H rivals, the payoff to continuation, given the rivals also continue, is
vS (3ιH , c1 , H) = β ((c2 π H (3ιH ) − κ) + vE (3ιH , c2 , H)) = −1.5.

31

Working Paper Series
A series of research studies on regional economic issues relating to the Seventh Federal
Reserve District, and on financial and economic topics.
Risk Taking and the Quality of Informal Insurance: Gambling and Remittances in Thailand
Douglas L. Miller and Anna L. Paulson

WP-07-01

Fast Micro and Slow Macro: Can Aggregation Explain the Persistence of Inflation?
Filippo Altissimo, Benoît Mojon, and Paolo Zaffaroni

WP-07-02

Assessing a Decade of Interstate Bank Branching
Christian Johnson and Tara Rice

WP-07-03

Debit Card and Cash Usage: A Cross-Country Analysis
Gene Amromin and Sujit Chakravorti

WP-07-04

The Age of Reason: Financial Decisions Over the Lifecycle
Sumit Agarwal, John C. Driscoll, Xavier Gabaix, and David Laibson

WP-07-05

Information Acquisition in Financial Markets: a Correction
Gadi Barlevy and Pietro Veronesi

WP-07-06

Monetary Policy, Output Composition and the Great Moderation
Benoît Mojon

WP-07-07

Estate Taxation, Entrepreneurship, and Wealth
Marco Cagetti and Mariacristina De Nardi

WP-07-08

Conflict of Interest and Certification in the U.S. IPO Market
Luca Benzoni and Carola Schenone

WP-07-09

The Reaction of Consumer Spending and Debt to Tax Rebates –
Evidence from Consumer Credit Data
Sumit Agarwal, Chunlin Liu, and Nicholas S. Souleles

WP-07-10

Portfolio Choice over the Life-Cycle when the Stock and Labor Markets are Cointegrated
Luca Benzoni, Pierre Collin-Dufresne, and Robert S. Goldstein

WP-07-11

Nonparametric Analysis of Intergenerational Income Mobility
with Application to the United States
Debopam Bhattacharya and Bhashkar Mazumder

WP-07-12

How the Credit Channel Works: Differentiating the Bank Lending Channel
and the Balance Sheet Channel
Lamont K. Black and Richard J. Rosen

WP-07-13

Labor Market Transitions and Self-Employment
Ellen R. Rissman

WP-07-14

First-Time Home Buyers and Residential Investment Volatility
Jonas D.M. Fisher and Martin Gervais

WP-07-15

1

Working Paper Series (continued)
Establishments Dynamics and Matching Frictions in Classical Competitive Equilibrium
Marcelo Veracierto

WP-07-16

Technology’s Edge: The Educational Benefits of Computer-Aided Instruction
Lisa Barrow, Lisa Markman, and Cecilia Elena Rouse

WP-07-17

The Widow’s Offering: Inheritance, Family Structure, and the Charitable Gifts of Women
Leslie McGranahan

WP-07-18

Incomplete Information and the Timing to Adjust Labor: Evidence from the
Lead-Lag Relationship between Temporary Help Employment and Permanent Employment
Sainan Jin, Yukako Ono, and Qinghua Zhang

WP-07-19

A Conversation with 590 Nascent Entrepreneurs
Jeffrey R. Campbell and Mariacristina De Nardi

WP-07-20

Cyclical Dumping and US Antidumping Protection: 1980-2001
Meredith A. Crowley

WP-07-21

Health Capital and the Prenatal Environment:
The Effect of Maternal Fasting During Pregnancy
Douglas Almond and Bhashkar Mazumder

WP-07-22

The Spending and Debt Response to Minimum Wage Hikes
Daniel Aaronson, Sumit Agarwal, and Eric French

WP-07-23

The Impact of Mexican Immigrants on U.S. Wage Structure
Maude Toussaint-Comeau

WP-07-24

A Leverage-based Model of Speculative Bubbles
Gadi Barlevy

WP-08-01

Displacement, Asymmetric Information and Heterogeneous Human Capital
Luojia Hu and Christopher Taber

WP-08-02

BankCaR (Bank Capital-at-Risk): A credit risk model for US commercial bank charge-offs
Jon Frye and Eduard Pelz

WP-08-03

Bank Lending, Financing Constraints and SME Investment
Santiago Carbó-Valverde, Francisco Rodríguez-Fernández, and Gregory F. Udell

WP-08-04

Global Inflation
Matteo Ciccarelli and Benoît Mojon

WP-08-05

Scale and the Origins of Structural Change
Francisco J. Buera and Joseph P. Kaboski

WP-08-06

Inventories, Lumpy Trade, and Large Devaluations
George Alessandria, Joseph P. Kaboski, and Virgiliu Midrigan

WP-08-07

2

Working Paper Series (continued)
School Vouchers and Student Achievement: Recent Evidence, Remaining Questions
Cecilia Elena Rouse and Lisa Barrow
Does It Pay to Read Your Junk Mail? Evidence of the Effect of Advertising on
Home Equity Credit Choices
Sumit Agarwal and Brent W. Ambrose

WP-08-08

WP-08-09

The Choice between Arm’s-Length and Relationship Debt: Evidence from eLoans
Sumit Agarwal and Robert Hauswald

WP-08-10

Consumer Choice and Merchant Acceptance of Payment Media
Wilko Bolt and Sujit Chakravorti

WP-08-11

Investment Shocks and Business Cycles
Alejandro Justiniano, Giorgio E. Primiceri, and Andrea Tambalotti

WP-08-12

New Vehicle Characteristics and the Cost of the
Corporate Average Fuel Economy Standard
Thomas Klier and Joshua Linn

WP-08-13

Realized Volatility
Torben G. Andersen and Luca Benzoni

WP-08-14

Revenue Bubbles and Structural Deficits: What’s a state to do?
Richard Mattoon and Leslie McGranahan

WP-08-15

The role of lenders in the home price boom
Richard J. Rosen

WP-08-16

Bank Crises and Investor Confidence
Una Okonkwo Osili and Anna Paulson

WP-08-17

Life Expectancy and Old Age Savings
Mariacristina De Nardi, Eric French, and John Bailey Jones

WP-08-18

Remittance Behavior among New U.S. Immigrants
Katherine Meckel

WP-08-19

Birth Cohort and the Black-White Achievement Gap:
The Roles of Access and Health Soon After Birth
Kenneth Y. Chay, Jonathan Guryan, and Bhashkar Mazumder

WP-08-20

Public Investment and Budget Rules for State vs. Local Governments
Marco Bassetto

WP-08-21

Why Has Home Ownership Fallen Among the Young?
Jonas D.M. Fisher and Martin Gervais

WP-09-01

Why do the Elderly Save? The Role of Medical Expenses
Mariacristina De Nardi, Eric French, and John Bailey Jones

WP-09-02

3

Working Paper Series (continued)
Using Stock Returns to Identify Government Spending Shocks
Jonas D.M. Fisher and Ryan Peters

WP-09-03

Stochastic Volatility
Torben G. Andersen and Luca Benzoni

WP-09-04

The Effect of Disability Insurance Receipt on Labor Supply
Eric French and Jae Song

WP-09-05

CEO Overconfidence and Dividend Policy
Sanjay Deshmukh, Anand M. Goel, and Keith M. Howe

WP-09-06

Do Financial Counseling Mandates Improve Mortgage Choice and Performance?
Evidence from a Legislative Experiment
Sumit Agarwal,Gene Amromin, Itzhak Ben-David, Souphala Chomsisengphet,
and Douglas D. Evanoff

WP-09-07

Perverse Incentives at the Banks? Evidence from a Natural Experiment
Sumit Agarwal and Faye H. Wang

WP-09-08

Pay for Percentile
Gadi Barlevy and Derek Neal

WP-09-09

The Life and Times of Nicolas Dutot
François R. Velde

WP-09-10

Regulating Two-Sided Markets: An Empirical Investigation
Santiago Carbó Valverde, Sujit Chakravorti, and Francisco Rodriguez Fernandez

WP-09-11

The Case of the Undying Debt
François R. Velde

WP-09-12

Paying for Performance: The Education Impacts of a Community College Scholarship
Program for Low-income Adults
Lisa Barrow, Lashawn Richburg-Hayes, Cecilia Elena Rouse, and Thomas Brock
Establishments Dynamics, Vacancies and Unemployment: A Neoclassical Synthesis
Marcelo Veracierto

WP-09-13

WP-09-14

The Price of Gasoline and the Demand for Fuel Economy:
Evidence from Monthly New Vehicles Sales Data
Thomas Klier and Joshua Linn

WP-09-15

Estimation of a Transformation Model with Truncation,
Interval Observation and Time-Varying Covariates
Bo E. Honoré and Luojia Hu

WP-09-16

Self-Enforcing Trade Agreements: Evidence from Antidumping Policy
Chad P. Bown and Meredith A. Crowley

WP-09-17

Too much right can make a wrong: Setting the stage for the financial crisis
Richard J. Rosen

WP-09-18

4

Working Paper Series (continued)
Can Structural Small Open Economy Models Account
for the Influence of Foreign Disturbances?
Alejandro Justiniano and Bruce Preston

WP-09-19

Liquidity Constraints of the Middle Class
Jeffrey R. Campbell and Zvi Hercowitz

WP-09-20

Monetary Policy and Uncertainty in an Empirical Small Open Economy Model
Alejandro Justiniano and Bruce Preston

WP-09-21

Firm boundaries and buyer-supplier match in market transaction:
IT system procurement of U.S. credit unions
Yukako Ono and Junichi Suzuki
Health and the Savings of Insured Versus Uninsured, Working-Age Households in the U.S.
Maude Toussaint-Comeau and Jonathan Hartley

WP-09-22

WP-09-23

The Economics of “Radiator Springs:” Industry Dynamics, Sunk Costs, and
Spatial Demand Shifts
Jeffrey R. Campbell and Thomas N. Hubbard

WP-09-24

On the Relationship between Mobility, Population Growth, and
Capital Spending in the United States
Marco Bassetto and Leslie McGranahan

WP-09-25

The Impact of Rosenwald Schools on Black Achievement
Daniel Aaronson and Bhashkar Mazumder

WP-09-26

Comment on “Letting Different Views about Business Cycles Compete”
Jonas D.M. Fisher

WP-10-01

Macroeconomic Implications of Agglomeration
Morris A. Davis, Jonas D.M. Fisher and Toni M. Whited

WP-10-02

Accounting for non-annuitization
Svetlana Pashchenko

WP-10-03

Robustness and Macroeconomic Policy
Gadi Barlevy

WP-10-04

Benefits of Relationship Banking: Evidence from Consumer Credit Markets
Sumit Agarwal, Souphala Chomsisengphet, Chunlin Liu, and Nicholas S. Souleles

WP-10-05

The Effect of Sales Tax Holidays on Household Consumption Patterns
Nathan Marwell and Leslie McGranahan

WP-10-06

Gathering Insights on the Forest from the Trees: A New Metric for Financial Conditions
Scott Brave and R. Andrew Butters

WP-10-07

Identification of Models of the Labor Market
Eric French and Christopher Taber

WP-10-08

5

Working Paper Series (continued)
Public Pensions and Labor Supply Over the Life Cycle
Eric French and John Jones

WP-10-09

Explaining Asset Pricing Puzzles Associated with the 1987 Market Crash
Luca Benzoni, Pierre Collin-Dufresne, and Robert S. Goldstein

WP-10-10

Does Prenatal Sex Selection Improve Girls’ Well‐Being? Evidence from India
Luojia Hu and Analía Schlosser

WP-10-11

Mortgage Choices and Housing Speculation
Gadi Barlevy and Jonas D.M. Fisher

WP-10-12

Did Adhering to the Gold Standard Reduce the Cost of Capital?
Ron Alquist and Benjamin Chabot

WP-10-13

Introduction to the Macroeconomic Dynamics:
Special issues on money, credit, and liquidity
Ed Nosal, Christopher Waller, and Randall Wright

WP-10-14

Summer Workshop on Money, Banking, Payments and Finance: An Overview
Ed Nosal and Randall Wright

WP-10-15

Cognitive Abilities and Household Financial Decision Making
Sumit Agarwal and Bhashkar Mazumder

WP-10-16

Complex Mortgages
Gene Amromin, Jennifer Huang, Clemens Sialm, and Edward Zhong

WP-10-17

The Role of Housing in Labor Reallocation
Morris Davis, Jonas Fisher, and Marcelo Veracierto

WP-10-18

Why Do Banks Reward their Customers to Use their Credit Cards?
Sumit Agarwal, Sujit Chakravorti, and Anna Lunn

WP-10-19

The impact of the originate-to-distribute model on banks
before and during the financial crisis
Richard J. Rosen
Simple Markov-Perfect Industry Dynamics
Jaap H. Abbring, Jeffrey R. Campbell, and Nan Yang

WP-10-20

WP-10-21

6
Full text of Working Papers (Federal Reserve Bank of Chicago) : Simple Markov-Perfect Industry Dynamics, Working Paper 2010-21

FRASER
