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

The family of inequalities for the linear program in Chiong et al. (2017) takes the form

	$\displaystyle\left(\bm{\delta}^{l_{1}}-\bm{\delta}^{M+1}\right)^{\prime}\mathbf{s}^{M+1}$	$\displaystyle\leq-1^{\prime}(D_{1}\circ S_{1})1=\sum_{k=1}^{K-1}\left(\bm{\delta}^{l_{k}}-\bm{\delta}^{l_{k+1}}\right)^{\prime}\mathbf{s}^{l_{k}}$
		$\displaystyle=\sum_{k=1}^{K-2}\left(\bm{\delta}^{l_{k}}-\bm{\delta}^{l_{k+1}}\right)^{\prime}\mathbf{s}^{l_{k}}+\left(\bm{\delta}^{l_{K-1}}-\bm{\delta}^{M+1}\right)^{\prime}\mathbf{s}^{l_{K-1}}$		(1)

for every cycle $l_{1},\dots,l_{K},l_{1}$ from $\mathcal{M}=\{1,\dots,M\}$ with $l_{K}=M+1$. Here $\bm{\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}$, $\bm{\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 (1) 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$¹¹1See sequence A119913 in the Online Encyclopedia of Integer Sequences. Therefore, simple enumeration is computationally infeasible and Chiong et al. (2017) resort to using a (tiny) subset of inequalities (1) 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(\bm{\delta}^{i}-\bm{\delta}^{j}\right)^{\prime}\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

$\displaystyle\sum_{k=1}^{K}\left(\bm{\delta}^{l_{k}}-\bm{\delta}^{l_{k+1}}\right)^{\prime}\mathbf{s}^{l_{k}}\geq 0$

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 (1) depends on $\bm{\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 (1), 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

$\displaystyle\mathcal{F}_{l_{1},l_{K-1}}=\left\{\text{ineq}(l_{1},\dots,l_{K-1}):\,\,\,l_{2},\dots,l_{K-2}\in\mathcal{M}\text{ s.t. }l_{1},\dots,l_{K-1}\text{ is a path from }l_{1}\text{ to }l_{K-1}\right\},$

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

I suggest the following algorithmic implementation:

1. 1.

   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}$.

2. 2.

   For every $l_{1}\in\mathcal{M}$,

   • •

     for every $l\in\mathcal{M}$, set $\text{rhs}(l_{1},l)=(D_{G})_{l_{1},l}+\left(\bm{\delta}^{l}-\bm{\delta}^{M+1}\right)^{\prime}\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^{*})$.

3. 3.

   The resulting system of $M$ inequalities $\text{ineq}_{1}^{*},\dots,\text{ineq}_{M}^{*}$ is equivalent to the system (1) with all cycles exhausted.

I extend the Monte Carlo exercise of Chiong et al. (2017) 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 Chiong et al. (2017) and the other is multinomial probit with the same DGP parameters as the logit and with the covariance matrix of the error term

$$\Sigma=\begin{pmatrix}1&-0.7&0.3\\ -0.7&1&0.3\\ 0.3&0.3&1\end{pmatrix}.$$

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 1 and 2, 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\}$).