📖 Conditional choice probabilities, identification and two-step estimator

NFXP solves the model inside every likelihood evaluation. This class turns the argument around: the conditional choice probabilities (CCPs) observed in the data pin down the value function differences, so the model can be estimated without ever solving it. The same result of Hotz & Miller (1993) also says exactly what the data can and cannot identify.

cd sb-dse-code
git reset --hard HEAD
git pull

git pull upstream main                 # collect the task
cp -r tasks/eta_ccp solutions/eta_ccp  # work on the copy

Integrated $\ne$ expected value function¶

Maintain the setup of the Zurcher engine replacement model of Rust (1987) from Class 9, leaning to more generality. The Bellman equation of the Zurcher problem is

and it breaks into three pieces that are useful on their own: the choice-specific value, the expected value, and the value function itself,

The last equation uses the EV1 assumption on the distribution of $\varepsilon$, but in more generality it can be written as

Let’s repeat the terminology:

• $v(x,d)$ is the choice-specific value function, or conditional value function, and

• $EV(x,d)$ is commonly referred to as the expected value function and sometimes as the ex-post value function

Here is a new object and yet another representation. The integrated value function $V^\sigma(x)$, also known as the ex-ante value function, is the value function with the taste shock integrated out,

The subscript $\sigma$ follows the notation of Aguirregabiria & Mira (2007), who define it as the value function under a strategy profile $\sigma$.

We could write the Bellman equation in the space of integrated value functions $V^\sigma(x)$ by cutting the circle of Bellman at a different point:

The new representation of the Bellman equation is

This is the expectation of the maximum utility in a RUM with alternative utilities given by $v(x,d') + \varepsilon_{d'}$, which McFadden (1974) called the social surplus function in Class 6.

In the EV1 case max-stability gives it in closed form, with $\gamma \approx 0.5772$ the Euler–Mascheroni constant,

Choice probabilities¶

Recall that by the Williams–Daly–Zachary theorem in the general case the choice probabilities are the derivatives of the social surplus function,

and under the EV1 assumption the derivative of the logsum is the multinomial logit,

Exchanging the order of differentiation and integration in the general case, we can also express the choice probabilities as the integral with respect to the distribution $q(\varepsilon|x)$ of the indicator that $d$ is the maximizer

Inversion theorem¶

Let $d_0$ denote the reference alternative, so that the values of other alternatives will be measured relative to it.

For each $x$ consider the vector of value differences $\Delta v(x) \in \mathbb{R}^{K-1}$, where $K=|D(x)|$ is the number of alternatives, with elements

Rewriting the event $\left\{ d = \arg\max_{d' \in D(x)} \{v(x,d')+\varepsilon_{d'}\} \right\}$ from above step by step, we have

The steps are:

• write the argmax as a system of inequalities,

• subtract $v(x,d_0)$ from both sides of each inequality so that only differences appear, and

• read the result as the probability mass of a region of $\Omega$ that depends on $\Delta v(x)$ only

Compare this derivation to the static multinomial logit model of Class 6.

In other words, if

is a mapping from $K-1$ value differences to the $K$ vector of probabilities, then the choice probabilities are given by $P(x) = Q(\Delta v(x),x)$.

The theorem is the reason the reference alternative was needed: $K$ probabilities that sum to one carry $K-1$ degrees of freedom, and so do the $K-1$ differences. Levels of the choice-specific values are not recoverable from choices, only their differences.

What we have: the Hotz–Miller inversion gives a mapping from the choice probabilities to the value differences for any choice model with random terms $\varepsilon$ satisfying the regularity conditions of the theorem, and in the EV1 and GEV cases we have closed-form expressions for the inverse map.

Relationship between $V^\sigma(x)$, $v(x,d)$ and choice probabilities¶

Recall that the choice probability $P(d|x)$ in the general case is simply the expectation of the indicator that a particular choice $d$ yields the maximum utility,

The expression for $V^\sigma(x)$ as the expected maximum can then be expanded using the law of iterated expectations, conditioning on which alternative is chosen:

Conditional on $d$ being the maximizer, the maximum is $v(x,d)+\varepsilon_d$, and $v(x,d)$ is not random, which is all that happens between the second and the last line. The term that remains,

has the special name of correction term, see Aguirregabiria & Mira (2002). It is the expectation of the random component conditional on the event that the alternative it is associated with has the highest value. We end up with

We can make one more step, using the Hotz–Miller inversion with a reference alternative $d_0$, to arrive at

where $\psi(x,d_0)$ is a function of the choice probabilities and not of the value functions, see Lemma 1 in Arcidiacono & Miller (2011). This result holds can be written for any reference alternative $d_0$, and therefore holds for every $d$.

In other words, the difference between the integrated value function and any choice-specific reference value is a function of the choice probabilities only. This is the result that every CCP-based method builds on.

Correction terms for EV1 and GEV¶

Hotz & Miller (1993) and Arcidiacono & Miller (2011) show that the correction term has a closed form in the two workhorse cases,

where $N(d)$ is the set of alternatives in the same nest as $d$ and $\sigma\leqslant 1$ is the scale parameter within the nest.

Finite dependence¶

Hotz-Miller inversion establishes the relationship between the choice probabilities and the value differences, but values are still defined recursively.

Main idea of finite dependence is to note that it may be possible to cancel out the future after several periods

• recursion reduces to several periods (one repeated cycle)

• then no fixed point to solve for

• estimator can be applied to short panels

The idea goes back to Altuğ & Miller (1998), and we follow the general version in Section 3 of Arcidiacono & Miller (2011).

The starting point is the expression derived above

Substituting it into the definition of the choice-specific value gives

where $k \in D(x')$ is just some alternative chosen in the next period.

• It does not have to be the same in every $x'$.

• It does not even have to be a single alternative either, and can be represented by some choice weights $\{\omega_k\}$, such that $\sum_{k\in D(x')} \omega_k = 1$:

Let’s now repeat this step again in the next period, and so on. This is referred to as telescoping the integrated value function.

1. Fix the current period $t$, the state $x_t = x$ and the initial choice $d$.

2. A choice sequence assigns to every later period $\tau > t$ and every state $x_\tau$ a vector of decision weights $\omega_\tau(k|x_\tau,d) \geqslant 0$ with $\sum_{k \in D(x_\tau)} \omega_\tau(k|x_\tau,d) = 1$.

• The weights may depend on the state reached and may mix over alternatives

• Arcidiacono & Miller (2011) write them as $d^*_{k\tau}(z_\tau,j)$

Along the sequence, the state evolves according to the distribution

$\kappa_\tau(\cdot|x,d)$ of $x_{\tau+1}$, defined recursively by

In other words, we look at the distribution of states resulting from the chosen sequence of choice weights

or in the simple case of a deterministic sequence of choices $d_\tau$

In both cases the induced distribution of states is

Now we can compute the choice specific value along some choice sequence!

Theorem 1 of Arcidiacono & Miller (2011) shows that, for any state $x$, any initial choice $d$ and any choice sequence,

The term $\psi(x_\tau,k) = V^\sigma(x_\tau) - v(x_\tau,k)$ compensates at each step for the sequence not being the optimal policy.

Why is this useful?

From period $t+\rho+1$ on, set the weights of the two sequences equal.

Every term of Theorem 1 after $t+\rho$ is then identical for $d$ and $d'$ and cancels in the difference, leaving

Helpful properties of finite dependence:

• the $\psi$ mappings, the first-stage CCPs and the transition probabilities, the value difference is a linear function of flow utilities over $\rho+1$ periods.

• only the $\psi$ functions of alternatives that carry positive weight in one of the two sequences are needed

The Zurcher model is the leading case: engine replacement is a renewal action, so the model has one-period finite dependence. The practical of Class 13 derives the resulting value difference and codes the estimator built on it.

Finite dependence can take more than one period and require sequences that react to the state. In the stylized labor-supply example of Section 3.2.2 of Arcidiacono & Miller (2011), working today raises human capital $z$ by 1 or 2 units with equal probability. Working in any later period raises it by exactly 1, and staying home leaves it unchanged. Starting with home, the sequence work, work reaches $z+2$ at $t+3$ for sure. Starting with work, stay home at $t+1$ if the gain was 2 and work if it was 1, then stay home at $t+2$: again $z+2$ at $t+3$. The pair has two-period finite dependence, and the second sequence is state-contingent.

What if no finite dependence?¶

Finite dependence is a property of the transition probabilities, and nothing guarantees it. If no later choice can undo or replicate the effect of today’s choice on the state, the terms never cancel. Then the infinite sum, or the matrix inversion of the identification section, is back.

Finding the sequences by hand is application-specific; Arcidiacono & Miller (2019) search for the decision weights numerically.

See also the JMP by Jaepil Lee (2025) for an application of numerically searching for finite dependence sequences in estimation.

The CCPs that enter are those at the states reachable within $\rho$ periods, including rarely visited ones, where $\log \hat P$ is noisy. The pay-off is largest in nonstationary models with short panels. There, the CCPs in the last observed period carry all the information about the unobserved future, and flow utilities are estimable up to $\rho$ periods before the sample ends without modeling the horizon.

Identification¶

The previous results have immediate implications for identification of the model primitives of dynamic discrete choice models in general.

• The model is characterized by the primitives $\{u, \pi, q, \beta\}$ (and the horizon, infinite here)

• The data are a panel of states and choices $(x,d)$

The question is: which primitives the data pin down??

Assumption: the discount factor $\beta$ and the distribution of the taste shocks $q$ are taken as known

Further, consistent estimate of the transition probabilities $\pi$ are available (see below).

So, main focus is non-parametric identification of flow utilities $u$!

Assume a discrete state space, so that the integral over $\pi(x'|x,d)$ is a sum and can be represented by a matrix multiplication. As before, $\Pi(d)$ the transition probability matrix for the state space $X$ under action $d$.

First, we can consistently estimate the choice probabilities $P(d|x)$, the CCPs, and the transition probabilities $\Pi(d)$ from the data on $(x,d)$ in the first stage, giving common name CCP or two-stage estimators to the whole family of CCP-based estimation methods.

Now fix the reference alternative $d_0$ and let its flow utility $u(x,d_0)$ be given for every $x$. Stack all entities into vectors over the state space $X$.

The definition of the choice-specific value and the relationship $V^\sigma - v(d_0) = \psi(d_0)$ give

This is the integrated value function in terms of first-stage objects and the flow utility of the reference alternative $u(d_0)$.

To recover the utility of the other actions, follow the same route from $v(d) = u(d) + \beta \Pi(d) V^\sigma$ and $V^\sigma - v(d) = \psi(d)$:

and substituting $V^\sigma$,

The same result can be written without matrix inversion, as a discounted sum along a choice sequence, using Theorem 1 above:

• take the sequence that chooses $d_0$ in every period after $t$, $\omega_\tau(d_0|x_\tau,\cdot) = 1$ for $\tau > t$

• let $\kappa_\tau(\cdot|x,d)$ be the distributions of the state it generates after the initial choice $d$

How does this relate to what we already have?

• It is the matrix formula above written out term by term

• It is Theorem 1 of the finite dependence section applied to $d$ and $d_0$ with the same continuation, and differenced

Why is this useful?

When the two sequences reach the same distribution of the state after $\rho$ periods, the sum stops at $t+\rho$.

• $u$ is then identified from CCPs at most $\rho$ periods ahead

• this is what makes identification off short panels possible in nonstationary models

The converse matters as much. Arcidiacono & Miller (2020) also show that any bounded choice of $u(x,d_0)$, state by state, together with the $u(x,d)$ implied by the formula above, generates exactly the same CCPs and transitions as the true model: the two are observationally equivalent.

In the matrix form, replacing $u(d_0)$ by an arbitrary vector $c$ changes the other utilities to

without changing anything in the data. Therefore:

• flow utilities are identified only relative to one alternative per state

• the normalization does not have to set it to zero, nor use the same alternative in every state

• a normalization is needed unless some data inform the level of utility, for example data on costs or prices

• or unless the parameterization of $u$ restricts how utilities vary across states and alternatives tightly enough to rule out the transformation above

A parametric form alone is not enough: if it is flexible enough to absorb $u^*(d) - u(d)$, the normalization is still implicit in it.

CCP-based estimation¶

There are many estimation approaches based on the CCP representation of the dynamic discrete choice models:

• Minimum distance Altuğ & Miller, 1998

• Simulated moments Hotz et al., 1994

• Asymptotic least squares Pesendorfer & Schmidt-Dengler, 2008

• Quasi-maximum likelihood Hotz & Miller, 1993

• Pseudo-maximum likelihood Aguirregabiria & Mira, 2002

• Nested pseudo-likelihood Aguirregabiria & Mira, 2007

• Many-many more

All of them share the same two-step structure, which is why they are collectively called two-step CCP estimators:

Input: panel data (x_it, d_it)
Algorithm:
  1. Estimate the CCPs P(d|x) and transition probabilities Π(d) directly from the data
     - non-parametrically, like frequency counts
     - parametrically, like multinomial logit or nested logit for P(d|x)
       and a discrete choice model for Π(d)
     - semi-parametrically, like flexible or local logit
  2. Use the estimated CCPs and transition probabilities to construct
     a criterion function that depends on the structural parameters θ
  3. Optimize the criterion function to obtain the estimates of θ
     by one of the approaches above
Output: estimate of θ, obtained without solving the model

The second step is where the methods differ: the value function differences $\Delta v(x)$ implied by $\theta$ and the first-stage estimates are matched to the first-stage CCPs by a distance, a set of moments, or a likelihood. In the Zurcher model with the logit inverse map, step 1 estimates the replacement probability in every mileage bin, a frequency table in principle and a smoothed one in practice, and step 2 is a static logit estimation with the future differenced out by finite dependence. This is what we code in the practical of Class 13, and the pseudo-likelihood versions of step 2 are the subject of Class 14.

Issues with CCP-based estimation¶

The first-stage estimates enter the criterion function directly, so their sampling error is inherited by $\hat\theta$.

With many states and a modest panel, frequency estimates of $P(d|x)$ are noisy or exactly zero in rarely visited states, and $\log P$ in the inverse map amplifies the noise.

Two-step estimators are therefore less efficient than NFXP in finite samples, and in the tails of the state space they can be badly biased.

Smoothing the first stage helps, at the price of a choice of smoother that the theory does not make for you.

Further topics¶

The CCP estimation approach gave rise to a number of further avenues of methodological research and applied work:

• Unobserved heterogeneity among decision-makers, Arcidiacono & Miller (2011), who developed the theory of representation with correction terms and an expectation-maximization algorithm to estimate finite mixtures of types

• Computational finite dependence: find and exploit the finite dependence structure in applications by comparing the distributions of future states at different points of the state space, Arcidiacono & Miller (2019)

• Identification literature: the discount factor by Abbring & Daljord (2020), and further special cases and circumstances