Sequential Estimation of Structural Models with aFixed Point Constraint
Hiro Kasahara1

Katsumi Shimotsu2

1 Department of Economics
University of British Columbia
2 Department of Economics

Hitotsubashi University

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 2010

1 / 39Outline

1

Structural model 1: game-theoretic model of entry

2

Structural model 2: dynamic discrete game3

Review of existing estimation methods

4

Alternative estimation method

5

Simulation results

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 2010

2 / 39

Introduction: structural economic models
Many markets are characterized as a competition among a
few firms with differentiated products
Between monopoly and perfect competition
In such markets, strategic interaction between firms become
important.
Many economists want to understand how firms competewith each other in such markets.
Implications for competition policy, entry regulation, etc.
“Structural economic models" explicitly model firms’
strategic interaction (and dynamic choice)
Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 2010

3 / 39Structural model 1: game-theoretic model of entry
Two potential entrants to a market (for example, 5th
generation smartphone, Docomo and KDDI).
If both firms enter, both firms earn positive profit. If only one
firm enters, it earns larger profit.
Payoff matrix
firm 2inoutfirm 1 in (1, 1) (3, 0)
out (0, 3) (0, 0)Nash equilibrium: given the other player’s action,
I have no incentive to change my action ⇒ (in,in)
Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 2010

4 / 39

Games with private information
But firm 1 may not know everything about firm 2.
Payoff matrix with a random component

firm 1inoutfirm 2in(ε1 − θ, ε2 − θ)(0, ε2 )out(ε1 , 0)(0, 0)

ε1 and ε2 are drawn independently from uniform
distribution[0, 1]. Both firms know θ.
Only firm 1 observes ε1 , and only firm 2 observes ε2 (private
information).

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 2010

5 / 39

How to determine the equilibrium
firm 2inoutfirm 1 in (ε1 − θ, ε2 − θ) (ε1 , 0)
out(0, ε2 )(0, 0)
Suppose firm 1 thinks that firm 2 enters with probability P2 =firm 1’s subjective probability (“belief")
Firm 1 enters the market if
P2 (ε1 − θ) + (1 − P2 )ε1 > 0 ⇒ ε1 > θP2
Because ε1 ∼ U[0, 1], firm 1 enters the market withprobability 1 − θP2 when his belief is P2 .

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 2010

6 / 39

How to determine the equilibrium
Firm 1 enters the market with probability 1 − θP2 when his
belief is P2 .
Firm 2 enters the market with probability 1 − θP1 when his
belief is P1 .
Bayesian perfect equilibrium: both players’ belief must be
consistent with their action.
P1 = 1 − θP2 ,

P2 = 1 − θP1 ⇒ P1 = P2 = 1/(1 + θ)Best response mapping: [0, 1]2 → [0, 1]2
Ψ(θ, P) = (1 − θP2 , 1 − θP1 )0 .
Then BPE is a fixed point of Ψ : P ∗ = Ψ(θ, P ∗ )Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 2010

7 / 39Estimation of θ in this model

Suppose we have iid data of the entry decision (a1i , a2i ) fori = 1, . . . , n, and we want to estimate the value of θ.
If we assume the data are in the equilibrium,
we can estimate θ by"#
1 1 − P̂1 1 − P̂2
.
θ̂ =
+
2
P̂1
P̂2

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 2010

8 / 39

Do people actually behave according to the gametheory?
Many experimental resultsSee, for example, The Handbook of Experimental Economics(1995), John H. Kagel and Alvin E. Roth, eds., Princeton
University Press.
Overall conclusion: yes and noGame of market: theoretical monopoly price > price inexperiments > theoretical no-monopoly price
Provision of public goods: less free-riding than predicted bytheoryHiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 2010

9 / 39

A game may have multiple equilibria
Payoff matrix with the entry cost of −2
firm 2inoutfirm 1 in (−1, −1) (1, 0)
out(0, 1)(0, 0)Nash equilibria: (in,out), (out,in)
We assume Ψ(θ, P) has a unique fixed point forthe moment.
Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 2010

10 / 39

Structural model 2: dynamic discrete gameN firms = potential entrants
Entry/exit choice: ait ∈ A = {0, 1}.
Firm i’s profit in period t:Π̃i (at , St , ai,t−1 , t ; θ)All the firms’ current decision: at = (a1t , ..., aNt )0
I Market demand condition: S (observable)t
I Past entry decision: ai,t−10
I Private shocks:  = ( , ..., t1tNt ) .
I

θ: parameter of interest

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 201011 / 39

Dynamic discrete game example (continued)
Profit function of firm i:Π̃i (at , St , at−1 , it ; θ) = θRS ln St − θFC,i − θEC (1 − ai,t−1 )− θRN ln(1 +Xajt ) + it1

j6=i

θRS : Revenue parameter
θFC,i : Operating cost
θEC : Entry cost
θRN : Degree of strategic substitution

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 201012 / 39

Structural model 2: dynamic discrete game

Dynamic optimization by firm i
"∞
#
X
max
E
β t Πi (at , St , ai,t−1 , t ; θ)|St , at−1 ; θai1 ,ai2 ,...

t=0

Assume the state variable follows a Markov process
Markov decision problem given his belief
Stationary solution

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 201013 / 39

Structural model 2: dynamic discrete gameEmpirical implication: firm i’s conditional choice probabilities= Pi (a|x).
Pi = {Pi (a|x)}(a,x) : firm i’s conditional choice probabilities for
all possible x
The conditional choice probabilities of all the firms:
P = (P1 , . . . , PN )For a given θ, an equilibrium is characterized by a fixed pointof the best response mappingP = Ψ(θ, P)

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 201014 / 39

P can be large
For example,
5 potential entrants
all the firms’ entry status in the previous period:
25 = 32 support points
market condition takes 10 different values
xt takes 10 × 32 = 320 different values
Length of P = 320 × 5 = 1600
⇒ finding a fixed point of Ψ can be computationally costly
Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 201015 / 39

Economic models with a fixed point constraint

When P = P(a|x) is the choice probability of a discrete
action a conditional on x, the log-likelihood function is
Qn (θ) =nXln P(ai |xi ) s.t. P = Ψ(θ, P)

i=1

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 201016 / 39

Approach 1: nested fixed point approach (Rust, 1987)nθ̂ML = arg max
θ∈Θ

s.t.

1X
ln P (ai |xi )ni=1

P = Ψ (θ, P)

Starting from an initial value of θ,(Inner Loop) For each candidate parameter θ, find the fixed
point: Pθ = Ψ(θ, Pθ ).
(Outer Loop) Maximize the log-likelihood function by aquasi-Newton method.
This algorithm produces θ̂ML but is very computationallyintensive.

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 201017 / 39

Approach 2: constraint optimization approach (Su andJudd, 2010)
Write down the LagrangiannL(θ, P, λ) =1X
ln P (ai |xi ) + λ(P − Ψ (θ, P))ni=1Solve the first-order condition∇θ L(θ∗ , P ∗ , λ∗ ) = 0,
∇P L(θ∗ , P ∗ , λ∗ ) = 0,
P ∗ − Ψ(θ∗ , P ∗ ) = 0
According to the authors, one can solve this problem using
the “NEOS Server, a free internet service which gives theuser access to several state-of-the-art solvers."
Applications?
Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 201018 / 39

Approach 3: NPL estimator (Aguirregabiria and Mira,
2007)
P̃0 : initial guess of P
Step 1: Given P̃k −1 ,n1Xln[Ψ(θ, P̃k −1 )](ai |xi ).
ni=1

can be viewed as a pseudo log-likelihood function. So,
estimate θ by maximizing this objective function ⇒ θ̃kStep 2: Given θ̃k , update the estimate of P byP̃k = Ψ(θ̃k , P̃k −1 ).
Iterate Steps 1-2:
Hiro Kasahara, Katsumi Shimotsu (){θ̃k , P̃k }∞k =1
Structural Estimation

IBIS 201019 / 39

NPL Fixed Points: {θ̌, P̌}
If the sequence {θ̃k , P̃k }∞k =1 converges, its limit satisfiesnθ̌ = arg max
θ1X
ln[Ψ(θ, P̌)](ai |xi ),ni=1P̌ = Ψ(θ̌, P̌).
The NPL estimator is defined as (θ̌, P̌) that achieves thehighest pseudo-likelihood value.
Easy to implement: standard optimization and policy
iteration

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 2010

20 / 39

What empirical researchers want

Estimation methods that work
Easy-to implement, easy-to understand methods
Not all the economists/econometricians want to spend a lotof time on writing computer codes.

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 2010

21 / 39

Convergence of the NPL algorithm?

Convergence of {θ̃k , P̃k }∞k =1 ?
Empirical researchers report non-convergence of the NPL
algorithm.
For example, it can exhibit a 2-period cycle.
Little is known when it works and when it doesn’t, except fora few counter-examples.

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 201022 / 39

Insight: a population NPL sequence
Suppose we have infinitely many observations.
θ̃k = θ̃(P̃k −1 ) = arg max E ln[Ψ(θ, P̃k −1 )](ai |xi ).
θP̃k = Ψ(θ̃(P̃k −1 ), P̃k −1 ) ≡ φ0 (P̃k −1 ).
True probability P 0 is an NPL fixed point:
P 0 = φ0 (P 0 ).
| dominant eigenvalue of (∇P 0 φ0 (P)|P=P 0 ) | < 1⇒ stability at P 0 .

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 201023 / 39

Property of NPL updating (Kasahara and Shimotsu,
2010)
In a neighborhood of P 0 ,θ̃j − θ̂NPL = Op (||P̃j−1 − P̂NPL ||),
P̃j − P̂NPL = MΨθ ΨP (P̃j−1 − P̂NPL )+ Op (n−1/2 ||P̃j−1 − P̂NPL ||) + Op (||P̃j−1 − P̂NPL ||2 ),whereMΨθ = I − Ψθ (Ψ0θ ∆P Ψθ )−1 Ψ0θ ∆P∇P 0 φ0 (P)|P=P 0 = MΨθ ΨP .

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 201024 / 39

Property of NPL updating (Kasahara and Shimotsu,
2010)

The convergence of P̃k depends on the eigenvalues ofMΨθ ΨP .
The dominant eigenvalue of AB is not necessarily boundedby that of A and B.
But ρ(MΨθ ΨP ) ≈ ρ(ΨP ) holds if dim(P)  dim(θ).

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 201025 / 39

Dynamic Game Example (continued)
Profit function of firm i:Π̃i (at , St , at−1 , it ; θ) = θRS ln St − θFC,i − θEC (1 − ai,t−1 )− θRN ln(1 +Xajt ) + it1

j6=i

θRS : Revenue parameter
θFC,i : Operating cost
θEC : Entry cost
θRN : Degree of strategic substitution

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 2010

26 / 39

Dominant eigenvalue of ΨP and MΨθ ΨP

θRN
1
2
4
6

ρ(ΨP ) ρ(MΨθ ΨP )
0.337
0.292
0.693
0.595
1.184
1.180
1.479
1.478

Note: dim(P) = 144 and dim(θ) = 2.
Strong strategic substitutability→ {θ̃k , P̃k } diverges away from (θ0 , P 0 ).

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 201027 / 39

What if Ψ is not locally contractive around P 0 ?

(1) Relaxation method:[Λ(θ, P)](a|x) = {[Ψ(θ, P)](a|x)}α P(a|x)(1−α) , α ∈ (0, 1)— easy, works in some cases(2) Recursive Projection Method (borrowed from Shroff andKeller, 1993, SIAM)

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 201028 / 39

(1) Locally contractive mapping (relaxation method)[Λ(θ, P)](a|x) = {[Ψ(θ, P)](a|x)}α P(a|x)(1−α)

The same fixed point: Pθ = Ψ(θ, Pθ ) = Λ(θ, Pθ )Eigenvalues of ∇P 0 Λ(θ, P) = α×(eigenvalues ofΨP ) + (1 − α)We can choose α so that ρ(ΛP ) < 1 if all the
eigenvalues of ΨP are smaller than 1.
Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 201029 / 39

Convergence of Ψ and Λ for Dynamic Game Example

θRN = 1 θRN = 2 θRN = 4 θRN = 6
ρ(ΨP )
0.337
0.693
1.184
1.479
ρ(ΛP )
0.257
0.495
0.802
0.916
ρ(MΨθ ΨP ) 0.292
0.595
1.180
1.478
ρ(MΛθ ΛP )
0.258
0.494
0.805
0.915

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 201030 / 39

Alternative Sequential Estimation ProcedureP̃0 : an initial consistent estimator
Use Λ(θ, P) in place of Ψ(θ, P) and update θ andP sequentially.
The algorithm converges locally if ρ(ΛP ) < 1.

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 201031 / 39

(2) Recursive Projection Method (RPM) (Shroff andKeller, 1993, SIAM)
The eigenvalues of ∇P 0 Ψ(θ, Pθ ): {λ1 , ..., λL }|λ1 | ≥ ... ≥ |λm | > 1 − δ ≥ |λm+1 | ≥ ... ≥ |λL |.
Typically, m is small. Let
Zθ = [z1 , ..., zm ] ,| {z }
eigenvectorsΠθ ≡ Zθ (Zθ0 Zθ )−1 Zθ0 .
|{z}projection

Decompose Pj−1 as
uj−1 = Πθ Pj−1 ,Hiro Kasahara, Katsumi Shimotsu ()vj−1 = (I − Πθ )Pj−1 .

Structural Estimation

IBIS 201032 / 39

RPM (cont.)
Definef (u, v , θ) ≡ Πθ Ψ(θ, u + v ),g(u, v , θ) ≡ (I − Πθ )Ψ(θ, u + v ).

Pj = Ψ(Pj−1 , θ) = f (uj−1 , vj−1 , θ) + g(uj−1 , vj−1 , θ).
|{z}
not contracting
Newton step on u = f (u, v , θ): uj = h(uj−1 , vj−1 , θ)
Pj = Γ(Pj−1 , θ) = h(uj−1 , vj−1 , θ) + g(uj−1 , vj−1 , θ)

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 201033 / 39Sequential Estimation Procedure by approximate RPM(P̃0 , θ̃0 ): an initial consistent estimator
Step 1: Given P̃k −1 , estimate θ byn1X
θ̃k = arg max
ln[Γ(θ; P̃k −1 , θ̃k −1 )](ai |xi ).
nθ
i=1

Step 2: Given θ̃k , update the estimate of P byP̃k = Γ(θ̃k ; P̃k −1 , θ̃k −1 ).
Iterate Steps 1-2:{θ̃k , P̃k }∞k =1

The algorithm converges locally if ρ(MΓθ ΓP ) < 1, whereMΓθ = I − Γθ (Γ0θ ∆P Γθ )−1 Γ0θ ∆P .
Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 201034 / 39

Stable Case: θRN = 2 and |ρ(MΨθ ΨP )| < 1

Estimator

θ̂RN

NPL-Ψ
NPL-Λ
RPM
Ψ (k = 1)n = 500√
Bias
MSE-0.0467 0.4705-0.0467 0.4705-0.0544 0.4642-0.7895 0.9604

Hiro Kasahara, Katsumi Shimotsu ()n = 2000√
Bias
MSE-0.0009 0.2339-0.0009 0.2339-0.0102 0.2274-0.2565 0.3949

Structural Estimationn = 8000√
Bias
MSE-0.0095 0.1130-0.0095 0.1130-0.0111 0.1116-0.0828 0.1687

IBIS 201035 / 39

Unstable Case: θRN = 4 and |ρ(MΨθ ΨP )| > 1

Estimator

θ̂RN

Note:

NPL-Ψ
NPL-Λ
RPM
Ψ (k = 1)n = 500√
Bias
MSE-0.1417 0.2572
0.02410.14240.02490.1604-0.7713 0.9094

n = 2000√
Bias
MSE-0.1414 0.2314-0.0001 0.0739-0.0003 0.0841-0.1964 0.2599

n = 8000√
Bias
MSE-0.0918 0.1612
0.00130.03520.00140.0342-0.0462 0.0937

With 1000 simulated samples. We set q = 4 for q-NPL.

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 201036 / 39

Unstable Case: MSE of θ̂RN for θRN = 4 and n = 8000√

MSE of θ̂RN :

NPL-Ψ
NPL-Λ
RPM
Note:

k=2
0.0676
0.06970.0599k=50.07190.03690.0361k=10
0.07840.03550.0353k=15
0.12190.03540.0350k=20
0.13020.03540.0349k=25
0.15680.03540.0349With 1000 simulated samples.

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 201037 / 39

Open questions

Multiple equilibria (1): how to find all the fixed points on
Ψ(θ, P)
Multiple equilibria (2): how to determine which equilibria areplayed by the data

Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 201038 / 39References
Aguirregabiria, V. and Mira. P. (2010).“Dynamic discrete choice
structural models: A survey.” Journal of Econometrics 156, 38-67.
Aguirregabiria, V. and Mira, P. (2007). “Sequential estimation of
dynamic discrete games.” Econometrica 75, 1-53.
Imai, S., Jain N., and Ching, A. (2009). “Bayesian Estimation of
Dynamic Discrete Choice Models." Econometrica 77, 1865-1899.
Rust, J. (1987). “Optimal replacement of GMC bus engines: anempirical model of Harold Zurcher.” Econometrica 55, 999-1033.
Shroff, G. M. and Keller, H. B. (1993). “Stabilization of unstableprocedures: the recursive projection method.” SIAM Journal of
Numerical Analysis, 30, 1099-1120.
Su, Che-Lin and Judd, K. L. (2010). Constrained optimization
approaches to estimation of structural models. Working Paper,
University of Chicago.
Hiro Kasahara, Katsumi Shimotsu ()Structural Estimation

IBIS 201039 / 39