Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
80,375 characters · 21 sections · 0 citation commands
Duality in dynamic discrete choice models
\pagenumbering{gobble}
\linespread{1.5}
{ Empirical research utilizing dynamic discrete choice models of economic decision-making has flourished in recent decades, with applications in all areas of applied microeconomics including labor economics, industrial organization, public finance, and health economics. The existing literature on the identification and estimation of these models has recognized a close link between the conditional choice probabilities (hereafter, CCP, which can be observed and estimated from the data) and the payoffs (or\ choice-specific value functions, which are unobservable to the researcher); indeed, most estimation procedures contain an \textquotedblleft inversion\textquotedblright\ step in which the choice-specific value functions are recovered given the estimated choice probabilities. }
{ This paper has two contributions. First, we explicitly characterize this duality relationship between the choice probabilities and choice-specific payoffs. Specifically, in discrete choice models, the social surplus function (McFadden (1978)) provides us with the mapping from payoffs to the probabilities with which a choice is chosen at each state (conditional choice probabilities). Recognizing that the social surplus function is convex, we develop the idea that the convex conjugate of the social surplus function gives us the inverse mapping - from choice probabilities to utility indices. More precisely, the subdifferential of the convex conjugate is a correspondence that maps from the observed choice probabilities to an identified set of payoffs. In short, the choice probabilities and utility indices are related in the sense of conjugate duality. The discovery of this relationship allows us to succinctly characterize the empirical content of discrete choice models, both static and dynamic. }
{ Not only is the convex conjugate of the social surplus function a useful theoretical object; it also provides a new and practical way to \textquotedblleft invert\textquotedblright\ from a given vector of choice probabilities back to the underlying utility indices which generated these probabilities. This is the second contribution of this paper. We show how the conjugate along with its set of subgradients can be efficiently computed by means of linear programming. This linear programming formulation has the structure of an optimal assignment problem (as in Shapley-Shubik's (1971) classic work). This surprising connection enables us to apply insights developed in the optimal transport literature, e.g. Villani (2003, 2009), to discrete choice models. We call this new methodology the \textquotedblleft Mass Transport Approach\textquotedblright\ to CCP\ inversion. }
{ This paper focuses on the estimation of dynamic discrete-choice models via two-step estimation procedures in which conditional choice probabilities are estimated in the initial stage; this estimation approach was pioneered in Hotz and Miller (HM, 1993) and Hotz, Miller, Sanders, Smith (1994).\footnote{{ Subsequent contributions include Aguirregabiria and Mira (2002, 2007), Magnac and Thesmar (2002), Pesendorfer and Schmidt-Dengler (2008), Bajari, et. al. (2009), Arcidiacono and Miller (2011), and Norets and Tang (2013).}} Our use of tools and concepts from convex analysis to study identification and estimation in this dynamic discrete choice setting is novel in the literature. Based on our findings, we propose a new two-step estimator for DDC models. A nice feature of our estimator is that it works for practically any assumed distribution of the utility shocks.\footnote{{ While existing identification results for dynamic discrete choice models allow for quite general specifications of the additive choice-specific utility shocks, many applications of these two-step estimators maintain the restrictive assumption that the utility shocks are distributed i.i.d. type I extreme value, independently of the state variables, leading to choice probabilities which take the multinomial logit form.}} Thus, our estimator would make possible the task of evaluating the robustness of estimation to different distributional assumptions. \footnote{{ While they are not the focus in this paper, many applications of dynamic choice models do not utilize HM-type two step estimation procedures, and they allow for quite flexible distributions of the utility shocks, and also for serial correlation in these shocks (examples include Pakes (1986) and Keane and Wolpin (1997)). This literature typically employs simulated method of moments, or simulated maximum likelihood for estimation (see Rust (1994, section 3.3)).}} }
{ Section 2 contains our main results regarding duality between choice probabilities and payoffs in discrete choice models. Based on these results, we propose, in Section 3, a two-step estimation approach for these models. We also emphasize here the surprising connection between dynamic discrete-choice and optimal matching models. In Section 4 we discuss computational details for our estimator, focusing on the use of linear programming to compute (approximately) the convex conjugate function from the dynamic discrete-choice model. Monte Carlo experiments (in Section 5) show that our estimator performs well in practice, and we apply the estimator to Rust's (1987) bus engine replacement data (Section 6). Section 7 concludes. The Appendix contains proofs and also a brief primer on relevant results from convex analysis. Sections 2.2 and 2.3, as well as Section 4, are not specific to dynamic discrete choice problems but are also true for any (static) discrete choice model. }
{ In this section we review the basic dynamic discrete-choice setup, as encapsulated in Rust's (1987) seminal paper. The state variable is $x\in \mathcal{X}$ which we assume to take only a finite number of values. Agents choose actions $y\in \mathcal{Y}$ from a finite space $\mathcal{Y} =\left\{0,1,\ldots,D\right\}$. The single-period utility flow which an agent derives from choosing $y$ in a given period is
where ${\Greekmath 0122} _{y}$ denotes the utility shock pertaining to action $y$, which differs across agents. Across agents and time periods, the set of utility shocks ${\Greekmath 0122} \equiv \left( {\Greekmath 0122} _{y}\right) _{y\in \mathcal{Y}}$ is distributed according to a joint distribution function $ Q(\cdots ;x)$ which can depend on the current values of the state variable $ x $. We assume that this distribution $Q$ is known to the researcher. }
{ Throughout, we consider a stationary setting in which the agent's decision environment remains unchanged across time periods; thus, for any given period, we use primes ($^{\prime}$) to denote next-period values. Following Rust (1987), and most of the subsequent papers in this literature, we maintain the following conditional independence assumption (which rules out serially persistent forms of unobserved heterogeneity \footnote{{ See Norets (2009), Kasahara and Shimotsu (2009), Arcidiacono and Miller (2011), and Hu and Shum (2012).}}): }
{ The discount rate is ${\Greekmath 010C}$. Agents are dynamic optimizers whose choices each period satisfy\footnote{{ We have used Assumption 1 to eliminate ${\Greekmath 0122}$ as a conditioning variable in the expectation in Eq. ((ref)). }}
where the value function $\bar{V}$ is recursively defined via Bellman's equation as\footnote{ See, eg., Bertsekas (1987, chap. 5) for an introduction and derivation of this equation. }
}
{ $V(x)$, the ex-ante value function, is defined as:\footnote{ There is a difference between the definition of $V(x)$ and the last terms in Equation (1) above. Here, we are considering the expectation of the value function $\bar{V}(x,{\Greekmath 0122})$ taken over the distribution of ${\Greekmath 0122}|x$ (ie. holding the first argument fixed). In the last term of Eq. (1), however, we are considering the expectation over the {\em joint} distribution of $(x',{\Greekmath 0122}')|x$ (ie. holding neither argument fixed). }
}
{ The expectation above is conditional on the current state $x$. In the literature, $V(x)$ is called the ex-ante (or integrated) value function, because it measures the continuation value of the dynamic optimization problem before the agent observes his shocks ${\Greekmath 0122} $, so that the optimal action is still stochastic from the agent's point of view. }
{ Next we define the choice-specific value functions as consisting of two terms: the per-period utility flow and the discounted continuation payoff:
} In this paper, the utility flows $\left\{u_y(x); \forall y\in\mathcal{Y}, \forall x\in\mathcal{X}\right\}$, and subsequently also the choice-specific value functions $\left\{w_y(x), \forall y,x \right\}$, will be treated as unknown parameters; and we will study the identification and estimation of these parameters. For this reason, in the initial part of the paper, we will suppress the explicit dependence of $w_y$ on $x$ for convenience.
{ Given these preliminaries, we derive the duality which is central to this paper. }
{ We start by introducing the expected indirect utility of a decision maker facing the $|\mathbb{\mathcal{Y}}|$-dimensional vector of choice-specific values $w\equiv \left\{w_y, y\in\mathcal{Y}\right\}'$:
where the expectation is assumed to be finite and is taken over the distribution of the utility shocks, $Q(\cdot; x)$. This function $\mathcal{G} (\cdot ;x):\mathbb{R}^{|\mathcal{Y}|}\rightarrow \mathbb{R}$, is called the \textquotedblleft social surplus function\textquotedblright\ in McFadden's (1978) random utility framework, and can be interpreted as the expected welfare of a representative agent in the dynamic discrete-choice problem. }
{ For convenience in what follows, we introduce the notation $ Y(w,{\Greekmath 0122} )$ to denote an agent's optimal choice given the vector of choice-specific value functions $w$ and the vector of utility shocks $ {\Greekmath 0122} $; that is, $Y(w,{\Greekmath 0122} )=\relax\protect\ifmmode\expandafter\text@\else\expandafter\mbox\fi{argmax}_{y\in \mathcal{Y} }(w_{y}+{\Greekmath 0122} _{y})$.\footnote{{ We use $w$ and $ {\Greekmath 0122}$ (and also $p$ below) to denote vectors, while $w_{y}$ and $ {\Greekmath 0122} _{y}$ (and $p_y$) denote the $y$-th component of these vectors.}} This notation makes explicit the randomness in the optimal alternative (arising from the utility shocks ${\Greekmath 0122}$). We get
which shows an alternative expression for the social surplus function as a weighted average, where the weights are the components of the vector of conditional choice probabilities $p(x)$. For the remainder of this section, we suppress the dependence of all quantities on $x$ for convenience. In later sections, we will reintroduce this dependence when it is necessary. }
{ In the case when the social surplus function $\mathcal{G}(w)$ is differentiable (which holds for most discrete-choice model specifications considered in the literature\footnote{{ This includes logit, nested logit, multinomial probit, etc. in which the distribution of the utility shocks is absolutely continuous and $w$ is bounded, cf. Lemma 1 in Shi, Shum and Wong (2014).}}), we obtain a well-known fact that the vector of choice probabilities $p$ compatible with rational choice coincides with the gradient of $\mathcal{G}$ at $w$: }
{ This result, which is analogous to Roy's Identity in discrete choice models, is expounded in McFadden (1978) and Rust (1994; Thm. 3.1)). It characterizes the vector of choice probabilities corresponding to optimal behavior in a discrete choice model as the gradient of the social surplus function. For completeness, we include a proof in the Appendix. The WDZ theorem provides a mapping from the choice-specific value functions (which are unobserved by researchers) to the observed choice probabilities $p$. }
{ However, the identification problem is the reverse problem, namely to determine the set of $w$ which would lead to a given vector of choice probabilities. This problem is exactly solved by convex duality and the introduction of the convex conjugate of $\mathcal{G}$, which we denote as $\mathcal{G}^{\ast }$:\footnote{{ Details of convex conjugates are expounded in the Appendix. Convex conjugates are also encountered in classic producer and consumer theory. For instance, when $f$ is the convex cost function of the firm (decreasing returns to scale in production), then the convex conjugate of the cost function, $f^{*}$, is in fact the firm's optimal profit function.}} }
{ Equation ((ref)) above has the property that if $p$ is not a probability, that is if either conditions $p_{y}\geq 0$ or $ \sum_{y\in \mathcal{Y}}p_{y}=1$ do not hold, then $\mathcal{G}^{\ast }\left( p\right) =+\infty $. Because the choice-specific value functions $w$ and the choice probabilities $p$ are, respectively, the arguments of the functions $ \mathcal{G}$ and its convex conjugate function $\mathcal{G}^{\ast }$, we say that $w$ and $p$ are related in the sense of conjugate duality. The theorem below states an implication of this duality, and provides an \textquotedblleft inverse\textquotedblright\ correspondence from the observed choice probabilities back to the unobserved $w$, which is a necessary step for identification and estimation. }
{ The definition and properties of the subdifferential of a convex function are provided in Appendix A.\footnote{{ $\mathcal{G }$ is differentiable at $w$ if and only if $\partial \mathcal{G}(w)$ is single-valued. In that case, part (i) of Th. (ref) reduces to $ p={\Greekmath 0272} \mathcal{G}(w)$, which is the WDZ theorem. If, in addition, ${\Greekmath 0272} \mathcal{G}$ is one-to-one, then we immediately get $w=\left( {\Greekmath 0272} \mathcal{G}\right) ^{-1}(p)$, or ${\Greekmath 0272} \mathcal{G}^{\ast }(p)=\left( {\Greekmath 0272} \mathcal{G}\right) ^{-1}(p)$, which is the case of the classical Legendre transform. However, as we show below, ${\Greekmath 0272} \mathcal{G}(w)$ is not typically one-to-one in discrete choice models, so that the statement in part (ii) of Th. (ref) is more suitable.}} Part (i) is, of course, connected to the WDZ theorem above; indeed, it is the WDZ theorem when $\mathcal{G}(w)$ is differentiable at $w$. Hence, it encapsulates an optimality requirement that the vector of observed choice probabilities $p$ be derived from optimal discrete-choice decision making for some unknown vector $w$ of choice-specific value functions. }
{ Part (ii) of this proposition, which describes the \textquotedblleft inverse\textquotedblright\ mapping from conditional choice probabilities to choice-specific value functions, does not appear to have been exploited in the literature on dynamic discrete choice. It relates to Galichon and Salani\'{e} (2012) who use convex analysis to estimate matching games with transferable utilities. It specifically states that the vector of choice-specific value functions can be identified from the corresponding vector of observed choice probabilities $p$ as the subgradient of the convex conjugate function $\mathcal{G}^{\ast }(p)$. Eq. ((ref)) is also constructive, and suggests a procedure for computing the choice-specific value functions corresponding to observed choice probabilities. We will fully elaborate this procedure in subsequent sections\footnote{{ Clearly, Theorem (ref) also applies to static random utility discrete-choice models, with the $w(x)$ being interpreted as the utility indices for each of the choices. As such, Eq. ((ref)) relates to results regarding the invertibility of the mapping from utilities to choice probabilities in static discrete choice models (e.g. Berry (1994); Haile, Hortacsu, and Kosenok (2008); Berry, Gandhi, and Haile (2013)). Similar results have also arisen in the literature on stochastic learning in games (Hofbauer and Sandholm (2002); Cominetti, Melo and Sorin (2010)).}}. }
{ Appendix A contains additional derivations related to the subgradient of a convex function. Specifically, it is known (Eq. ((ref))) that $\mathcal{G}(w)+\mathcal{G}^{\ast }(p)=\sum_{y\in \mathcal{Y}}p_{y}w_{y}$ if and only if $p\in \partial \mathcal{G}(w)$. Combining this with Eq. ((ref)), we obtain an alternative expression for the convex conjugate function $\mathcal{G}^{\ast } $:
corresponding to the weighted expectations of the utility shocks $ {\Greekmath 0122} _{y}$ conditional on choosing the option $y$. It is also known that the subdifferential $\partial \mathcal{G}^*(p)$ corresponds to the set of maximizers in the program ((ref)) which define the conjugate function $\mathcal{G}^*(p)$; that is,
Later, we will exploit this variational representation of the subdifferential $\mathcal{G}^*(p)$ for computational purposes; cf. Section 4 below. }
{ It follows from Theorem (ref) that the identification of systematic utilities boils down to the problem of computing the subgradient of a generalized entropy function. However, from examining the social surplus function $\mathcal{G}$, we see that if $w\in \partial \mathcal{G}^{\ast }\left( p\right) $, then it is also true that $ w-K\in \partial \mathcal{G}^{\ast }\left( p\right) $, where $K\in \mathbb{R} ^{|\mathcal{Y}|}$ is a vector taking values of $K$ across all $\mathcal{Y}$ components. Indeed, the choice probabilities are only affected by the differences in the levels offered by the various alternatives. In what follows, we shall tackle this indeterminacy problem by isolating a particular $w^{0}$ among those satisfying $w\in \partial \mathcal{G}^{\ast }\left( p\right) $, where we choose
}
{ We will impose the following assumption on the heterogeneity. }
{ Under this assumption, Theorem (ref) below shows that Eq. ((ref)) defines $w^{0}$ uniquely. Theorem (ref) will then show that the knowledge of $w^{0}$ allows for easy recovery of all vectors $w$ satisfying $p\in \partial \mathcal{G}\left( w\right) $. }
{ The proof of this theorem is in the Appendix. Moreover, even when Assumption (ref) is not satisfied, $w^{0}$ will still be set-identified; Theorem (ref) below describes the identified set of $w^{0}$ corresponding to a given vector of choice probabilities $p$. }
{ Our next result is our main tool for identification; it shows that our choice of $w^{0}(x)$, as defined in Eq. ((ref)) is without loss of generality; it is not an additional model restriction, but merely a convenient way of representing all $w(x)$ in $\partial \mathcal{G} ^{\ast }\left( p\left( x\right) \right) $ with respect to a natural and convenient reference point.\footnote{{ This indeterminacy issue has been resolved in the existing literature on dynamic discrete choice models (eg. Hotz and Miller (1993), Rust (1994), Magnac and Thesmar (2002) by focusing on the differences between choice-specific value functions, which is equivalent to setting $w_{y_{0}}(x) $, the choice-specific value function for a benchmark choice $y_{0}$, equal to zero. Compared to this, our choice of $w^{0}(x)$ satisfying $\mathcal{G} (w^{0}(x))=0$ is more convenient in our context, as it leads to a simple expression for the constant $K$ (see Section (ref)).}} }
{ This theorem shows that any vector within the set $\partial \mathcal{G}^{\ast }\left( p\right) $ can be characterized as the sum of the (uniquely-determined, by Theorem (ref)) vector $w^{0}$ and a constant $K\in \mathbb{R}$. As we will see below, this is our invertibility\ result for dynamic discrete choice problems, as it will imply unique identification of the vector of choice-specific value functions corresponding to any observed vector of conditional choice probabilities. \footnote{{ See Berry (1994), Chiappori and Komunjer (2010), Berry, Gandhi, and Haile (2012), among others, for conditions ensuring the invertibility or \textquotedblleft univalence\textquotedblright\ of demand systems stemming from multinomial choice models, under settings more general than the random utility framework considered here.}} }
{ To summarize the empirical content of the model, we recall the fact that the ex-ante value function $V$ solves the following equation
(derived in Pesendorfer and Schmidt-Dengler (2008), among others), where we write $p(x^{\prime }|x,y)={Pr}(x_{t+1}=x^{\prime }|x_{t}=x,y_{t}=y)$. Noting that the choice-specific value function is just
and, comparing with Eq. ((ref)),
}
{ Hence, by Theorem (ref), the true $w\left( x\right) $ will differ from $w^{0}(x)$ by a constant term $V(x)$:
where $w^{0}\left( x\right) $ is defined in Theorem (ref). This result is also convenient for identification purposes, as it separates identification of $w$ into two subproblems, the determination of $w^{0}$ and the determination of $V$. Once $w^0$ and $V$ are known, the utility flows are determined from Eq. ((ref)). This motivates our two-step estimation procedure, which we describe next. }
{ Based upon the derivations in the previous section, we present a two-step estimation procedure. In the first step, we use the results from Theorem (ref) to recover the vector of choice-specific value functions $w^{0}(x)$ corresponding to each observed vector of choice probabilities $p(x) $. In the second step, we recover the utility flow functions $\bar{u}_{y}(x)$ given the $w^{0}(x)$ obtained from the first step. }
{ In the first step, the goal is to recover the vector of choice-specific value functions $w^{0}(x)\in \partial \mathcal{G}^{\ast }(p(x))$ corresponding to the vector of observed choice probabilities $p(x)$ for each value of $x$. In doing this, we use Theorem 1 above and Proposition 2 below, which show how $w^{0}(x)$ belongs to the subdifferential of the conjugate function $\mathcal{G}^{\ast }(p\left( x\right) )$. We delay discussing these details until Section 4. There, we will show how this problem of obtaining $w^0(x)$ can be reformulated in terms of a class of mathematical programming problems, the Monge-Kantorovich mass transport problems, which leads to convenient computational procedures. Since this is the central component of our estimation procedure, we have named it the mass transport approach (MTA). }
{ From the first step, we obtained $w^{0}(x)$ such that $ w(x)=w^{0}(x)+V(x)$. Now in the second step, we use the recursive structure of the dynamic model, along with fixing one of the utility flows, to jointly pin down the values of ${w}(x)$ and $V(x)$. Finally, once ${w}(x)$ and $V(x)$ are known, the utility flows can be obtained from $\bar{u} _{y}\left( x\right) =w_{y}(x)-{\Greekmath 010C} \mathbb{E}\left[ V(x^{\prime })|x,y \right] $. }
{ In order to nonparametrically identify $\bar{u} _{y}\left(x\right) $, we need to fix some values of the utility flows. Following Bajari, Chernozhukov, Hong, and Nekipelov (2009), we fix the utility flow corresponding to a benchmark choice $y_0$ to be constant at zero:\footnote{{ In a static discrete-choice setting (i.e. $ {\Greekmath 010C}=0$), this assumption would be a normalization, and without loss of generality. In a dynamic discrete-choice setting, however, this entails some loss of generality because different values for the utility flows imply different values for the choice-specific value functions, which leads to differences in the optimal choice behavior. Norets and Tang (2013) discuss this issue in greater detail.}} }
{ With this assumption, we get
}
{ Let $W$ be the column vector whose general term is $\left( w_{y_{0}}^{0}(x)\right) _{x\in \mathcal{X}}$, let $V$ be the column vector whose general term is $\left( V\left( x\right) \right) _{x\in \mathcal{X}}$, and let $\Pi^{0}$ be the $|\mathcal{X}|\times |\mathcal{X}|$ matrix whose general term $\Pi^{0}_{ij}$ is ${Pr}\left( x_{t+1}=j|x_{t}=i,y=y_{0}\right) $ . Equation ((ref)), rewritten in matrix notation, is
and for ${\Greekmath 010C} <1$, matrix $I-{\Greekmath 010C} \Pi^0 $ is a diagonally dominant matrix. Hence, it is invertible and Equation ((ref)) becomes
}
{ The right hand side of this equation is uniquely estimated from the data. After obtaining $V(x)$, $\bar{u}_{y}(x)$ can be nonparametrically identified by
where $w^{0}\left( x\right) $ is as in Theorem (ref), and $V$ is given by ((ref)). }
{ As a sanity check, one recovers $\bar{u}_{y_{0}}(.)=W+V-{\Greekmath 010C} \Pi^{0} V=0$. Also, when ${\Greekmath 010C} \rightarrow 0$, one recovers $\bar{u} _{y}(x)=w_{y}^{0}(x)-w_{y_{0}}^{0}(x)$ which is the case in standard static discrete choice. Moreover, since our approach to identifying the utility flows is nonparametric, our MTA approach does not leverage any known restrictions on the flow utility (including parametric or shape restrictions) in identifying or estimating the flow utilities.}\footnote{To ensure that the inverted $w$ satisfies certain shape restrictions, the linkage between $w$ and the CCP will no longer be stipulated by the subdifferential of the convex conjugate function. It is possible that there exists a modification of the convex conjugate function that is {\em equivalent} to imposing certain shape restrictions on utilities. This is an interesting avenue for future research.}
{ Eqs. ((ref)) and ((ref)) above, showing how the per-period utility flows can be recovered from the choice-specific value functions via a system of linear equations, echoes similar derivations in the existing literature (e.g. Aguirregabiria and Mira (2007), Pesendorfer and Schmidt-Dengler (2008), Arcidiacono and Miller (2011, 2013)). Hence, the innovative aspect of our MTA estimator lies not in the second step, but rather in the first step. In the next section, we delve into computational aspects of this first step. }
{ Existing procedures for estimating DDC models typically rely on a small class of distributions for the utility shocks -- primarily those in the extreme-value family, as in Example 1 above -- because these distributions yield analytical (or near-analytical) formulas for the choice probabilities and $\left\{ \mathbb{E}[{\Greekmath 0122} _{y}|Y(w,{\Greekmath 0122} )=y,x]\right\} _{y}$, the vector of conditional expectation of the utility shocks for the optimal choices, which is required in order to recover the utility flows\footnote{{ Related papers include Hotz and Miller (1993), Hotz, Miller, Sanders, Smith (1994), Aguirregabiria and Mira (2007), Pesendorfer and Schmidt-Dengler (2008), Arcidiacono and Miller (2011). Norets and Tang (2013) propose another estimation approach for binary dynamic choice models in which the choice probability function is not required to be known.}}. Our approach, however, which is based on computing the $\mathcal{G}^{\ast }$ function, easily accommodates different choices for $Q_{{\Greekmath 0122}}$, the (joint) distribution of the utility shocks conditional on $X$. Therefore, our findings expand the set of dynamic discrete-choice models suitable for applied work far beyond those with extreme-value distributed utility shocks.\footnote{{ This remark is also relevant for static discrete choice models. In fact, the random-coefficients multinomial demand model of Berry, Levinsohn, and Pakes (1995) does not have a closed-form expression for the choice probabilities, thus necessitating a simulation-based inversion procedure. In ongoing work (Chiong, Galichon, Shum (2013)), we are exploring the estimation of random-coefficients discrete-choice demand models using our approach.}} }
{ In Section 4.1, we show that the problem of identification in DDC models can be formulated as a mass transport problem, and also how this may be implemented in practice. In showing how to compute $\mathcal{G}^{\ast }$, we exploit the connection, alluded to above, between this function and the assignment game, a model of two-sided matching with transferable utility which has been used to model marriage and housing markets (such as Shapley and Shubik (1971) and Becker (1973)). }
{ Much of our computational strategy will be based on the following proposition, which was derived in Galichon and Salani\'{e} (2012, Proposition 2). It characterizes the $\mathcal{G}^{\ast }$ function as an optimum of a well-studied mathematical program: the \textquotedblleft mass transport,\textquotedblright problem, see Villani (2003). }
{ In Eq. ((ref)) above, the minimum is taken across all joint distributions of $(Y,{\Greekmath 0122} )$ with marginal distribution equal to, respectively, $p$ and $Q$. It follows from the proposition that the main problem of identification of the choice-specific value functions $w$ can be recast as a mass transport problem (Villani (2003)), in which the set of optimizers to Eq. ((ref)) yield vectors of choice-specific value functions $w\in \partial \mathcal{G}^{\ast }\left( p\right) $. }
{ Moreover, the mass transport problem can be interpreted as an optimal matching problem. Using a marriage market analogy, consider a setting in which a matched couple consisting of a \textquotedblleft man\textquotedblright\ (with characteristics $y\sim p$) and a \textquotedblleft woman\textquotedblright\ (with characteristics $ {\Greekmath 0122} \sim {Q}$) obtain a joint marital surplus $-c(y,{\Greekmath 0122} )={\Greekmath 0122} _{y}$. Accordingly, Eq. ((ref)) is an optimal matching problem in which the joint distribution of characteristics $(y,{\Greekmath 0122} )$ of matched couples is chosen to maximize the aggregate marital surplus. }
{ In the case when $Q$ is a discrete distribution, the mass transport problem in the above proposition reduces to a linear-programming problem which coincides with the assignment game of Shapley and Shubik (1971). This connection suggests a convenient way for efficiently computing the $\mathcal{G}^{\ast }$ function (along with its subgradient). Specifically, we will show how the dual problem (Eq. ((ref))) takes the form of a linear programming problem or assignment game, for which some of the associated Lagrange multipliers correspond to the the subgradient $ \partial \mathcal{G}^{\ast }$, and hence the choice-specific value functions. These computational details are the focus of Section (ref) below. We include the proof of Proposition (ref) in the Appendix for completeness. }
{ Let $\hat{Q}$ be a discrete approximation to the distribution $ Q $. Specifically, consider a $S$-point approximation to $Q$, where the support is $\relax\protect\ifmmode\expandafter\text@\else\expandafter\mbox\fi{Supp}(\hat{Q})=\{{\Greekmath 0122} ^{1},\dots ,{\Greekmath 0122} ^{S}\} $. Let ${Pr}(\hat{Q}={\Greekmath 0122} ^{s})=q_{s}$. The best $S$-point approximation is such that the support points are equally weighted, $q_{s}= \frac{1}{S}$, i.e. the best $\hat{Q}$ is a uniform distribution, see Kennan (2006). Therefore, let $\hat{Q}$ be a uniform distribution whose support can be constructed by drawing $S$ points from the distribution $Q$. Moreover, $\hat{Q}$ converges to $Q$ uniformly as $S\rightarrow \infty $,\footnote{{ Because $\hat{Q}$ is constructed from i.i.d. draws from $Q$, this uniform convergence follows from the Glivenko-Cantelli Theorem. }} so that the approximation error from this discretization will vanish when $S$ is large. Under these assumptions, Problem ((ref))-((ref)) has a Linear Programming formulation as
}
{ For this discretized problem, the set of $w\in \partial \mathcal{G}^{\ast }\left( p\right) $ is the set of vectors $w$ of Lagrange multipliers corresponding to constraints ((ref)). To see how we recover $w^{0}$, the specific element in $\partial \mathcal{G}^{\ast }\left( p\right) $ as defined in Theorem 1, we begin with the dual problem
Consider $\left( {\Greekmath 0115} ,z\right) $ a solution to ((ref)). By duality, ${\Greekmath 0115} $ and $z$ are, respectively, vectors of Lagrange multipliers associated to constraints ((ref)) and ((ref)). \footnote{{ Because the two linear programs ((ref)) and ((ref)) are dual to each other, the Lagrange multipliers of interest ${\Greekmath 0115} _{y}$ can be obtained by computing either program. In practice, for the simulations and empirical application below, we computed the primal problem ((ref)).}} We have $\mathcal{G}^{\ast }\left( p\right) =\sum_{y\in \mathcal{Y}}p_{y}{\Greekmath 0115} _{y}+\sum_{s=1}^{S}q_{s}z_{s}$ , which implies\footnote{{ This uses Eq. ((ref)) in Appendix A, which (in our setup) states that $\mathcal{G}^{*}(p)+\mathcal{G} ({\Greekmath 0115} )=p\cdot {\Greekmath 0115} $, for all Lagrange multiplier vectors ${\Greekmath 0115} \in \partial \mathcal{G}^{*}(p)$.}} that $\mathcal{G}\left( {\Greekmath 0115} \right) =-\sum_{s=1}^{S}q_{s}z_{s}$. Also, for any two elements ${\Greekmath 0115} ,w^{0}\in \partial \mathcal{G}^{\ast }(p)$, we have $\sum_{y\in \mathcal{Y} }p_{y}{\Greekmath 0115} _{y}-\mathcal{G}({\Greekmath 0115} )=\sum_{y\in \mathcal{Y} }p_{y}w_{y}^{0}-\mathcal{G}(w^{0})$. }
{ Hence, because $\mathcal{G}(w^{0})=0$, we get
}
{ In Theorem 5 below, we establish the consistency of this estimate of $w^0$. }
{ Thus far, we have proposed a procedure for computing $\mathcal{G }^{\ast }$ (and the choice-specific value functions $w^{0}$) by discretizing the otherwise continuous distribution $Q$. However, because the support of $ {\Greekmath 0122} $ is discrete, $w_{y}^{0}$ will generally not be unique. \footnote{{ Note that Theorem 1 requires ${\Greekmath 0122} $ to have full support.}} This is due to the non-uniqueness of the solution to the dual of the LP problem in Eq. ((ref)), and corresponds to Shapley and Shubik's (1971) well-known results on the multiplicity of the core in the finite assignment game. Applied to discrete-choice models, it implies that when the support of the utility shocks is finite, the utilities from the discrete-choice model will only be partially identified. In this section, we discuss this partial identification, or indeterminacy, problem further. }
{ Recall that
where $c\left( y,{\Greekmath 0122} \right) =-{\Greekmath 0122} _{y}$. In Proposition (ref), this problem was shown to be the dual formulation of an optimal assignment problem. }
{ We call identified set of payoff vectors, denoted by $ \mathcal{I}\left( p\right) $, the set of vectors $w$ such that
and we denote by $\mathcal{I}_{0}\left( p\right) $ the normalized identified set of payoff vectors, that is the set of $w\in \mathcal{I} \left( p\right) $ such that $\mathcal{G}\left( w\right) =0$. If $Q$ were to have full support, $\mathcal{I}_{0}\left( p\right) $ would contain only the singleton $\left\{ w^{0}\right\} $ as in Theorem (ref). Instead, when the distribution $Q$ is discrete, the set $\mathcal{I} _{0}\left( p\right) $ contains a multiplicity of vectors $w$ which satisfy ( (ref)). One has: }
{ This result allows us to easily derive bounds on the individual components of $w^0$ using the characterization of the identified set using linear inequalities. Indeed, for each $y\in \mathcal{Y}$, we can obtain upper (resp. lower) bounds on $w_{y}$ by maximizing (resp. minimizing) $w_{y}$ subject to the linear inequalities characterizing $\mathcal{I}_{0}(p)$,\footnote{However, letting $\bar{w}_y$ (resp. $\underline{w}_y$) denote the upper (resp. lower) bound on $w_y$, we note that typically the vector $( w_y, y\in\mathcal{Y})'\not\in \mathcal{I}_{0}(p)$. } which is a linear programming problem.\footnote{{ Moreover, partial identification in $w^0$ (due to discretization of the shock distribution $Q({\Greekmath 0122})$ will naturally also imply partial identification in the utility flows $u^0$. For a given identified vector $w^0$ (and also given the choice probabilities $p$ and transition matrix $\Pi^0$ from the data), we can recover the corresponding $u^0$ using Eqs. ((ref))-((ref)). }} }
{ Furthermore, when the dimensionality of discretization, $S$, is high, the core shrinks to a singleton, and the core collapses to $ \left\{ w^{0}\right\}$. This is a consequence of our next theorem, which is a consistency result.\footnote{{Gretsky, Ostroy, and Zame (1999) also discusses this phenomenon in their paper.}} In our Monte Carlo experiments below, we provide evidence for the magnitude of this indeterminacy problem under different levels of discretization. }
{ Here we show (strong) consistency for our MTA estimator of $ w^{0}$, the normalized choice-specific value functions. In our proof, we accommodate two types of error: (i) approximation error from discretizing the distribution $Q$ of ${\Greekmath 0122} $, and (ii) sampling error from our finite-sample observations of the choice probabilities. We use $Q^{n}$ to denote the discretized distributions of ${\Greekmath 0122}$, and $p^n$ to denote the sample estimates of the choice probabilities. The limiting vector of choice probabilities is denoted $p^0$. For a given $(Q^n, p^n)$, let $ w_{y}^{n}$ denote the choice-specific value functions estimated using our MTA approach. }
{ The proof, which is in the appendix, may be of independent interest as the main argument relies on approximation results from mass transport theory, which we believe to be the first use of such results for proving consistency in an econometrics context. }
{ In this section, we illustrate our estimation framework using a dynamic model of resource extraction. To illustrate how our method can tractably handle any general distribution of the unobservables, we use a distribution in which shocks to different choices are correlated. We will begin by describing the setup. }
{ At each time $t$, let $x_{t} \in \{1,2,\dots,30\}$ be the state variable denoting the size of the resource pool. There are three choices, }
{ The joint distribution of the unobserved state variables is given by $({\Greekmath 0122} _{0}-{\Greekmath 0122} _{2},{\Greekmath 0122} _{1}-{\Greekmath 0122} _{2})\sim N\left(
,
\right) $. Other parameters we fix and hold constant for the Monte Carlo study are the discount rate, ${\Greekmath 010C} =0.9$ and ${\Greekmath 0119} =(0.3,0.35,0.25,0.10)$. }
{ As a preliminary check of our estimation procedure, we show that we are able to recover the utility flows using the actual conditional choice probabilities implied by the underlying model. We discretized the distribution of ${\Greekmath 0122}$ using $S=5000$ support points. As is clear from Figure (ref), the estimated utility flows (plotted as dots) as a function of states matched the actual utility functions very well. }
{
}
{ To test the performance of our estimation procedure when there is sampling error in the CCPs, we generate simulated panel data of the following form: $\{y_{it}\;, x_{it} :i =1,2,\dots, N; \;t=1,2,\dots, T\}$ where $y_{it} \in \{0,1,2\}$ is the dynamically optimal choice at $x_{it}$ after the realization of simulated shocks. We vary the number of cross-section observations $N$ and the number periods $T$, and for each combination of $(N,T)$, we generate 100 independent datasets.\footnote{ { In each dataset, we initialized $x_{i1}$ with a random state in $\mathcal{X}$. When calculating RMSE and $R^{2}$, we restrict to states where the probability is in the interior of the simplex $\Delta^3$, otherwise utilities are not identified and the estimates are meaningless.}} }
{ For each replication or simulated dataset, the root-mean-square error (RMSE) and $R^{2}$ are calculated, showing how well the estimated $ \bar{u}_{y}(x)$ fits the true utility function for each $y$. The averages are reported in Table (ref). }
{
}
As mentioned in Section (ref), using a discrete approximation to the distribution of the unobserved state variable introduces a partial identification problem: the identified choice-specific value functions might not be unique. Using simulations, we next show that the identified set of choice-specific value functions (which we will simply refer to as \textquotedblleft payoffs\textquotedblright ) shrinks to a singleton as $S$ increases, where $ S $ is the number of support points in the discrete approximation of the continuous error distribution. For $S$ ranging from 100 to 1000, we plot in Figure (ref), the differences between the largest and smallest choice-specific value function for $y=2$ across all values of $p\in \Delta ^{3}$ (using the linear programming procedures described in Section (ref)).
{
}
As is evident, even at small $S$, the identified payoffs are very close to each other in magnitude. At $S=1000$, where computation is near-instantaneous, for most of the values in the discretised grid of $ \Delta^{3}$, the core is a singleton; when it is not, the difference in the estimated payoff is less than 0.01. Similar results hold for the choice-specific value functions for choices $y=0$ and $y=1$, which are plotted in Figures (ref) and (ref) in the Appendix. To sum up, it appears that this indeterminacy issue in the payoffs is not a worrisome problem for even very modest values of $S$.
{ One common technique used in the literature to estimate dynamic discrete choice models with non-standard distribution of unobservables is the Simulated Maximum Likelihood (SML). Our MTA method has a distinct advantage over SML -- while MTA allows the utility flows $\bar{u}_{y}(x)$ for different choices $y$ and states $x$ to be nonparametric, the SML approach typically requires parameterizing these utility flows as a function of a low-dimensional parameter vector. This makes comparison of these two approaches awkward. Nevertheless, here we undertake a comparison of the nonparametric MTA vs. the parametric SML approach. First we compare the performance of the two alternative approaches in terms of computational time. The computations were performed on a Quad Core Intel Xeon 2.93GHz UNIX workstation, and the results are presented in Table (ref). }
From a computational point of view, the disadvantage of SML is that the dynamic programming problem must be solved (via Bellman function iteration) for each trial parameter vector, whereas the MTA requires solving a large-scale linear programming problem -- but only once. Table (ref) shows that our MTA procedure significantly outperforms SML in terms of computational speed. This finding, along with the results in Table (ref), show that MTA has the desirable properties of speed and accuracy, and also allows for nonparametric specification of the utility flows $\bar{u}_{y}(x)$.
{
}
Furthermore, as confirmed in our computations, the nonlinear optimization routines typically used to implement SML have trouble finding the global optimum; in contrast, the MTA estimator, by virtue of its being a linear programming problem, always finds the global optimum. Indeed, under the logistic assumption on unobservables and linear-in-parameters utility, one advantage of the Hotz-Miller estimator for DDC models (vs. SML) is that the system of equations defining the estimator has a unique global solution; in their discussion of this, Aguirregabiria and Mira (2010, pg. 48) remark that “extending the range of applicability of ... CCP methods to models which do not impose the CLOGIT [logistic] assumption is a topic for further research." This paper fills the gap: our MTA estimator shares the computational advantages of the CLOGIT setup, but works for non-logistic models. In this sense, the MTA estimator is a generalized CCP estimator.
{ In this section, we apply our estimation procedure to the bus engine replacement dataset first analyzed in Rust (1987). In each week $t$, Harold Zurcher (bus depot manager), chooses $y_{t} \in \{0,1\}$ after observing the mileage $x_{t} \in \mathcal{X}$ and the realized shocks $ {\Greekmath 0122}_{t}$. If $y_{t}=0$, then he chooses not to replace the bus engine, and $y_{t}=1$ means that he chooses to replace the bus engine. The states space is $\mathcal{X}=\{0,1,\dots 29\}$, that is, we divided the mileage space into 30 states, each representing a 12,500 increment in mileage since the last engine replacement.\footnote{{ This grid is coarser compared to Rust's (1987) original analysis of this data, in which he divided the mileage space into increments of 5,000 miles. However, because replacement of engines occurred so infrequently (there were only 61 replacement in the entire ten-year sample period), using such a fine grid size leads to many states that have zero probability of choosing replacement. Our procedure -- like all other CCP-based approaches -- fails when the vector of conditional choice probability lies on the boundary of the simplex.}} Harold Zurcher manages a fleet of 104 identical buses, and we observe the decisions that he made, as well as the corresponding bus mileage at each time period $t$. The duration between $t+1 $ and $t$ is a quarter of a year, and the dataset spans 10 years. Figures (ref) and (ref) in the Appendix summarize the frequencies and mileage at which replacements take place in the dataset. }
{ Firstly, we can directly estimate the probability of choosing to replace and not to replace the engine for each state in $\mathcal{X}$. Also directly obtained from the data is the Markov transition probabilities for the observed state variable $x_{t} \in X$, estimated as: }
{
}
{
}
{
}
{ For this analysis, we assumed a normal mixture distribution of the error term, specifically, ${\Greekmath 0122}_{t0} - {\Greekmath 0122}_{t1} \sim \frac{1}{2}N(0,1)+\frac{1}{2}N(0,\frac{1}{1+0.1x})$.\footnote{{ In this paper, we restrict attention to the case where the researcher fully knows the distribution of the unobservables $Q_{\vec{{\Greekmath 0122}}}$, so that there are no unknown parameters in these distributions. In principle, the two-step procedure proposed here can be nested inside an additional “outer loop” in which unknown parameters of $Q_{\vec{{\Greekmath 0122}}}$ are considered, but identification and estimation in this case must rely on additional model restrictions in addition to those considered in this paper. We are currently exploring such a model in the context of the simpler static discrete choice setting (Chiong, Galichon and Shum (2014, work in progress)). }} We chose this mixture distribution in order to allow the utility shocks to depend on mileage -- which accommodates, for instance, operating costs which may be more volatile and unpredictable at different levels of mileage. At the same time, these specifications for the utility shock distribution showcase the flexibility of our procedure in estimating dynamic discrete choice models for any general error distribution. For comparison, we repeat this exercise using an error distribution that is homoskedastic, i.e., its variance does not depend on the state variable $x_{t}$. The result appears to be robust to using different distributions of ${\Greekmath 0122}_{t0} - {\Greekmath 0122}_{t1}$. We set the discount rate ${\Greekmath 010C}=0.9$. }
{ To non-parametrically estimate $\bar{u}_{y=0} (x)$, we fixed $ \bar{u}_{y=1}(x)$ to 0 for all $x \in X$. Hence, our estimates of $\bar{u} _{y=0}(x)$ should be interpreted as the magnitude of operating costs \footnote{{ Operating costs include maintenance, fuel, insurance costs, plus Zurcher's estimate of the costs of lost ridership and goodwill due to unexpected breakdowns.}} relative to replacement costs\footnote{ { To be pedantic, this also includes the operating cost at $x=0$.} }, with positive values implying that replacement costs exceed operating costs. The estimated utility flows from choosing $y=0$ (don't replace) relative to $y=1$ (replace engine) are plotted in Figure (ref). We only present estimates for mileage within the range $x\in[9,25]$, because within this range, the CCPs are in the interior of the probability simplex (cf. footnote (ref) and Figure (ref) in appendix). }
{ Within this range, the estimated utility function does not vary much with increasing mileages, i.e. it has slope that is not significantly different from zero. The recovered utilities fall within the narrow band of 9 and 9.5, which implies that on average the replacement cost is much higher than the maintenance cost, by a magnitude of 18 to 19 times the variance of the utility shocks. It is somewhat surprising that our results suggest that when the mileage goes beyond the cutoff point of 100,000 miles, Harold Zurcher perceived the operating costs to be inelastic with respect to accumulated mileage. It is worth noting that Rust (1987) mentioned: “According to Zurcher, monthly maintenance costs increase very slowly as a function of accumulated mileage." }
{
}
{ To get an idea for the effect of sampling error on our estimates, we bootstrapped our estimation procedure. For each of 100 resamples, we randomly drew 80 buses with replacement from the dataset, and re-estimated the utility flows $\bar{u}_{y=0}(x)$ using our procedure. The results are plotted in Figure (ref). The evidence suggests that we are able to obtain fairly tight cost estimates for states where there is at least one replacement, i.e. for $x\geq9$ ($x \geq 112,500$ miles), and for states that are reached often enough; i.e. for $x\leq 22$ ($x \leq 275,000$ miles). }
{ In this paper, we have shown how results from convex analysis can be fruitfully applied to study identification in dynamic discrete choice models; modulo the use of these tools, a large class of dynamic discrete choice problems with quite general utility shocks becomes no more difficult to compute and estimate than the Logit model encountered in most empirical applications. This has allowed us to provide a natural and holistic framework encompassing the papers of Rust (1987), Hotz and Miller (1993), and Magnac and Thesmar (2002). While the identification results in this paper are comparable to other results in the literature, the approach we take, based on the convexity of the social surplus function $\mathcal{G}$ and the resulting duality between choice probabilities and choice-specific value functions, appears new. Far more than providing a mere reformulation, this approach is powerful, and has significant implications in several dimensions. }
{ First, by drawing the (surprising) connection between the computation of the $\mathcal{G}^{\ast }$ function and the computation of optimal matchings in the classical assignment game, we can apply the powerful tools developed to compute optimal matchings to dynamic discrete-choice models.\footnote{{ While the present paper has used standard Linear Programming algorithms such as the Simplex algorithm, other, more powerful matching algorithms such as the Hungarian algorithm may be efficiently put to use when the dimensionality of the problem grows.}} Moreover, by reformulating the problem as an optimal matching problem, all existence and uniqueness results are inherited from the theory of optimal transport. For instance, the uniqueness of a systematic utility rationalizing the consumer's choices follows from the uniqueness of a potential in the Monge-Kantorovich theorem. }
{ We believe the present paper opens a more flexible way to deal with discrete choice models. While identification is exact for a fixed structure of the unobserved heterogeneity, one may wish to parameterize the distribution of the utility shocks and do inference on that parameter. The results and methods developed in this paper may also extend to dynamic discrete games, with the utility shocks reinterpreted as players' private information.\footnote{{ See, e.g. Aguirregabiria and Mira (2007) or Pesendorfer and Schmidt-Dengler (2008)).}} However, we leave these directions for future exploration. }
{