Nested Pseudo Likelihood Estimation of Continuous-Time Dynamic Discrete Games

Nested Pseudo Likelihood Estimation of Continuous-Time Dynamic Discrete Games

Introduction

This paper introduces a new sequential estimator for continuous-time dynamic discrete choice models. In dynamic models, as compared to static models, forward-looking agents make decisions based on expected future payoffs each period. Discrete choice models focus on agents' discrete choices such as a firm's entry-exit decision or a worker's retirement. Dynamic discrete choice models have been rigorously studied in labor economics and empirical industrial organization since they were pioneered by Miller84, wolpin, pakes1986, and rust. They have been used subsequently in the areas of consumer inventory Song2003, Hendel2006, dynamic demand of durable goods Schiraldi2011, Gowrisankaran2012, and firm entry and exit benkard, holmes.\footnote{dorapakes and AM10 provide the survey of applied works in dynamic discrete choice models in discrete time.} These examples, however, are all based on discrete time models.

More recently, authors have worked with continuous time dynamic discrete choice models due to their flexibility in separating the timing of actions in the model from the timing of data sampling and to their computational advantages in large-scale games. In such models, the state variables change in a stochastic, sequential manner which helps avoid the “curse of dimensionality” arising from the need to compute players' expectations over future states Dora2012.\footnote{In discrete time models all state variables change at the same time, so if there are $n$ state variables (i.e., one for each firm) and each state variable can change to one of $\kappa$ alternative values, the number of possible future states is $\kappa^n$. In contrast, in continuous time models only one state variable can change at any given instant, meaning that there are only $\kappa (n-1)$ possible future states for a player to consider.} \citet*{Arcidiacono2016}---henceforth \citetalias{Arcidiacono2016}---showed that continuous time models remain empirically tractable, can be estimated with continuous or discrete time data, can better approximate the economic reality of certain industries, and that the computational advantages can allow researchers to solve and simulate counterfactuals in large-scale models. Blevins16 presents theoretical, computational and econometric properties of continuous time dynamic discrete choice games and extends results from \citetalias{Arcidiacono2016}. Since then, CCP estimation in dynamic discrete choice models has been applied in various areas, including the transportation industry mazur, qin, supermarket industry Schiraldi2012, TV advertising deng, nightlife cosman, online games nevskaya, and job search Arcidiacono2019.

The goal of this paper is to introduce a nested pseudo likelihood (NPL) estimator for continuous time models, which we refer to as the CTNPL estimator. \citetalias{Arcidiacono2016} developed a two-step estimator for continuous time discrete choice models, but here we extend this estimator using insights from the discrete time NPL estimator of AM02,AM07 to iteratively impose the equilibrium conditions from the game to improve estimates of the structural parameters. AM02 originally developed the NPL algorithm and estimator in a single agent, discrete time setting setting and AM07 extended the algorithm and estimator to discrete time dynamic discrete choice games. bugni introduced the $K$-MD estimator, a sequential version of the minimum-distance estimator proposed by PS08, based on the NPL mapping.

In this paper we introduce the CTNPL estimator, derive the large sample properties, and evaluate its performance in the setting of a familiar dynamic oligopoly model. Compared to the two-step pseudo maximum likelihood (PML) estimator, the NPL estimator has a number of advantages. First, it does not require consistent estimates for the initial conditional choice probabilities. Second, the estimator performs better in finite sample as nonparametric estimates of choice probabilities (CCPs) can be imprecise, leading two-step estimators to be biased. This paper shows that these advantages also carry over to the CTNPL estimator for continuous time models. We also compare continuous time and discrete time models and (i) show that the CTNPL estimator has advantages in terms of convergence\footnote{Despite its advantages, PS10 showed that the NPL algorithm may fail to converge to the NPL estimator when the NPL mapping is unstable. They provided a simple two-firm example model illustrating the issue and subsequent authors such as Egesdal and Aguirregabiria2019 have studied the problem in more complex models. KS12 provided a local convergence condition for the NPL estimator in discrete time models, however, Aguirregabiria2019 show that even when the population mapping is stable the algorithm can fail to converge when the sample counterpart mapping is unstable. We derive a local convergence condition for continuous time models, which is motivated by that of KS12, and in our simulation results the condition is more likely to be satisfied in continuous time.} and (ii) evaluate the potential for biased estimates and misleading economic conclusions when estimating a discrete time model using discrete time snapshot data that was actually generated by a continuous time model.

The rest of the paper is organized as follows. Section 2 develops a dynamic discrete game in continuous time with an example. Section 3 introduces the CTNPL algorithm to estimate the parameters in the model. In Section (ref), we simulate a five-player game in retail industry and present the performance of the CTNPL estimator. Section 5 concludes.

Model

In this section, we briefly review the continuous time dynamic discrete game framework of \citetalias{Arcidiacono2016}. To provide a concrete example, we also introduce a continuous-time version of the five-player entry/exit model of AM07. This model serves not only as a running example but also as the basis for our Monte Carlo experiments in Section (ref).

Setting

There are $N$ agents in the model indexed by $i=1, \ldots, N$ who choose actions $j$ from a choice set $\mathcal{A}=\{0, 1, \ldots, J-1\}$ at decision times that occur in continuous time indexed by $t \in [0, \infty)$. Such decisions by agents result in endogenous state changes. The model also allows exogenous state variables. Decision times and exogenous state changes occur according to Poisson processes as detailed below.

State space. The states are discrete and finite, so every state at time $t$ can be represented by a state vector $x_k$ in a finite state space $\mathcal{X}=\{x_1, \ldots, x_K\}$ where each state is indexed by $k=1, 2, \ldots, K$.

State changes. There are two types of state changes in the model---endogenous state changes which are relying on each agent's decision and exogenous state changes driven by “nature.” As endogenous state changes only when an agent makes a choice, we can define a state continuation function $l(i,j,k)$ which maps an agent $i$'s choice $j$ and current state $k$ to next state $l$. We assume that choice $j=0$, where $l(i,0,k)=k$, is costless and that all choices $j$ are meaningfully distinct $l(i,j,k) \neq l(i,j',k)$ for all states $k=1, \ldots, K$. On the other hand, although exogenous state changes are not the result of an action by a player per se, we can think of them as actions by nature. When treated as a player in this way we will index nature by $i = 0$.

\addtocounter{example}{-1}

Poisson and Markov jump processes.\footnote{Definitions and notations in this section are based on Schuette.} Corresponding to the two types of state changes in the model there are also two types of Poisson processes governing the times of those state changes. First, in each state $k$ each player $i$ makes decisions about changing its endogenous state according to a Poisson processes with a rate parameter $\lambda_{ik}$. Recall that for such a Poisson process, the expected number of events during a one-unit time interval is $1/\lambda_{ik}$. For example, if the unit of time is one calendar year and we assume $\lambda_{ik}=\lambda=1$ for all $i$ and $k$, then each agent moves on average once per year. This would correspond closely to the usual discrete-time assumption of exactly one move per year. However, the Poisson assumption is more general since it allows, stochastically, for each player to make more or fewer moves per period. Because the probabilities of each choice vary, in general, across states, the state-to-state transition rates are endogenous and are state-and-firm specific. Second, in each state $k$ the exogenous state variables change according to another state-specific Poisson process. We assume that these Poisson processes are independent so that the probability that more than one component of the state vector $x_k$ changes at a single instant is zero. However, the processes are not identically distributed since they have different rate parameters.

Intensity matrices. Since Poisson processes are continuous-time Markov processes and the state space of the model is finite, the overall state transition process is a finite Markov jump process. Such a process can be characterized by a $K \times K$ intensity matrix (also known as a transition rate matrix or infinitesimal generator matrix) which contains the rates of all possible state-to-state transitions. This matrix is the instantaneous counterpart of the one-step transition probability matrix in a discrete time model.

Each component $q_{kl}$ of the intensity matrix $Q = (q_{kl})$ represents the rate of leaving state $k$ and transitioning to state $l$. The difference is that the intensity rate gives the transition rate for an instant instead of over one period of time. So, when we define transition probability matrix over some small time interval $h$ as $P(h)$, we can write $P(h) = I + Qh$. Note that as $h \to 0$, $P(h)$ approaches the identity matrix (under which no transitions occur). Then, for states $k$, $l$ with $k \neq l$, we have

We can formally define the intensity matrix $Q$:

where

For endogenous state changes, we can write $q_{kl}$ as the product of the decision rate in state $k$ and a choice probability. First, each agent decides whether or not to change the state according to Poisson process at rate $\lambda_{ik}$. To determine the choice probability, we must look closer at the player's problem. Players are forward-looking and discount future payoffs at rate $\rho \in (0, \infty)$. They observe other players' moves and optimally choose their own action $j\in \mathcal{A}$ based on their beliefs of other agents' actions, including state changes by nature. We denote the conditional choice probability of agent $i$ choosing action $j$ in state $k$ as $\sigma_{ijk}$. So, if at some state $k$ a player makes decisions at rate $\lambda_{ik}$ and chooses action $j$ by probability $\sigma_{ijk}$, then the rate of state changes due to player $i$ taking action $j$ in state $k$ is $\lambda_{ik} \sigma_{ijk}$.

Under the assumptions of the model so far the overall intensity matrix $Q$ can be written as a sum of individual player-specific intensity matrices: $Q = Q_0 + Q_1 + \dots + Q_N$, where $Q_0 = (q_{kl})$ denotes the intensity matrix for exogenous state changes by nature and the elements of $Q_0$ are denoted $q_{kl}$ (i.e., we drop the $i = 0$ subscript for nature). For players $i= 1, \dots, N$, each element of $Q_i$, denoted $q_{ikl}$, can be written as follows:

The first case represents state transitions out of the current state. The rate of a transition from $k$ to $l$ is the product of the decision rate in $k$ and the probability of choosing action $j$ which results a transition to state $l$. The second case is the net rate of leaving state $k$, and therefore is the negative of the sum of the off-diagonal elements in row $k$. Because firms may find it optimal to remain in the same state (choosing $j = 0$) we must allow for self-transitions, so the total rate of leaving state $k$ due to action by player $i$ need not equal the rate of decisions $\lambda_{ik}$. The third case covers states $l$ for which transitions from $k$ to $l$ cannot occur in a single instant.

\addtocounter{example}{-1}

Payoffs. In the continuous time setting we distinguish agents' flow payoffs from instantaneous choice-specific payoffs. First, agents receive flow payoffs at each state $k$ regardless of their choices. We denote the flow payoffs by $u_{ik}$ and assume $|u_{ik}|< \infty$ for $i=1, \ldots, N$ and $k=1, \ldots, K$. On the other hand, at a decision time when player $i$ chooses action $j$ in state $k$, the player receives a lump-sum instantaneous choice-specific payoff which is the sum of a deterministic component $\psi_{ijk}$, where $|\psi_{ijk}|<\infty$, and a stochastic component $\varepsilon_{ijk} \in \mathbb{R}$. The deterministic component $\psi_{ijk}$ is common knowledge to other players but the second part $\varepsilon_{ijk}$ is only observed by player $i$. However, players have common knowledge of the distribution of the stochastic components.

\addtocounter{example}{-1}

Bellman Optimality and CCP Representation

In a Markovian game, every agent plays a stationary Markov strategy based on their beliefs regarding other agents' choice probabilities. Let $\varsigma_i$ denote the beliefs held by player $i$ about each of the $(N-1)$ other players playing each of their $J$ choices in each of $K$ states. Therefore, $\varsigma_i$ is a collection of $(N-1) \times J \times K$ probabilities, denoted $\varsigma_{imjk}$ for each player $m \neq i$, choice $j$, and state $k$.

We now introduce the value functions and CCPs. Agents establish the value function based on their expectations about endogenous state changes due to other agents' moves, exogenous state changes due to nature, and their own future decisions. We follow the derivation of instantaneous Bellman equation in Blevins16. The probability that agent $i$ makes a decision during a small increment of time of length $h$ while in state $k$ is $\lambda_{ik} h$ under the Poisson assumption. Denoting each agent $i$'s discount rate as $\rho_i$, the discount factor for the time increment $h$ is $1/(1+\rho_i h)$. Given agent $i$'s beliefs, $\varsigma_i$, we can express the Bellman equation as below:

We now turn to each of the terms inside square brackets in the previous equation. First, over the small amount of time $h$ that the model remains in state $k$ player $i$ receives an integrated flow payoff of $u_{ik}h$. Second, if the state changes from $k$ to $l$ due to nature, which occurs with probability proportional $q_{kl}$ over the interval $h$, then player $i$ receives the continuation value $V_{il}$. Third, each of player $i$'s rival players, indexed by $m \neq i$, may make a decision with probability proportional to $\lambda_{mk}$ over the time interval $h$. When this occurs, player $i$ believes that player $m$ plays action $j$ in state $k$ with probability $\varsigma_{imjk}$. When this happens, player $i$ receives a continuation value $V_{i, l(m,j,k)}$ where $l(m,j,k)$ denotes the index of the continuation state following the action of player $m$. Fourth, at rate $\lambda_{ik}$ player $i$ makes a decision and optimally chooses an action $j$. However, the values of the stochastic choice-specific shocks have not yet been realized, so player $i$ receives receives the expected maximum value of $\psi_{ijk}+\varepsilon_{ijk} + V_{l(i,j,k)}$ where $j$ is chosen optimally at the future decision time. Finally, the last (non-negligible) term accounts for the case where no state changes occur over the time interval $h$ and so the continuation value is simply $V_{ik}$.

By rearranging and letting $h \to 0$, we arrive at a simpler expression for the Bellman equation:

Now we define the best response function for each agent. A Markov strategy for agent $i$ is a mapping $\delta_{i}$ from each state $(k, \epsilon_{ik}) \in \mathcal{X} \times \mathbb{R}^J$ to an action $j \in \mathcal{A}$. Then, the best response for an agent $i$ is defined as:

Then, the choice probability for each agent becomes:

We now collect assumptions needed for the existence of an equilibrium.

Assumptions (ref) and (ref) are needed to define a continuous-time finite Markov jump process. In Assumption (ref), we rule out infinite rates and payoffs to make it possible to estimate by restricting the value to a finite number.

Assumption (ref) is common in the literature, as in the case of Assumption 1 of AM02 and AM07. Assumption (ref) requires that different choices should result in observationally distinct state changes. For example, choices $j=1$ and $j=2$ should not be defined separately if they in fact always result in the same state changes. It also involves a normalization on the baseline payoff/cost associated with inaction. Finally, the distributional assumption on $\varepsilon$ is widely in the previous literature. For example, see Assumption 2 of AM02 and AM07.

We define Markov perfect equilibrium (MPE) as in AM07 and \citetalias{Arcidiacono2016}.

By Proposition 5 in \citetalias{Arcidiacono2016}, under Assumptions 1--5, a Markov perfect equilibrium exists. Moreover, under Assumptions 1--5 and assuming that $\lambda_{ik}$ is constant across all agents and states denoted by $\lambda$, \citetalias{Arcidiacono2016} established the following linear representation of the value function, where $V_i(\theta,\sigma)$ is a $K$-vector:

where $\Sigma_m(\sigma_m)$ is the $K\times K$ state transition matrix induced by the actions of player $m$ given the choice probabilities $\sigma_m$ and where $E_i(\theta, \sigma)$ is a $K \times 1$ vector where each element $k$ is the ex-ante expected value of the choice-specific payoff in state $k$, $\sum_j \sigma_{ijk}[\psi_{ijk}+e_{ijk}(\theta, \sigma)]$ where $e_{ijk}(\theta, \sigma)$ is the expected value of $\varepsilon_{ijk}$ given that choice $j$ is optimal,

We now have two important equations that forms a players' decision problem.

We now introduce a policy iteration operator $\Psi$ in the space of conditional choice probabilities. Substituting (1) into (2),

where $\Upsilon$ is a policy valuation operator that maps an $NJK\times 1$ vector of conditional choice probabilities into an $NK\times 1$ vector in value function space. $\Gamma$ is a policy improvement operator that maps an $NK \times 1$ vector in value function space into $NJK\times 1$ vector of conditional choice probabilities.

Sequential vs. Simultaneous State Changes

The main fundamental difference between the continuous-time model we consider and traditional discrete-time models is not in the way time is measured or how payoffs are discounted and accrued, but rather that state changes occur in a stochastic, sequential manner. This leads to both a reduction in computational complexity and a dampening in strategic interaction. This does not, however, mean that in general there is unique equilibrium or that all fixed points are stable, but rather it can lead to improvements in convergence.

In terms of computation, in the continuous time model there is a reduction in the number of future possible states to consider because at any point in time the state can only be affected by a single agent's choice or by nature. Therefore, the number of future states is linear in the number of players. On the other hand, in discrete time all agents and nature move simultaneously and the number of possible future states increases exponentially in the number of players. This leads to a relatively dense transition matrix over a discrete unit of time as opposed to a relatively sparse intensity matrix in continuous time.

To give a simple example, suppose there are $N$ players and each player can choose from $J$ actions. In the continuous-time model, there are only $N \times J$ possible future states at a given instant (i.e., which player moves next and which choice do they make). In discrete-time with simultaneous moves, there are $J^N$ possible future states to consider. The difference will increase dramatically as either $N$ or $J$ get larger. So with $N = 5$ players and $J=2$ as in our application, the difference is already three-fold: $5 \times 2 = 10$ continuation states in continuous time versus $2^5 = 32$ in discrete time.

The two main differences with our model and a typical discrete time model are the way payoffs are accrued as flows over time and the sequential nature of moves. The latter, however, is the key distinction. To show this, we briefly consider a simultaneous move model in continuous time and show that it is equivalent to a transformation of a discrete time model. The Bellman equation in this model can be expressed as follows:

where $\tau$ is the random holding time until the next simultaneous move arrival, $j_i$ is firm $i$'s choice when the next move occurs, $\varsigma_{ik}(j_{-i})$ denotes player $i$'s belief that rival players will choose actions $j_{-i} = (j_1, \dots, j_{i-1}, j_{i+1}, \dots, j_N)$ resulting in the continuation state $k' = l(j_{1},\dots,j_{N}, k)$. This expression is from the perspective of an arbitrary point in time which is not necessarily a move arrival time. The first term inside the expectation is the flow utility accrued until the random next move increment $\tau$ and the second term is the discounted expected continuation value received when choosing the next action, given beliefs about rival actions. As in discrete time (and contrary to our continuous time model) there are no state changes between decision times.

To see that this model can be thought of as transformation of a standard discrete time model, define a transformed discount factor $\beta = \mathrm{E}\left[ e^{-\rho \tau} \right]$, where we assume the distribution of the holding time $\tau$ is independent of $k$, and a transformed choice-specific utility function $\tilde{u}_{ijk}(\varepsilon_{i}) = \psi_{ijk} + \mathrm{E}\left[ \int_0^\tau e^{-\rho t} u_{ik'}\,dt \mid k, j_i = j \right]$. Then, we can restate the Bellman from the perspective of a decision time, as is usually done in discrete time. Given choice-specific errors $\varepsilon_{ik}$ for player $i$, which are observed at a decision time, we have:

The representation on the last line is in the form of a standard dynamic discrete choice game in discrete time. Therefore, the key difference between the continuous-time model discussed in the paper and a standard discrete-time model is the stochastic, sequential nature of moves rather than the rather than the way time is measured, or that payoffs are accrued as flows.

One could also specify a sequential-move model in discrete time, but in that case one would need to also specify the order of moves, the number of moves by each player during a period, and a fixed time period between moves. Some advantages of the current continuous time specification are the mathematical tractability in terms of a Markov jump process, the fact that the order of moves is stochastic and fully flexible (e.g., allowing multiple actions by a single player per “period”), and that the times between actions are stochastic rather than fixed.

The CTNPL Estimator

CTNPL Algorithm

Before describing the CTNPL algorithm, we first introduce two more assumptions for identification and estimation with continuous time data observed only at fixed time intervals (Assumptions 6, 7 in ABBE, 2016; Assumptions 8, 9 in Blevins, 2016).

For continuous time models, we consider two types of data. The first type is continuous time data which is observed every instant. Stock prices can be an example close to this type. Second, some data generated by a continuous time model can be only observed at discrete times. For example, population can change any time during the year but annual population data may only be observed once per year. We show how to construct log likelihood functions for estimation using both types of data. We assume throughout that we have independent and identically distributed data across markets and that the Markov process is irreducible.

Fully observed continuous time data. Consider a dataset of observations in market $m$ and $n$-th move, $\{k_{mn}, t_{mn}: m=1, \ldots, M, n= 1, \ldots, T_m\}$ sampled in interval $[0, \bar{T}]$. State $k_{mn}$ denotes the state immediately before state change at time $t_{mn}$ and time $t_{mn}$ is the time of $n$-th state change in market $m$.

We follow the derivation in Section 6.1. in \citetalias{Arcidiacono2016} to construct the likelihood function. Let $h$ denote a $K(K-1)+NJK$ vector of hazard rates for state change:

The probability that there is a state change within $\tau$ units of time is:

This is because state changes due to nature occur in state $k$ according to Poisson processes with rate parameters $q_{kl}$, for each state $l \neq k$, and each player $i$ takes some action according to a Poisson process with rate parameter $\lambda_{ik}$.

When there is a state change from state $k$, conditional probability that the change is due to agent $i$'s action $j$ is

and conditional probability that it is due to nature is

Defining $g(\tau, k; h)=\exp\left[-\tau(\sum_{l \neq k} q_{kl} + \sum_i \lambda_{ik}\sum_{j \neq 0}\sigma_{ijk})\right]$, the likelihood of state change is

Let $\tau_{m,T+1}$ be the time interval between the last state change at time $T$ and $\bar{T}$, and $k_{m,T+1}\equiv k_{m,T}$. We introduce an indicator function $I_{mn}(i,j)$ which is 1 when $n$-th state change at market $m$ is induced by agent $i$'s action $j$ and $0$ otherwise. We also define $I_{mn}(0,l)$ as 1 when $n$-th state change at market $m$ is by nature's move to state $l$ and $0$ otherwise.

Combining the results above, the likelihood function becomes

The first term inside the summation is the common term in (ref) and the second term is from the likelihood of state changes due to nature. The third term is considering agents' moves and the last term is the likelihood of observing no state change after time $t_{m,T}$.

Since state changes due to nature are exogenous, the log-likelihood function of the model can be decomposed into terms involving the conditional choice probabilities of players and nature's transition probabilities. Consistent estimates for elements of $Q_0$, $q=(q_{12}, \ldots, q_{K-1,K})$, can be obtained from transition data without having to solve the dynamic game. Therefore, we assume in the remainder of the paper that $q$ is known and focus on the estimation of $\theta$ and $\sigma=(\sigma_{111}, \ldots, \sigma_{NJK})$. Then, the likelihood function becomes

Discretely observed data. Consider a dataset $\{k_{mn}: m=1, \ldots, M, n=0, \ldots, T\}$ consisting of observations that are sampled at times on the lattice $\{n\Delta:n=0, \ldots, T\}$. As before, we assume that $q$ is known. Given $q$ and $\sigma$, we can construct a transition matrix. Define the pseudo likelihood function

where $P_{k,l}(\Delta;\Psi(\theta, \sigma))$ denotes the $(k,l)$ element of the transition matrix induced by $\sigma=\Psi(\theta, \sigma)$.

We calculate $P(\Delta)$ using matrix exponential as in \citetalias{Arcidiacono2016}. First, assume that we have a continuous time data observed only at discrete times with unit interval, $\Delta=1$. Let $Z(\theta, \sigma)^r$ denote the transition matrix from some state $k$ to another state $k'$ after an unit interval of time $\Delta=1$ in $r$ steps. Then, let $a_{m,n}$ denote an indicator vector for an observation $n$ in market $m$ which is one in position $k_{m,n}$ and zero elsewhere. We can write the likelihood function as below:

Then, using the definition of matrix exponential, we can rewrite the previous equation as:

where $Q$ is the aggregate intensity matrix for the model.

CTNPL algorithm. We adapt the NPL algorithm to obtain the CTNPL estimator in the present continuous time model. Let $\hat{\sigma}^0$ be an initial estimate or guess of the vector of players' choice probabilities. Given $\hat{\sigma}^0$, for $l \geq 1$, perform the following steps:

Iterate in $l$ until convergence in $\sigma$ and $\theta$ is reached. Since we usually have observe continuous time data at discrete times in practice, we focus on properties of the CTNPL estimator using the likelihood function in (ref) in next section.

Remark on the definition of the NPL estimator. AM02 define $\hat{\theta}^l$ as policy iteration (PI) estimator and the estimation procedure as the NPL algorithm. In AM07, they define the same estimator as $K$-stage estimator\footnote{They call it $K$-stage estimator as they use $K$ as a notation for the number of stages. They also define ($\hat{\theta}^1$, $\hat{\sigma}^1)$ as the Pseudo Maximum Likelihood (PML) estimator.} and define the NPL estimator as the limit of the sequence $\{\hat{\theta}^l, \hat{\sigma}^l\}_{l=1}^L$ with certain conditions. Specifically, if the sequence $\{\hat{\theta}^l, \hat{\sigma}^l\}_{l=1}^L$ converges, its limit $(\tilde{\theta}, \tilde{\sigma})$, which is called NPL fixed point, satisfies two conditions: \[\tilde{\theta} = \operatorname*{argmax}_{\theta \in \Theta} L(\theta, \tilde{\sigma}) \quad \text{and} \quad \tilde{\sigma}=\Psi(\tilde{\theta}, \tilde{\sigma}).\] It is possible that there exist multiple NPL fixed points, so they choose the one with highest likelihood and define it as the NPL estimator, $(\hat{\theta}_{\text{NPL}}, \hat{\sigma}_{\text{NPL}})$. Subsequent studies use the definition of NPL estimator in AM07, so we follow the same definition PS10, KS12. Henceforth, we define $(\hat{\theta}^l, \hat{\sigma}^l)$ as the PI estimator and $(\hat{\theta}, \hat{\sigma})=(\hat{\theta}_{\text{CTNPL}}, \hat{\sigma}_{\text{CTNPL}})$ as the CTNPL estimator, dropping the subscript for simplicity.

Large Sample Properties

In this section, we consider the large sample properties of the CTNPL estimator. We start with the CTNPL estimator in the case of single agent continuous time models, then we consider both the PI estimator (for a finite number of iterations $l$) and the CTNPL estimator continuous time dynamic games.

Single Agent Dynamic Discrete Choice Models

The asymptotic properties of the CTNPL estimator for single agent models depend on a zero Jacobian property for $\Psi(\theta, \sigma)$. Specifically, we show that the Jacobian matrix $\Psi_\theta \equiv \nabla_{\theta}\Psi(\theta^*, \sigma^*)$ is equal to the zero matrix in agent models. This result is presented formally in Proposition (ref) immediately below, and we then show that it facilitates adaptive two-step estimation in Proposition (ref), where we show the estimator is efficient. The same zero Jacobian property will be used later, in Section (ref), where we show that it also ensures local stability of the estimator. All proofs are provided in Appendix (ref).

Next, Proposition (ref) shows that, under certain regularity conditions, the NPL estimator in a continuous time single agent discrete choice model is consistent, asymptotically normal, and efficient.

Conditions (a), (b), and (c) are usual regularity conditions, while (d) is needed for identification. Condition (e) requires that the initial CCP estimates are consistent. As can be seen from the limiting distribution in (ref), the asymptotic variance is not affected by the first-step estimation of the CCPs. In other words, in a single agent model there is no efficiency loss from two-step estimation, as was established in discrete time models by AM02. This is due to the so-called zero Jacobian property, which we show also holds in continuous-time models below in Proposition (ref), where we also relate the property to convergence of the algorithm.

Dynamic Discrete Games

We now extend the model to a dynamic discrete game with $N$ players and present the large sample theory first for the PI estimator for $l = 1, \dots, L$ in Proposition (ref) and then the CTNPL estimator in Proposition (ref).

The results above are for the PI estimator $\hat{\theta}^l$ for $l =1, \ldots, L$. AM07 provide large sample properties for the NPL estimator (i.e., at convergence, if the algorithm converges). We now present similar properties for the CTNPL estimator $\hat{\theta}$ in our continuous time model. A local convergence condition for $\hat{\theta}^l$ will be provided in the next section.

Proposition (ref) below establishes the large sample properties for $(\hat{\theta}, \hat{\sigma})$, but we first introduce a few definitions and notation from AM07. Let $\phi_M(\cdot)$ denote the NPL operator used to represent an iteration of the algorithm: \[\phi_M(\sigma) = \Psi(\tilde{\theta}_M(\sigma), \sigma) \quad \text{where} \quad \tilde{\theta}_M(\sigma) \equiv \operatorname*{argmax}_{\theta \in \Theta} L_M(\theta, \sigma).\]

Let $\Upsilon_M$ be the set of fixed points of $\phi$, $\Upsilon_M \equiv \{(\theta, \sigma) \in \Theta \times [0,1]^{NJK}:\theta = \tilde{\theta}(\sigma) \ \text{and} \ \sigma = \phi_M(\sigma)\}$. Then, choosing the fixed point that has the maximum value of the likelihood, \[(\hat{\theta}, \hat{\sigma}) \equiv \operatorname*{argmax}_{(\theta, \sigma) \in \Upsilon_M} L_M(\theta, \sigma).\] We denote the population counterparts of $\tilde{\theta}_M(\sigma)$ and $\tilde{\phi}_M(\sigma)$ as $\tilde{\theta}^*(\sigma)\equiv \operatorname*{argmax}_{\theta \in \Theta} L(\theta, \sigma)$ and $\phi^*(\sigma) = \Psi(\tilde{\theta}^*(\sigma),\sigma)$.

Assumptions from (a)--(d) are the same as Assumptions (a)--(d) in Proposition (ref). Assumptions (e)--(g) correspond to Assumptions (v)--(vii) of Proposition 2 in AM07. Note that consistency of $\hat{\sigma}^0$ is not required.

Convergence of the CTNPL Algorithm

Originally introduced for discrete time models, the NPL algorithm is a sequential method to find the NPL estimator. This is why it is possible for the NPL algorithm to fail to converge to a consistent estimator even if the NPL estimator is consistent. Ideally, the NPL algorithm could converge to the consistent estimator if it can be evaluated at every fixed point, but this may be infeasible in practice.

Starting from PS10, several papers have investigated the convergence of the NPL algorithm. KS12 show that a key determinant of the convergence of the NPL algorithm is the contraction property of the mapping $\Psi$ and propose a local convergence condition for NPL estimator in discrete time. Aguirregabiria2019 investigate this further and show that even when the population mapping is stable the algorithm can fail to converge when the sample NPL mapping is unstable. We extend these arguments to the CTNPL estimator and derive a local convergence condition for continuous time models that is analogous to the condition of KS12. Although we see improved convergence in practice due to the sequential nature of moves, as discussed in Section (ref), it is still possible to have multiple equilibria and unstable equilibria in the continous time setting.\footnote{We explore a simple $2 \times 2$ entry model with multiple equilibria in Appendix (ref).}

For simplicity, we define $\Psi_\theta \equiv \nabla_{\theta}\Psi(\theta^*, \sigma^*)$ and $\Psi_\sigma \equiv \nabla_{\sigma}\Psi(\theta^*, \sigma^*)$. Let $P$ be an aggregate transition probability matrix between states where the elements $P_{kl}$ of $P$ are \[P_{kl} =

.\]

Let $P^* = \vec P(\Delta; \Psi(\theta^*, \sigma^*))$ denote the $K^2 \times 1$ vectorized version of $P(\Delta; \Psi(\theta^*, \sigma^*))$. Then, define a scalar $a_{ij,kl}$ as: \[a_{ij,kl} =

\] We then construct a $NJK \times K^2$ matrix, denoted $A$, by stacking $a_{ij,kl}$ accordingly, and define $\Delta_\sigma=A \operatorname{diag}(P^{*})^{-1}A'$. Then, we can rewrite $\Omega_{\theta \theta'} = \Psi_{\theta}^{\prime}\Delta_\sigma\Psi_{\theta}$ and $\Omega_{\theta \sigma'} = \Psi^{\prime}_{\theta}\Delta_\sigma\Psi_{\sigma}$. We also define $M_{\Psi_\theta}\equiv I-\Psi_{\theta}(\Psi_{\theta'}\Delta_\sigma \Psi_\theta)^{-1}\Psi_{\theta'} \Delta_\sigma$.

We now present a local convergence condition for the CTNPL estimator $\hat{\sigma}^{l}$. If $\hat{\sigma}^l$ converges to $\hat{\sigma}$, $\hat{\theta}^l$ converges to $\hat{\theta}$ by the continuity of $L(\theta, \sigma)$ and applying the Theorem of the Maximum in (ref). So, it is sufficient to show the convergence for $\hat{\sigma}^l$. The convergence condition below is analogous to Proposition 2 in KS12.

In single agent models, the Jacobian matrix $\Psi_\sigma$ is zero at the fixed point $\sigma^* = \Psi(\theta^*, \sigma^*)$ by Proposition (ref), it follows that $r(M_\Psi \Psi_\sigma)$ is zero. Then, by Proposition (ref), the CTNPL estimator is stable and always converges locally to $(\hat{\theta}, \hat{\sigma})$ in single agent models. Next, we will investigate many of the properties we have derived in the context of a simulation study.

Monte Carlo Experiments

In this section we present the results of a series of Monte Carlo experiments carried out using the model of Example 1 from Section 2, which is a continuous time version of the dynamic discrete game described in Section 4 of AM07. We also provide further implementation details of the CTNPL algorithm for this model in Appendix (ref).

Data Generating Process (DGP)

We assume the profit functions of firms are:

The parameters we estimate are the fixed costs $\theta_{FC,i}$, entry costs $\theta_{\text{EC}}$, competition effect $\theta_{\text{RN}}$, and market effect $\theta_{\text{RS}}$. Fixed costs $\theta_{FC,i}$ are set as $(\theta_{\text{FC,1}}, \theta_{\text{FC,2}}, \theta_{\text{FC,3}}, \theta_{\text{FC,4}}, \theta_{\text{FC,5}}) = (-1.9, -1.8, -1.7, -1.6, -1.5)$. The parameter $\theta_{\text{RS}}$ equals to 1. We run six experiments varying by entry costs $\theta_{\text{EC}} = (1.0, 2.0, 4.0)$ and $\theta_{\text{RN}}=(0.0, 1.0, 2.0)$. The stochastic component in instantaneous payoff $\epsilon_{ijk}$ are independently and identically distributed and follow Type 1 extreme value distribution.

The support of the logarithm of market size is $\{1,2,3,4,5\}$ and each player chooses an action from $a_{ik} = \{0,1\}$. So, the size of state space is $K = 5 \times 2^5 = 160$. We assume that market size increases or decreases by at most 1 step at a single instant and that the rate is constant across states $k$. Let $q_1$ and $q_2$, respectively, denote the rate of market size increases and decreases, respectively. These two parameters fully characterize nature's intensity matrix $Q_0$. As mentioned above, we can obtain consistent estimates for $q_1$ and $q_2$, so for our experiments we assume that $Q_0$ is known and focus on estimating firms' payoff parameters. In particular, we choose the intensity matrix $Q_0$ so that the discrete-time transition probability matrix for market size is as in AM07\footnote{The transition probability matrix used for market size $s_k$ in AM07 is \[

.\]}. Throughout the experiments, we fix the discount rate at $\rho_{ik}=0.05$ and the move arrival rate at $\lambda_{ik}=1$ for all $i=1, \ldots, N$ and $k=1, \ldots, K$.

We assume in this section (unless specified otherwise), that the DGP is a continuous time model, however, we consider two distinct sampling regimes for estimation. First, we consider continuous time data observed every instant. Since the model is a finite-state jump process, it is equivalent to observe each jump time and the resulting state. We refer to this as continuous time data. To generate continuous time data, we calculate the MPE of the game, obtain the steady-state distribution, and draw the initial states $k_{m,0}$ for each market $m$. From these initial states, we draw the subsequent actions and state $(a_{k_{m,n}}, x_{k_{m,n-1}})$ using the equilibrium conditional choice probabilities. Second, we also consider discrete time data observed at fixed intervals of length $\Delta = 1$. We refer to this as discrete time data, noting that the underlying DGP is a continuous time model. In this case, initial states are also drawn using the steady-state distribution and then we draw the future states according to the transition probability matrix over the time interval, $P(\Delta)$.

For each experiment, we carry out 100 replications using a sample of $M = 400$ markets in each. For simplicity, we focus on the case where there is one observed continuous-time event or discrete-time observation per market. Table (ref) summarizes the DGP in the case of discretely-observed data. The parameters for the first three experiments differ only by the strategic interaction parameter, $\theta_{\text{RN}}$, which is increasing from Experiment 1 to 3. Increasing $\theta_{\text{RN}}$ decreases the average number of active firms. In this setting, both the average number of entries and exits are increasing when $\theta_{\text{RN}}$ increases. As excess turnover increases, there will be a larger change in the number of active firms between periods. As a result, the AR(1) coefficient for the number of current active firms decreases. As $\theta_{\text{RN}}$ decreases the flow payoff for all firms, firms are less likely to be active regardless of fixed costs.

In Experiments 4--6, $\theta_{\text{EC}}$ varies from 0 to 4. The number of active firms increases as $\theta_{\text{EC}}$ increases, which might be surprising, but this is because the probability of being active differs across firms. Specifically, more efficient firms tend to stay active as the entry cost increases. This can be seen with Firms 4 and 5, which have lower fixed costs.

Estimation Results

We consider several choices for the initial values of the CCPs: (i) true CCPs, (ii) frequency estimates, (iii) semi-parametric logit estimates (using market size and number of rival firms as explanatory variables), and (iv) random $\operatorname{U}(0,1)$ draws. Although (i) is infeasible, it yields a $\sqrt{M}$-consistent, asymptotically normal, and efficient estimator that serves as a benchmark AM07. For (ii), (iii), and (iv), we consider the two-step estimator ($l=1$) and the converged CTNPL ($l = 20$).

Table (ref) shows the means and standard deviations, in parentheses, of the Monte Carlo replications in the case of continuous time data. Based on the same replications, Table (ref) displays the square-root of the mean square error (RMSE) of each estimator relative to the infeasible two-step PML estimates. Using these two tables we can compare the performance of the various estimators.

First, we note that the CTNPL estimator converged to the same estimates within 20 iterations regardless of which CCP estimates were used for initialization (frequency estimates, semi-parametric logit estimates, or random $\operatorname{U}(0,1)$ draws). Therefore, we report these in a single row denoted “CTNPL” in the table.

Of the two-step estimators, initializing using the semi-parametric logit estimates appears to the best choice in terms of low biases, standard deviations, and therefore low relative RMSE values. Not surprisingly, using inconsistent, random $\operatorname{U}(0,1)$ starting values is a worse choice. Perhaps surprisingly, the frequency estimates are the worst choice for the initial CCPs. Even though frequency estimates are consistent, they result in a large bias with low variance across all parameters in Table (ref) which in turn leads to high relative RMSE values in Table (ref).

Overall, the performance of the CTNPL estimator---regardless of how it is initialized---is on par with the infeasible infeasible two-step PML estimator (which is initialized using the true CCPs). The RMSE values for the CTNPL estimator are close to one, meaning the estimators have similar performance, and in most cases the RMSEs are lower than those the other feasible two-step estimators. For some parameters in some experiments, the two-step semi-parametric logit estimator performs slightly better than CTNPL, but the CTNPL estimator is much more robust than the two-step PML estimator in terms of how it is initialized. Even if the frequency estimates are used to initialize the CTNPL estimator, the finite sample bias can be reduced by repeatedly imposing the MPE conditions through iteration.

We also carried out these experiments with a much smaller sample size $n=100$. We report the results in Tables (ref) and (ref). Here, the benefits of iterating are more pronounced: Even the 2S-Logit estimates have large amounts of finite sample bias and the improvements from iterating using CTNPL are more substantial.

Finally, Table (ref) and (ref) report the similar results for estimation using discretely observed data. In this case, the results are even more distinct: the best two-step PML estimator (semi-parametric logit) exhibits more bias while the CTNPL estimator remains closer to the infeasible two-step estimator. The bias is particularly acute for the strategic interaction parameter $\theta_{\text{RN}}$.

Strategic Interaction and Convergence

In the specification of Experiment 1, the strategic interaction between agents, denoted by $\theta_{\text{RN}}$, is set to zero which means that this setting corresponds to a collection of single agent models. In light of the zero Jacobian property of Proposition (ref), the $\Psi$ mapping is stable in this case and the algorithm will converge. However, as $\theta_{\text{RN}}$ increases it becomes more likely that the $\Psi$ mapping is unstable (both in a finite sample and in the population). KS12 showed, using a two-firm example, that a MPE for which the local convergence holds exists if the contemporaneous and dynamic interaction between firms is small.

In Section 2.3, KS12 showed that $r(M_{\Psi_P} \Psi_P)$ is close to $r(\Psi_P)$ in a typical setting where the number of states is larger than the number of parameters to estimate. This is also true in continuous-time games, so similarly we will focus here on $r(\Psi_\sigma)$ given that $\Psi_\sigma$ is often related to the characteristics of the economic model KS12.

Aguirregabiria2019 study the relationship between $\theta_{\text{RN}}$ and the spectral radius $r(\Psi_P)$ for the discrete time NPL estimator using the five player example game of AM07. We conjecture that $r(\Psi_\sigma)$ is smaller in continuous time games than the spectral radius in a comparable discrete time game since continuous time games do not allow simultaneous moves between agents, making it more likely that the best response mapping is more stable. We investigate this in the context of the model used for our Monte Carlo experiments.

Figure (ref) shows that the conjecture holds in the present model. Displayed in the top panel is our replication of a similar figure in Aguirregabiria2019. This figure shows the relationship between the spectral radii for different values of $\theta_{\text{RN}}$ using a discrete time version of the five player game in AM07. In the figure, the spectral radius becomes larger than 1 when $\theta_{\text{RN}}$ is larger than 2.2. The lower panel of Figure (ref) shows the relationship between the spectral radius and strategic interaction parameter in the continuous time model. To construct the figure, we use the same setting of Experiment 1 above and examine how $r(\Psi_\sigma)$ changes with respect to $\theta_{\text{RN}}$. To produce the figure, we generate different data sets for each value of $\theta_{\text{RN}}$ and calculate the spectral radius of $\Psi_{\sigma}$. Even when $\theta_{\text{RN}}$ increases to 5 the spectral radius is 0.6, still far below the threshold for instability. On the right y-axis, we also report the average number of active firms in each game. As the strategic interaction parameter increases, the number of firms varies from almost 4 to around 1.

Although we can see that the number of active firms in the discrete time and continuous time models is similar, the meaning of a particular value for the strategic interaction parameter $\theta_{\text{RN}}$ is different in the two models. In order to provide another means to compare the spectral radii, we also compare the discrete time model with the best-fit continuous time model in Figure (ref). To do so, we use the same discrete time data for each replication and use it to estimate the continuous time model. Then we calculate the Jacobian $\Psi_\sigma$ as before and calculate the spectral radius.

As such, the horizontal axis of Figure (ref) has two labels. The upper labels denote the original values of $\theta_{\text{RN}}$ used to generate the discrete time data. The numbers in parentheses below are the corresponding estimates of $\theta_{\text{RN}}$ from the continuous time model. Note that when $\theta_{\text{RN}}$ is zero in continuous time, the spectral radius is also zero as established in Proposition (ref). Note that the continuous time estimates for the strategic interaction parameter are lower, and sometimes even negative, but the spectral radii are calculated using the absolute values of the eigenvalues so they are always positive. As $\theta_{\text{RN}}$ increases to 11, spectral radius is at most around 0.23, even farther from one than before, so it it highly unlikely that there will be any convergence issues. As a result, in this example we can allow for a wider range of strategic interaction values than in discrete time without worrying about convergence to an inconsistent estimator. Even though the estimates always converged for the continuous time model, while the discrete time model failed to converge in many cases, this is not a universal result. In general, there can be multiple equilibria in continuous time models and unstable CTNPL fixed points, as discussed in Appendix (ref). However, the sequential nature of moves in continuous time appears to improve convergence in practice in this heterogeneous agent entry-exit model.

Estimation of Misspecified Discrete Time Models

Finally, in this section we consider the effects of misspecification when one estimates a simultaneous move, discrete time model but in reality the DGP is a continuous time model with asynchronous moves. We focus on this direction of misspecification because currently the most common practice is for applied researchers to use simultaneous move, discrete time models estimated using snapshot (time-aggregated) data. Continuous time models make up a small, but emerging share of the literature and we consider the other direction of misspecification in Appendix (ref).

It is not a foregone conclusion that estimating a misspecified model would lead all parameter estimates and counterfactuals to be incorrect. Any finite-state, continuous-time Markov jump process, including those generated by the structural model we consider, has an embedded discrete time Markov chain, or jump chain, that characterizes transitions at jump times without regard for the time elapsed between jumps karlin81second. Therefore, one may wonder whether the discrete time game could approximate the continuous time game well enough to avoid bias in some parameters. We show that this is not the case in our example entry model: the transition matrix is only one component of the complete structural model and the specification of sequential vs simultaneous moves is also important and ultimately still leads to misspecification bias.

We report estimates for the misspecified discrete time NPL estimator in Table (ref) along with the correctly specified CTNPL estimates for comparison (the latter being reproduced from Table (ref)). There is bias in all parameters, however it is important to note that there are severe biases in the important strategic interaction and entry cost parameters. It is also of interest to learn how these biases behave in different settings. In particular, the biases tend to be larger when entry costs are smaller.

Although the estimates for $\theta_{\text{RS}}$ have small standard deviations, the biases are larger than those of estimates from correctly specified models in all experiments. This result suggests that when a researcher wrongly chooses a discrete time model to estimate parameters from continuous data, it is possible to arrive at inconsistent estimates with large finite sample bias although seeming precise with small standard errors.

The underlying issue is that the discrete time model conflates higher rates of entry due to low entry costs with higher rates of entry due to low levels of competition. To see this, consider a two-firm model and suppose the market is empty at time $t = 0$. Suppose firm 1 first enters at time $t = 0.1$ and firm 2 later decides not to enter at time $t = 0.2$. Suppose that this market structure remains until time $t=1$. Although firm 1 has spent nearly the entire unit of time in the market, the discrete time model interprets this as no firms in the market at time $t = 0$ and a firm-1 monopoly beginning at time 1. Through the discrete time lens, firm 2 chose to not enter an empty market and therefore entry costs must be high. On the other hand, the continuous time model---even with discrete time data---allows for the possibility that firm 1 entered earlier and firm 2 may have chosen to remain out because of the competitive effect and the presence of firm 1 rather than high entry costs.

Figure (ref) illustrates the possibility of misleading estimates. We plot the misspecified discrete time model estimates from Experiment 1 and the true values. Even though the confidence intervals for the discrete time estimates are small, the estimates are far from the true parameters. This suggests that a researcher should carefully specify the model by considering whether sequential moves are important and understanding how and when the state variables change.

We can also examine how this problem affects counterfactuals. Dynamic game estimation results are often used for estimating the impact of a policy affecting firms' entry-exit decisions. Suppose that the entry costs are one million dollars and the government is considering subsidizing firms by two hundred thousand dollars. In particular, the policy would reduce the fixed costs by \$200K. Since the correct model and the misspecified model have different estimates for entry costs and fixed costs, the policy will result in different steady state outcomes.

To compare the different counterfactual predictions, we change the parameter values according to the counterfactual policy, recalculate the equilibrium, and compare the results over 50,000 simulations. Table (ref) presents the average number of active firms before and after subsidization. The first column is the average number of active firms before firms receiving the subsidy. Then, in Experiment 1, if firms receive the subsidy the continuous time model predicts that the number of active firms increase by 5.6% but the misspecified discrete time model suggests 20.4% increase in the number of active firms. The prediction from the discrete time model is four times larger. This overestimation of the effect when using the misspecified model also occurs for the other experiments.

Conclusion

This paper introduced an NPL estimator for dynamic discrete choice models in continuous time, which we refer to as the CTNPL estimator. We derived its properties, and demonstrated the performance in a series of Monte Carlo experiments involving a model with five heterogeneous firms. Specifically, we first showed that the CTNPL estimator is consistent and asymptotically normal both with and without initial consistent and asymptotically normal CCP estimates. Second, we presented a local convergence condition in the iterative CTNPL algorithm. Researchers have documented problems regarding the convergence of the NPL algorithm in discrete time. We showed that the algorithm always converges in continuous-time single agent models and that provided simulation evidence that convergence failures are much less likely to affect comparable continuous-time games. Third, our Monte Carlo experiments based on those of AM07 showed that the CTNPL estimator is more robust than two-step estimators initialized from estimates or random draws for the CCPs. Finally, our results highlight the potential for economically misleading estimates and counterfactuals when estimating discrete time models in cases where events in the data generating process are unfolding in continuous time.