Efficient counterfactual estimation in semiparametric discrete choice models: a note on Chiong, Hsieh, and Shum (2017)

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.

11,126 characters · 2 sections · 4 citation commands

Rendered from LaTeX for readability, not typeset faithfully. Citation keys are highlighted; maths is left as source; figures, tables and equation environments are summarised rather than reproduced; unrecognised commands are greyed out so nothing is silently dropped. Email addresses are removed.

Efficient counterfactual estimation in semiparametric discrete choice models: a note on chiong2017counterfactual

\onehalfspacing

abstractI suggest an enhancement of the procedure of \citet*{chiong2017counterfactual} for calculating bounds on counterfactual demand in semiparametric discrete choice models. Their algorithm relies on a system of inequalities indexed by cycles of a large number $M$ of observed markets, and hence seems to require computationally infeasible enumeration of all such cycles. I show that such enumeration is unnecessary because solving the “fully efficient” inequality system exploiting cycles of all possible lengths $K=1,\dots,M$ can be reduced to finding the length of the shortest path between every pair of vertices in a complete bidirected weighted graph on $M$ vertices. The latter problem can be solved using the Floyd--Warshall algorithm with computational complexity $O\left(M^3\right)$, which takes only seconds to run even for thousands of markets. Monte Carlo simulations illustrate the efficiency gain from using cycles of all lengths, which turns out to be positive, but small.

The Algorithm

The family of inequalities for the linear program in chiong2017counterfactual takes the form

align[align omitted — 458 chars of source]

for every cycle $l_1,\dots,l_{K},l_1$ from $\mathcal{M}= \{1,\dots,M\}$ with $l_K=M+1$. Here $\boldsymbol{\delta}^m \in \mathbb{R}^J$ and $\mathbf{s}^m \in \Delta_J$ are the mean utility vector and the market share vector for market $m\in \mathcal{M}$, $\boldsymbol{\delta}^{M+1}$ is the mean utility vector for the counterfactual market $M+1$ and $\mathbf{s}^{M+1}$ is the choice variable -- the counterfactual market share to be bounded. Denote the inequality (ref) by $\text{ineq}(l_1,\dots,l_{K-1})$.

The number of possible cycles in a complete graph is exponential in $M$ and is of order $10^{20}$ already for $M=22$\footnote{See sequence A119913 in the Online Encyclopedia of Integer Sequences}. Therefore, simple enumeration is computationally infeasible and chiong2017counterfactual resort to using a (tiny) subset of inequalities (ref) corresponding to cycles of length $K=2$. I will show that enumeration is not necessary for this problem and that the full system of inequalities is easy to construct using graph optimization.

Define $G$ to be a complete bidirected weighted graph on vertices $\mathcal{M}$ with weight $w_{ij} = \left(\boldsymbol{\delta}^{i}-\boldsymbol{\delta}^{j}\right)'\mathbf{s}^{i}$ assigned to edge $(i,j) \in \mathcal{M}\times \mathcal{M}$. Since the mean utilities and shares for markets $\mathcal{M}$ are identified via cyclic monotonicity, it holds that

align*[align* omitted — 125 chars of source]

for every path $l_1,\dots,l_{K},l_{K+1}=l_1$ from $\mathcal{M}$, and hence $G$ has no negative cycles.

Note that the left-hand side of the inequality (ref) depends on $\boldsymbol{\delta}^{l_1}$ and so the inequalities for different values of $l_1$ are generally non-parallel. Hence, for each $l_1$, we can minimize the right-hand side over all possible paths $l_1,\dots,l_{K-1}$ starting from $l_1$ to get the sharpest inequality.

This minimization problem resembles the problem of finding the shortest path from vertex $l_1$ in the graph $G$, but is not equivalent to it because of the presence of the second term in (ref), corresponding to the last edge in the path.

I suggest iterating through $M(M-1)$ ordered pairs $(l_1,l_{K-1})$ of different vertices from $\mathcal{M}$ and, for each such pair, finding the shortest path that connects $l_1$ and $l_{K-1}$ in graph $G$. This can be accomplished using the Floyd--Warshall algorithm, which has polynomial computational complexity $O\left(M^3\right)$ for graphs with no negative cycles such as $G$. The length of the shortest path between $l_1$ and $l_{K-1}$ corresponds to the sharpest of the family of inequalities

align*[align* omitted — 214 chars of source]

from which we can then pick the sharpest one over $l_{K-1}$.

I suggest the following algorithmic implementation:

enumerate• Run the Floyd--Warshall algorithm on graph $G$, obtaining a matrix $D_G$ of shortest path lengths between every pair of vertices. Set the diagonal elements $(D_G)_{ii}=0$ for all $i\in\mathcal{M}$. • For every $l_1\in \mathcal{M}$, \begin{itemize} • for every $l\in \mathcal{M}$, set $\text{rhs}(l_1,l) = (D_G)_{l_1,l} + \left(\boldsymbol{\delta}^{l}-\boldsymbol{\delta}^{M+1}\right)'\mathbf{s}^{l}$, • set $l^*=\arg \min_{l\in\mathcal{M}}\text{rhs}(l_1,l)$, • save the inequality $\text{ineq}_{l_1}^*$ with the right hand side $\text{rhs}(l_1,l^*)$. \end{itemize} • The resulting system of $M$ inequalities $\text{ineq}_{1}^*,\dots,\text{ineq}_{M}^*$ is equivalent to the system (ref) with all cycles exhausted.

Monte Carlo Simulation

I extend the Monte Carlo exercise of chiong2017counterfactual and compare performance of their original procedure using only 2-cycles (denoted CHS) with the proposed procedure exhausting all possible cycles (denoted All cyc.).

I use the following two model specifications: one is multinomial logit as in chiong2017counterfactual and the other is multinomial probit with the same DGP parameters as the logit and with the covariance matrix of the error term \[ \Sigma=

pmatrix[pmatrix omitted — 62 chars of source]

. \] A counterfactual of interest is the increase of price of good $j$ by 1% (denoted $p_j\uparrow$), for $j=1,2,3.$ As can be seen from Tables (ref) and (ref), the fully efficient procedure always dominates the CHS procedure both in terms of widths of the bounds and their standard errors. Although the gain is minimal and is unlikely to be relevant in practice, I suggest using the fully efficient procedure since it bears no extra computational costs (average computational time is less than 20 seconds for $M=1000$ and is less than 3 seconds for $M\in \{200,500\}$).

table[table omitted — 1,873 chars of source]

table[table omitted — 1,938 chars of source]