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.
113,141 characters · 27 sections · 3 citation commands
Yogurts Choose Consumers? Estimation of Random-Utility Models via Two-Sided Matching
Discrete choice models play a tremendous role in applied work in economics. In these models, an agent $i$ characterized by a utility shock $\varepsilon _{i}\in \Omega $ must choose from a finite set of alternatives $j\in \mathcal{J}$ in order to maximize her utility. The random utility framework pioneered by \citeasnoun{mcfadden1978modelling} assumes that the utility $\mathcal{U}_{\varepsilon _{i}j}\left( \delta _{j}\right) $ that agent $i$ gets from alternative $j$ depends on $\delta _{j}$, a systematic utility level associated with alternative $j$ (possibly parameterized as a function of regressors such as characteristics of alternative $j$) which is identical across all agents, and a realization $ \varepsilon _{i}$ of agent $i$'s random utility shocks. The agent chooses the alternative yielding maximal utility:
We focus on parametric random utility models, where the function $\mathcal{U}:\left( \varepsilon ,j,\delta \right) \in \Omega \times \mathcal{J}\times \mathbb{R}\mapsto \mathcal{U} _{\varepsilon j}\left( \delta \right) \in \mathbb{R}$ as well as the distribution of $\varepsilon $ in the population, denoted $P$, are known to the researcher. Particular instances of these models are Additive Random Utility Models (hereafter ARUMs), including Logit or Probit models, where $\Omega =\mathbb{R} ^{\mathcal{J}}$, $\mathcal{U}_{\varepsilon _{i}j}\left( \delta _{j}\right) =\delta _{j}+\varepsilon _{ij}$, and $\varepsilon $ follows a Gumbel or Gaussian distribution. However, our results extend to the more general class of Non-Additive Random Utility Models (NARUMs), in which $\mathcal{U} _{\varepsilon _{i}j}\left( \delta _{j}\right) $ is not (quasi-)linear in $\delta _{j}$.
Under an assumption guaranteeing that agents are not indifferent between any pair of alternatives (see Assumption 2 below), we can define the vector-valued demand map $\sigma \left( .\right) $, the $j$-th component ($j\in\mathcal{J}_0$) of which is defined as\ the probability that alternative $j$ dominates all the other ones, given the vector of systematic utilities $\left( \delta _{j}\right) _{j\in \mathcal{J}}$:
The main focus of the paper pertains to {\em demand inversion}: given a vector of observed market shares $\left( s_{j}\right) _{j\in \mathcal{J}}$, how can one characterize and compute the full set of utility vectors $\left( \delta _{j}\right) _{j\in \mathcal{J}}$ such that $s=\sigma \left( \delta \right)$ -- that is, which rationalizes the observed market shares? (In cases where the distribution $P$ of the utility shocks depends on parameters unknown to the researcher, which arises in many applications as well as in our simulations and application below, demand inversion refers to recovering $\delta_j$ for a given set of parameters of $P$.) Additionally, the demand map may also be {\em non-invertible}, which arises when multiple vectors $\delta $ solve the demand inversion problem.
We establish a new equivalence principle between the problem of demand inversion and the problem of stable matchings in two-sided models with Imperfectly Transferable Utility (ITU). More precisely, we show that a discrete choice model can always be interpreted as a two-sided matching market where consumers and alternatives are viewed as firms and workers; and that the demand inversion problem, that is the recovery of utility vectors $\left( \delta _{j}\right)_{j\in \mathcal{J}}$, can be reformulated as the equilibrium problem of determining competitive wages in the corresponding matching market. In other words, the identified set of solution vectors $\delta $ coincides with the set of equilibrium wages in the matching market. This equivalence implies two important contributions:
{ In this paragraph we discuss how our paper relates to the existing literature on (1) demand inversion and (2) two-sided matching.
Demand inversion literature. Demand inversion is a crucial intermediate step for estimating aggregate discrete-choice models of product-differentiated markets; see, e.g., \citeasnoun{berry1994estimating} and \citeasnoun{berry1995automobile} (BLP). It also plays an important role in two-step estimation procedures for dynamic discrete-choice models\footnote{ Specifically, even though we don't pursue the connection here, the demand inversion problem considered in this paper also applies straightforwardly to the problem in dynamic discrete-choice estimation of “inverting" the choice-specific value functions from the conditional choice probabilities.} (including \citeasnoun {hotz1993conditional}, \citeasnoun{aguirregabiria2002swapping}, \citeasnoun{bajari2007estimating}, \citeasnoun{arcidiacono2011conditional}, \citeasnoun{kristensen2014ccp}).
Theoretically, there is a large literature that tackles the problem of the invertibility of the demand map utilizing either differentiability or monotonicity of the demand map. The first approach, based on global univalence theorems, requires the differentiability of the mapping $\sigma \left( \delta \right) $. \footnote{The Hadamard-Palais univalence theorem (\citeasnoun{palais1959natural}) asserts that (i) if $\sigma :\mathbb{R}^{J}\rightarrow \mathbb{R}^{J}$ is $C^{1}$, (ii) if its Jacobian is invertible at all points, and (iii) if $\left\Vert \sigma \left( \delta \right) \right\Vert \rightarrow \infty $ as $\left\Vert \delta \right\Vert \rightarrow \infty $, then $\sigma $ is globally invertible; further results are collected in \citeasnoun{Parthasarathy} and \citeasnoun{RadulescuRadulescu}.} Such results were used by \citeasnoun{chiappori} and \citeasnoun{kristensen2014ccp} to study (resp.) multinomial choice and nonadditive random utility models. The results in \citeasnoun{GaleNikaido} focus on uniqueness, leaving existence aside: assuming that the Jacobian of $\sigma $ is a P-matrix and that the domain is a rectangle, Gale-Nikaido's result guarantees the injectivity of $\sigma $\textemdash namely, that $\sigma ^{-1}\left( \left\{ s\right\} \right) $ should have at most one point\textemdash but can be empty.
A second approach to demand inversion relies on gross substitutes\textemdash a form of monotonicity\textemdash that $\sigma _{j}$ is decreasing, or at least nonincreasing, with respect to $\delta _{j^{\prime }}$. This category of papers includes the literature on ARUMs, where this property holds automatically (eg. \citeasnoun{mcfadden1978modelling}). \citeasnoun {hotz1993conditional} study the problem of the nonemptiness of $\sigma ^{-1}\left( s\right)$, within general ARUMs ; \citeasnoun{berry1994estimating} provided a complete argument (which extends to nonadditive random utility models), and also shows uniqueness of the vector of systematic utilities under continuity conditions. \citeasnoun{magnac2002identifying} investigate identification of structural parameters (period utility flows) in dynamic discrete choice models. \citeasnoun{norets2013surjectivity} focus on the surjectivity of ARUMs, under the assumption of absolute continuity of the distribution of the additive utility shocks. More broadly, \citeasnoun{berry2013connected} show injectivity in general demand systems with gross substitutes (thus going beyond random utility models) under a connected strong substitute assumption.
To date, the existing literature has not provided a general characterization of the identified utility set $\sigma^{-1}(s)$, defined as the set of utility vectors $\left( \delta _{j}\right) $ which rationalize a vector of market shares $\left( s_{j}\right)$. This paper is the first to consider situations when the identified utility set $\sigma^{-1}\left( \left\{ s\right\} \right) $ is non-singleton. In addition, most of the papers cited above provide little guidance on computing the identified set.\footnote{As \citeasnoun[p. 10]{berry2015identification} underline, \textquotedblleft (...) the invertibility result of \citeasnoun{berry2013connected} is not a characterization (or computational algorithm) for the inverse\textquotedblright.} Besides a handful of models,\footnote{These include the logit, nested logit, and random-coefficient logit models (\citeasnoun{berry1994estimating}, \citeasnoun{berry1995automobile}, \citeasnoun{dube2012improving}).} there are no well-established procedures for demand-inversion in general (non-additive) random utility models with arbitrary error distributions. Our paper aims to fill this gap. In doing so, it builds on a set of recent papers which have reformulated the problem of demand inversion in ARUMs as an optimal transport problem, using the tools of convex duality. This approach was pioneered by \citeasnoun{galichon2017cupid}, and was extended to ARUMs with possibly noncontinuous distributions of unobserved heterogeneity by \citeasnoun{chiong2015duality}, and to continuous choice problems by \citeasnoun{CGHP}. However, these papers do not cover nonadditive random utility models, and do not characterize the structure of the identified set.
Two-sided matching literature. We provide a brief and incomplete review of the two-sided matching literature, as one key result in this paper is to show the equivalence between demand inversion and a two-sided matching model. The matching literature is split between models with non-transferable utility (NTU), and transferable utility (TU), with intermediate cases called imperfectly transferable utility (ITU).\footnote{A key reference for the matching literature (TU, NTU and ITU alike) is \citeasnoun{roth1992two}, while \citeasnoun{galichon2015optimal} focuses on the TU case, or equivalently, optimal transport methods.} A connection was made earlier between TU matching models and ARUMs (see \citeasnoun{galichon2017cupid} and \citeasnoun{chiong2015duality}), and in the present paper, we are making a novel connection between matching models with ITU and NARUMs.
A large class of algorithms for computing matching models consists of “deferred acceptance algorithms” which revolve around Tarski's fixed point theorem, and interpreting stable matchings as fixed points of monotone mappings. They apply to NTU and ITU models. These ideas appeared in \citeasnoun{Adachi2000}, followed by \citeasnoun{Fleiner}, \citeasnoun{EcheniqueOvideo} and \citeasnoun{hatfield2005matching}. The seminal deferred acceptance algorithms (\citeasnoun{gale1962college}; \citeasnoun{crawford1981job}; \citeasnoun{kelso1982job}) can be interpreted in this way.
Other methods are “descent methods,” which rely on a reformulation of the problem as a convex optimization problem, and apply in the TU case. Some of the methods involve coordinate descent (as the auction algorithm of \citeasnoun{bertsekas1989auction}), while some involve gradient descent (as the semi-discrete approach of \citeasnoun{aurenhammer1987power}). The linear programming solution to the optimal assignment problem described in \citeasnoun{shapley1971assignment} also belongs in this category. The study of rates of convergence of these algorithms have been the subject of intense study; see the book \citeasnoun{peyrecuturi} and \citeasnoun{Book_assignment} for results and further references. }
Section (ref) introduces the general random utility framework which is the focus of this paper and provides examples. Section (ref) presents our main equivalence result between NARUMs and two-sided matching problems, and discusses the lattice structure of the identified utility set. Based on the equivalence result, in Section (ref) we introduce several matching-based algorithms which can solve a wide variety of random utility models. Section (ref) contains two simulation investigations of the algorithms, including the pure characteristics model. Section (ref) utilizes our matching approach to estimate a spatial voting model using electoral data from the 1999 European Parliament elections. Section (ref) concludes. Proofs and several additional theoretical results are collected in the appendix.
Let $\mathcal{J}_{0}=\mathcal{J}\cup \left\{ 0\right\} $ be a finite set of alternatives, where $j=0$ denotes a special alternative which serves as a benchmark (see section (ref) below). The agent's program is thus
where $u_{\varepsilon _{i}}$ is the indirect utility of an agent with shock $ \varepsilon _{i}$. The utility agent $i$ derives from alternative $j$ depends on the systematic utility vector $\delta _{j}$ associated with this alternative, and on the realization $\varepsilon _{i}$\ of this agent's utility shock. We will work under two assumptions:
These two assumptions are standard in the literature, and are automatically satisfied in ARUMs. Assumption (ref) (a) is a standard measurability condition, and (b) is often invoked in the literature on non-separable models (see, e.g., \citeasnoun{Matzkin2007}).\footnote{Assumption 1 also circumscribes the set of models we consider here. Specifically, it rules out purely "horizontal" (Hotelling) choice models, where the utility of consumer $\varepsilon$ for store $j$ is $\mathcal{U}_{\varepsilon j}(\delta_j) = -|\delta_{j}-\varepsilon|$ , interpreted as the (minus the) absolute distance between the consumer's home location $\varepsilon$ and the store's location $\delta_j$ where $\delta_j, \varepsilon \in [0,1]$. This specification violates the monotonicity condition (Assumption 1(b)). Interestingly, it turns out the {\em quadratic} version of this model can be reparametrized in a way which satisfies our modelling assumptions; see Section 6 below.}
Assumption (ref) rules out indifference (precisely, an event of measure zero) between two alternatives, and is maintained in practically all the applied discrete choice literature. {In earlier versions of the paper (available from the authors upon request), we showed that the results in this paper hold even without Assumption (ref), albeit at the greater notational expense of introducing set-valued functions.} In the present paper, for simplicity, we maintain Assumption (ref) as it suffices for our purposes.
Under Assumption (ref), the demand of alternative $j$ (defined in ((ref)) above) corresponds to the fraction of consumers who prefer weakly or strictly alternative $j$ to any other one:
Importantly, the uniqueness of the vector of market shares associated with a given utility vector $\delta $ does not imply that the demand inversion problem has a unique solution. There may be multiple vectors $\delta $ such that $ \sigma (\delta )=s$. Under Assumptions (ref) and (ref), the vector of market shares $s=\sigma \left( \delta \right) $ is a probability vector on $ \mathcal{J}_{0}$, which prompts us to introduce $\mathcal{S}_{0}$, the set of such probability vectors as
We formalize the definition of the demand map.
Any discrete choice model requires some normalization, because the choice probabilities result from the comparison of the relative utility payoffs from each alternative. Throughout the paper we normalize the systematic utility associated to the default alternative to zero:
and we use
to denote the map induced by this normalization.
In the special ARUM case where $\mathcal{U} _{\varepsilon _{i}j}\left( \delta _{j}\right) =\delta _{j}+\varepsilon _{ij}$ , imposing normalization ((ref)) is innocuous because the vector of systematic utilities $\left( \delta _{j}\right) $ yields the same choice problem as the vector $\left( \delta _{j}+c\right) $ where $c$ is a constant; hence, for ARUMs, any normalization will yield the same identified utility vectors $\delta $ up to an additive constant. However, this is no longer true in nonadditive models, for which the normalization ((ref)) entails some loss of generality.\footnote{While it is possible to reparameterize any NARUM into an ARUM $\mathcal{U}_{\varepsilon j}(\delta)=\gamma_j+\eta_j$ by defining $\gamma_j\equiv \int \mathcal{U}_{\varepsilon j}(\delta) dP_{\varepsilon}$ and $\eta_j= \mathcal{U}_{\varepsilon j}(\delta)-\gamma_j$, it is not clear whether this reparameterization simplifies the demand inversion problem of recovering $\delta$, which is the main point of our paper (in some cases, the reparameterization obfuscates the demand inversion problem).} We explore this below in Section 5.
Next, we consider several examples of random utility models falling within our framework. Since we assume that market shares are generated by the mapping in Eq. ((ref)), we implicitly assume that the random element $\varepsilon$ is independently and identically distributed across all consumers in the market. However, we make no restrictions on $\varepsilon$ across alternatives: as the examples below show, $\varepsilon$ can be individual-specific, choice-specific, or some combination of the two.
In this section, we show a central result of this paper; namely, an equivalence between discrete-choice models and two-sided matching problems. This equivalence is noteworthy as discrete choice problems are traditionally considered to be “one-sided” problems. However, we will demonstrate that they are equivalent to a two-sided \textquotedblleft marriage problem\textquotedblright\ between consumers and yogurts, where both sides of the market must assent to be matched.
{Specifically, our main theorem demonstrates an equivalence between the discrete-choice framework described in the previous section and a two-sided matching market with imperfectly transferable utility (see \citeasnoun{galichon2014empirical}). } A consequence of this equivalence is that the demand inversion problem for estimating discrete-choice models can be equivalently formulated as solving for equilibrium utility payoffs from the corresponding two-sided matching problem, a well-understood exercise for which a number of algorithms are available.
We begin by formally defining the object of interest for demand inversion, which is to recover the identified utility set:
Requiring non-zero market shares is a standard assumption in demand inversion of discrete-choice models; see, e.g., Lemma 1 of \citeasnoun{berry2014identification}.\footnote{ In the ARUM case, a sufficient condition for this is that $\varepsilon$ has full-support (a nowhere vanishing density) on $\mathbb{R}^{\mathcal{J}_{0}}$ (see, e.g., \citeasnoun{GalichonHsieh2019}), which is satisfied in models such as logit, probit, and mixed-logit. However, it may fail to hold in, e.g., pure characteristic models (see, e.g., \citeasnoun{song2007measuring}), without sufficient variation in the choice-specific characteristics. Moreover, we assume throughout that the demand model is correctly specified, so that the identified utility set in ((ref)) is non-empty. }
Next we introduce a matching game between consumers and yogurts, which is essentially that of \citeasnoun{demange1985strategy}; our presentation of this model is inspired by the presentation in chapter 9 of \citeasnoun{roth1992two}\footnote{ Demange and Gale's model is discrete and extends the model of \citeasnoun{shapley1971assignment} beyond the transferable utility setting. See also \citeasnoun{crawford1981job}, \citeasnoun{kelso1982job}, \citeasnoun{hatfield2005matching}. We formulate a slight variant here in that we (1) we allow for multiple agents per type and (2) do not allow for unmatched agents. However, this leaves analysis essentially unchanged.}. In this matching model, one side of the market consists of a continuum of consumers, distinguished by type $\varepsilon$, while the other side is an equi-massed continuum of jars of yogurt, distinguished by alternative (brand) $j\in\mathcal{J}_0$. We start by introducing some terminology. Let $\mathcal{M}\left( P,s\right) $ be the set of probability distributions on $ \Omega \times \mathcal{J}_{0}$ with marginal distributions $P$ and $s$; namely, $\pi \in \mathcal{M}\left( P,s\right) $ if and only if $\pi \left( B\times \mathcal{J}_{0}\right) =P\left( B\right) $ for all $B$ (Borel-measurable subsets of $\Omega$), and $\pi \left( \Omega \times \left\{ j\right\} \right) =s_{j}$ for all $j\in \mathcal{J}_{0}$.
{Let $u_{\varepsilon}$ (resp. $v_j$) denote utility payoffs for each consumer $\varepsilon$ (resp. yogurt $j$) from the matching game. These payoffs are endogenously determined in equilibrium, as will be clear below.} Let $f_{\varepsilon j}\left( u\right) $ be the transfer (positive or negative) needed by a consumer $ \varepsilon $ in order to reach utility level $u\in \mathbb{R}$ when matched with a yogurt $j$. Symmetrically, let $g_{\varepsilon j}\left( v\right) $ be the transfer needed by a yogurt $j$ in order to reach utility level $v\in \mathbb{R}$ when matched with a consumer $\varepsilon $. (The connection between $f$ and $g$ and the primitives of the discrete choice model will be clarified below, in Eq. (ref).) The functions $ f_{\varepsilon j}\left( .\right) $ and $g_{\varepsilon j}\left( .\right) $ are assumed increasing for every $\varepsilon $ and $j$.
{ We describe this game in the context of a dance party where consumers (indexed by $\varepsilon$) seek out jars of yogurt $j$ to dance with. Each consumer $\varepsilon$ charges a price of $u_{\varepsilon}$ utils for dancing; similarly, yogurt $j$ charges a price of $v_j$ for dancing. Thus, a dance between consumer $\varepsilon$ and yogurt $j$ involves a payment of $g_{\varepsilon j}(v_j)$ from consumer $\varepsilon$ to yogurt $j$, and a payment of $f_{\varepsilon j}(u_\varepsilon)$ from the yogurt to the consumer. These transfers can be negative: for instance, if yogurt $j$ already provides consumer $\varepsilon$ with utility exceeding $u_{\varepsilon}$ by dancing with her, then $f_{\varepsilon j}(u_\varepsilon)<0$ and involves a payment from consumer $\varepsilon$ to yogurt $j$. }
Condition (i) implies that if a random vector $\left( \varepsilon ,j\right) $ has distribution $\pi \in \mathcal{M}\left( P,s\right) $, then $\varepsilon \sim P$ and $j\sim s$. Hence, $\pi $ is interpreted as the probability distribution that a consumer with utility shock $\varepsilon $ is matched with a yogurt of type $j$; in other words, $\pi \left( j|\varepsilon \right) $ denotes the conditional probability that an individual with utility shock $ \varepsilon $ chooses yogurt $j$, which is degenerate (equaling 0 or 1) under Assumption 2. To understand condition (ii), consider that if there exists a consumer $\varepsilon $ and a yogurt of type $j$ for which $f_{\varepsilon j}\left( u_{\varepsilon }\right) +g_{\varepsilon j}\left( v_{j}\right) <0$, then there exists $u^{\prime }>u_{\varepsilon }$ and $v^{\prime }>v_{j}$ such that $f_{\varepsilon j}\left( u^{\prime }\right) +g_{\varepsilon j}\left( v^{\prime }\right) =0$. In other words, $(u', v')$ are feasible for $\left( \varepsilon ,j\right) $ and strictly improve upon the equilibrium payoffs $ u_{\varepsilon }$ and $v_{j}$, which is ruled out in equilibrium. { The feasibility condition (iii) rules out matchings involving net positive transfers ($f_{\varepsilon j}(u_{\varepsilon})+g_{\varepsilon j}(v_j)>0$) which, intuitively, are those where one (or both) of the agents have equilibrium payoffs which are inachievably high compared to the utility they supply each other from matching. }
The next theorem establishes that the demand inversion problem is equivalent to a matching problem. The proofs for this and all subsequent claims are in the appendix.
We offer some intuition of the equivalence here. A matching equilibrium requires that, given the transfer functions, the equilibrium transfers be set such that {\em both} sides of the market (consumers and yogurts) are happy with their matched partners. On the consumer side, consumer $ \varepsilon $ seeks the yogurt $j$ which offers her the highest payoff $\mathcal{U}_{\epsilon}$. On the yogurt side, each yogurt $j$ also seeks to maximize its payoff, which is equivalent to {\em minimizing} the mean utility $\delta_j$ that consumers receive from them; for that reason, we have the yogurt's payoff $v_j=-\delta_j$. To understand the intuition for the transfer functions ((ref)), note that if we plug these into Definition 3, the no-blocking pair condition becomes
and the feasibility pair condition becomes
which correspond to the conditions characterizing optimal consumer choices in the discrete-choice problem.
Our equivalence result states that the identified set of utilities in the discrete-choice demand problems corresponds to the equilibrium set of some matching problem. This matching equivalence result also raises the possibility of multiplicity of the identified set of utilities. Assumption (ref) implies a unique demand map (Eq. ((ref))), and hence a unique allocation in the matching problem. However, just as in \citeasnoun{shapley1971assignment}, there may be multiple payoffs (corresponding to the $\delta$'s here) which support the equilibrium allocation. We will return to this below.
In the special case when the random utility model is additive (ARUM) as in example (ref), one has $f_{\varepsilon j}\left( u\right) =u$ and $g_{\varepsilon j}\left( -\delta \right) =-\mathcal{U}_{\varepsilon j}\left( \delta \right) =-\varepsilon _{j}-\delta _{j}$, so that the stability conditions become $ u_{\varepsilon }+v_{j}\geq \varepsilon _{j}$ with equality for $\left( \varepsilon ,j\right) \in Supp(\pi )$. As noted initially in \citeasnoun{galichon2017cupid}, this problem is now equivalent to a matching problem with transferable utility, where the joint surplus of a match between a consumer $\varepsilon $ and a yogurt $j$ is $\varepsilon _{j}$. We will discuss these in more detail in section (ref) below.
Next, we show that the set-valued function $s\rightarrow \tilde{\sigma}^{-1}\left( s\right) $ is isotone\footnote{Isotone has the meaning of (monotone) increasing, and is a standard term used in the literature on lattices (see \citeasnoun{topkissupermodularity} for a reference on lattices and isotonicity in economics).} (in a sense to be made precise) and that $\tilde{\sigma}^{-1}\left( s\right) $ has a lattice structure.
The lattice structure is very useful for deriving algorithms for computing the identified utility set $\tilde{\sigma}^{-1}\left( s\right) $ when demand is non-invertible. The literature on the estimation of discrete choice models has favored an approach based on imposing conditions guaranteeing invertibility of demand, or equivalently situations in which $\tilde{\sigma}^{-1}\left( s\right) $ is restricted to a single point. In particular, \citeasnoun{berry2013connected} (hereafter BGH) provide conditions under which $\tilde{\sigma}^{-1}\left( s\right) $ should contain at most one point, from which it also follows that the map $ s\rightarrow \tilde{\sigma}^{-1}\left( s\right) $ is isotone on its domain. In contrast, our approach here imposes minimal assumptions, and one must consider {\em non-invertible} models, in which the demand map ((ref)) is not one-to-one and $\tilde{\sigma}^{-1}\left( s\right) $ is a set. In this case, we need to generalize the notion of isotonicity which applies to the identified set $\tilde{\sigma}^{-1}(.)$. The next theorem states that the correct generalization is the notion of isotonicity with respect to {\em Veinott's strong set order}.\footnote{See e.g. \citeasnoun{veinottlectures}. Veinott's strong set order provides an ordering over sets. Let $\mathcal{X}$ and $\mathcal{X}'$ be two subsets in $\mathbb{R}^d$; we say that $\mathcal{X} < \mathcal{X}'$ in the Veinott strong set order iff $\forall x\in \mathcal{X}, x'\in\mathcal{X}'$, the “join” (or componentwise minimum) $x\wedge x' \in \mathcal{X}$ and the “meet” (or componentwise maximum) $x\vee x' \in \mathcal{X}'$.} For the following, recall the lattice \textquotedblleft join\textquotedblright\ and \textquotedblleft meet\textquotedblright\ operators ($\wedge $ and $\vee $) are defined by $ \left( \delta \wedge \delta ^{\prime }\right) _{j}:=\min \left\{ \delta _{j},\delta _{j}^{\prime }\right\} $ (componentwise minimum) and $\left( \delta \vee \delta ^{\prime }\right) _{j}:=\max \left\{ \delta _{j},\delta _{j}^{\prime }\right\} $ (componentwise maximum).
In the special case where $s\rightarrow \tilde{\sigma}^{-1}\left( s\right) $ is a singleton, we recover the isotonicity of the inverse demand as in BGH. Going further, by taking $s=s^{\prime }$ in Theorem (ref), we obtain that, whenever it is non-empty, the set $\tilde{\sigma }^{-1}\left( s\right) $ is a lattice\footnote{ Whether the identified set is empty is considered in the Section (ref).}:
This result is similar to \citeasnoun{demange1985strategy}, who showed that the set of payoffs which ensures a stable allocation is a lattice whenever it is non-empty. This implies that the set of identified utilities has a \textquotedblleft maximal\textquotedblright\ (resp. \textquotedblleft minimal\textquotedblright ) element which is composed of the component-wise upper- (resp. lower-) bounds among all the utility vectors in $\tilde\sigma^{-1}(s)$. The upper bound corresponds to the unanimously most preferred stable allocation for the consumers (\textquotedblleft consumer-optimal\textquotedblright ) and the unanimously least preferred stable allocation for the yogurts; conversely, the lower bound corresponds to the unanimously most preferred stable allocation for the yogurts (\textquotedblleft yogurt-optimal\textquotedblright ) and least preferred for the consumers. Formally, define
Then the lattice property implies:
Practically, most applications of partially identified models focus on computing the component-wise upper and lower bounds of the identified set of parameters; for general partially identified models, the vector of component-wise bounds will typically lie {\em outside} the (joint) identified set of parameters. In contrast, our lattice result here implies that these component-wise upper and lower bounds constitute {\em sharp} upper and lower bounds for the parameter vector as a whole, in the sense that they are attainable for selection mechanisms which place all probability on the highest (for upper bound) or lowest (for lower bound) payoffs for consumers.\footnote{In addition, the upper- and lower-lattice bounds here are the “widest" possible in the sense that for each $j$, no utility lower than ${\delta^{\min}}_j$, or higher than $\delta^{\max}_j$, can rationalize the observed set of market shares. {Moreover, the equivalence theorem also implies that the identified utility set $\sigma^{-1}(s)$, while not necessarily convex, is connected, which derives from the properties of the core of matching games (section 9.2 of \citeasnoun{roth1992two}).} }
In addition, the matching literature provides algorithms to compute these extremal elements, which can be directly used to assess multiplicity: indeed, $\tilde{\sigma}^{-1}\left( s\right) $ is a single element (point-identified) if and only if its minimal and maximal elements coincide. This flexibility in handling models for which the researcher may not know {\em a priori} whether model parameters are point- or partially-identified is an important contribution of the matching approach developed in this paper. We turn to these algorithms next.
The equivalence established in Theorem (ref) between matching and discrete-choice models allows us to leverage several matching algorithms for both NARUMs and ARUMs. The use of these algorithms in the empirical discrete-choice literature is new. In addition, matching-based algorithms have several advantages over existing procedures: (i) they can handle non-invertibility of the demand map, as all of these algorithms allow for the case where multiple utility vectors can rationalize the same set of market shares; and (ii) these algorithms do not require smoothness of the demand map and therefore can handle some well-known models\textemdash like the pure characteristics model\textemdash which have non-smooth demand maps. In contrast, existing algorithms for demand inversion often rely on directly solving the demand map $s_j=\sigma_j(\delta)$ for $\delta$ using fixed-point iterations or nonlinear-equation solvers, which typically requires smoothness of the demand map, and also rules out non-invertibility of the demand map.
We introduce three matching-based algorithms in this section. The first is an algorithm for matching models with imperfectly transferable utility (ITU) which can be used for demand inversion in both ARUMs or NARUMs. This algorithm, called {\em Market Share Adjustment}, is essentially an “accelerated” version of the classic deferred acceptance algorithm (\citeasnoun{gale1962college}, \citeasnoun{crawford1981job}), which iteratively adjusts the payoffs of the potential partners to achieve equilibrium. The second and third algorithms, in Section 4.2, are methods for computing stable allocations in two-sided matching models with transferable utility (TU), and apply only to ARUMs. We consider a {\em linear-programming} approach based on the classic \citeasnoun{shapley1971assignment} assignment game, and a version of the {\em auction algorithm} of \citeasnoun{bertsekas1992auction}, augmented to produce bounds for partially-identified settings.
While the model in this paper assumes a continuum of agents on each side of the market, for computational purposes we approximate this with a finite market populated by an equal (and large but finite) number, denoted $N$, of consumers and jars of yogurt.\footnote{In Appendix (ref) we present the {\em semi-discrete} algorithm for ARUMs, which is exact in that it computes the continuum problem directly. However, as we explain there, its use requires the unobserved taste vector to be (jointly) uniformly distributed over a polyhedron, which limits its general application.} On the consumer side, each consumer $i\in \left\{1,...,N\right\} $ is characterized by a value of the utility shock $\varepsilon_i$ drawn i.i.d. (across $i$) from $P$, the distribution of the utility shocks. For a given vector of market shares $\left(s_0, s_1,\ldots, s_J\right)$, the number of jars of each brand $j$ of yogurt are set proportionately to the observed market share; that is, $m_{j}\approx Ns_{j}\in \mathbb{N}$ of yogurts of type $j$ and, if needed, $m_{j}$ has been rounded to an adjacent integer so that $\sum_{j\in \mathcal{J}_{0}}m_{j}=N$. Throughout we maintain the utility normalization $\delta _{0}=0$.
Theorem (ref) establishes an equivalence between the identified utility set and equilibrium payoffs in a two-sided matching game with imperfectly transferable utility. Hence, for computing the identified utilities one could use the deferred-acceptance algorithms developed in \citeasnoun{crawford1981job} and \citeasnoun{kelso1982job} which are generalizations of Gale and Shapley's gale1962college deferred-acceptance algorithm. But these algorithms are very slow and inefficient, especially in the common situation where there are fewer products (i.e. “brands of yogurt”) than consumers.
As with all deferred-acceptance algorithms, there are two versions of the algorithm -- the “consumer-proposing” and “yogurt-proposing” versions -- return (resp.) the lattice upper bound or lower bound on the utility parameters. In the case when the model is point identified, the upper bound and lower bound will coincide; hence running both versions of this algorithm yields a data-driven assessment of whether the model is point- or partially-identified.
In the “consumer proposing” version, the utilities ($\delta$'s) start at a high level, and consumers choose, in successive rounds, jars of yogurts which maximize their utilities. Between rounds, the utilities pertaining to the brands of yogurts in excess demand (ie. chosen by more consumers than available jars) are decreased by an adjustment factor. Bidding continues until a round is reached where the reference brand of yogurt ($j=0$) is in excess demand: that is, when the number of consumers choosing jars of brand 0 is greater or equal to the number of its available jars. In the original \citeasnoun{kelso1982job} version, the adjustment is done for {\em each jar} of yogurt separately, leading to very slow convergence with a large number of consumers and jars. The MSA algorithm speeds this up by adjusting the utilities for {\em all jars of the same brand} of yogurt simultaneously. Since this accelerated process can lead to \textquotedblleft overshooting\textquotedblright\ (in which utilities move below their equilibrium values), the MSA algorithm involves running a deferred-acceptance procedure multiple times with successively smaller adjustment factors.\footnote{ This adjustment factor plays a role analogous to the step size in optimization procedures. One typically chooses a larger step size in initial exploration phases to move parameters away from regions where the optimum is unlikely to be. Choosing a larger step size speeds up the routine, but if the step size is too large, one might miss (“overshoot”) the optimum. Therefore, in later exploitation phases, one decreases the step size to achieve a better accuracy. Similar heuristics are used also to set the temperature parameter in simulated annealing, or the “learning rate” in machine learning procedures. }
We present below the pseudo code for the consumer-proposing version of the MSA algorithm, which obtains the lattice upper bound; Appendix (ref) contains a version of the algorithm which yields the lattice lower bound. Define $\bar{\delta}_{j}=\sup_{i\in \left\{ 1,...,N\right\} }\mathcal{U} _{\varepsilon_ij}^{-1}\left( \mathcal{U}_{i0}\left( \delta _{0}\right) \right) $. Clearly, $\bar{\delta}$ is an upper bound for the stable payoffs and for the lattice upper bound. Let $\eta^{tol}$ denote a small adjustment factor, which is a design parameter for the algorithm.
As shown above, the consumer-proposing MSA consists of a deferred-acceptance loop nested inside of an adjustment loop. In the deferred-acceptance loop, two cases can occur. In the “good case”, the deferred-acceptance loop starts with values $\delta_{j \in \mathcal{J}}$ above the lattice upper bound and an adjusting factor $\eta$ small enough, then all $\delta_{j \in \mathcal{J}}$ will reach the lattice upper bound without overshooting. In the “bad case”, that is when the deferred-acceptance loop starts with one $\delta_{j \in \mathcal{J}}$ below its upper bound and an adjusting factor $\eta$ small enough, then this $\delta_j$ will not decrease during the loop. The outer adjustment loop repeatedly calls the deferred-acceptance loop for decreasing values of the increment $\eta$. It terminates when the utilities outputted by the deferred-acceptance loop have all decreased (indicating that the approximation loop is in the “good case”); otherwise, the utilities are increased and the deferred-acceptance loop is called again.
While we have not yet formally proven convergence of the MSA algorithm, we find that it runs remarkably quickly in all our simulations, relative to the \citeasnoun{crawford1981job} algorithm. In practice, one can assess the convergence of the algorithm in the outer loop by comparing the actual market shares with the predicted market shares evaluated using the $\delta$'s returned in each call to the inner loop.
For ARUMs, we can use algorithms for matching models with transferable utility (TU). A well-known result in optimal transport theory (see \citeasnoun{galichon2015optimal}) states that the equilibrium matching under transferable utility maximizes the total surplus $\mathbb{E}\left[ \varepsilon _{\tilde{j}}\right] $ over all the distributions of $\left( \varepsilon ,\tilde{j}\right) $ such that $\varepsilon \sim P$ and $\tilde{j} \sim s$, that is $\pi $ solves
The equilibrium payoffs $u$ and $\delta $ are the parameters which optimize the dual problem:
These are convex programs which can be solved efficiently by linear programming (LP) or auction algorithms. We contribute two novel modifications to the literature. For LP, we introduce a formulation that simultaneously inverts multiple demand maps. Moreover, we augment both the LP and auction algorithms to compute lattice bounds for the identified utility set $\tilde\sigma^{-1}$.
For the large but finite discretization described above, the linear program ((ref)) becomes
which coincides with the dual of Shapley and Shubik's shapley1971assignment classic assignment game. While Shapley and Shubik showed that the set of optimizers in ((ref)) is a lattice, with bounds equal to the consumer-optimal and yogurt-optimal payoffs, they did not discuss how to compute these bounds. In principle, the upper (resp. lower) bounds can be obtained from the following problem: $$ \underset{u,\delta,\pi}{\max} \ \text{(resp. $\underset{u,\delta,\pi}{\min}$)} \sum_{j=0}^J\delta_j\quad \text{s.t. $(u,\delta)\in \left\{\text{arginf}\ (\ref{eq: LP})\right\}$.} $$ This is a “bilevel” program, as the solutions to the LP in ((ref)) are used as the inputs into a second LP.\footnote{See \citeasnoun{Book_Bilevel_Program}.} As is well-known, we can collapse a bilevel LP into a regular LP by replacing the lower-level LP (corresponding to ((ref))) with its optimality conditions. That is, the upper (resp. lower) bounds can be obtained from the following LP:
Constraints 1-3 in ((ref)) are the constraints of the primal assignment game ((ref)), whereas constraint 4 appears in the dual problem ((ref)). Constraint 5 equates the primal and dual objectives at the optimum. Taken together, these 5 constraints characterize the optimizing $(u,\delta)$ from ((ref)).\footnote{See, for instance, \citeasnoun{Mangasarian1969}.} Constraint 6 is our maintained normalization.
{ Combining LP problems.} A further benefit of the LP approach is that multiple demand inversion problems for different markets can be {\em combined} and solved simultaneously. Specifically, suppose there are $m=1,\dots,M$ markets. Instead of solving Problem ((ref)) for each of the $M$ markets separately, we combine these $M$ problems into one problem to invert {\em all} demand maps simultaneously:
where all of the subscripts are augmented by the market index $m$. Since the decision variables $(u_{mi},\delta_{mj})$ and the associated constraints are market-specific, the resulting constraint coefficient matrix has a block-diagonal structure, which enables the use of efficient parallel sparse matrix routines for modern LP solvers. We utilize this simultaneous demand inversion approach in the empirical application below, and confirm how one large but sparse problem (involving a larger number of parameters and constraints) is solved much more quickly than $M$ small problems.
Auction-type algorithms \`{a} la \citeasnoun{bertsekas1992auction} provide an alternative approach to linear programming methods for solving TU-matching models. In these algorithms, unassigned persons bid simultaneously for objects, decreasing their systematic utilities (or equivalently raising their prices). Once all bids are in, objects are assigned to the highest bidder. The procedure is iterated until no one is unassigned. The description here follows \citeasnoun{bertsekas1989auction}. We let $\kappa\in\left\{1,\ldots,N\right\}$ index jars of yogurt, where $j(\kappa)\in\mathcal{J}_0$ denotes the brand identity for the $\kappa$-th jar of yogurt.
We define the prices $p_{\kappa}$ as negative systematic utilities: $p_{\kappa} = -\delta_{\kappa}$.
Intuitively, the algorithm implements a Walrasian-style bidding procedure. In each round, each unassigned consumer bids for his favorite jar of yogurt. His bid (Eq. ((ref))) is equal to the difference between the utilities from his most-preferred and second-most-preferred brands of yogurt (plus an extra $\eta>0$ factor to ensure that prices are increasing each round). The consumer which makes the highest bid for a jar is assigned to it, and its price is increased by the amount of the bid; a consumer previously assigned to this jar becomes unassigned and bids in the next round. The algorithms stops when all individuals are assigned. The performance of the algorithm is considerably improved by applying it several times, starting with a large value of $\eta$ and gradually decreasing it.
{\em Computing utility bounds.} The auction algorithm as described above works for the case when the demand map is invertible (so that the identified set of utilities is a singleton). In practice, we do not know {\em a priori} whether the demand map is invertible or not; hence, we must extend the algorithm to allow for multiplicity of solutions. To do this, we note that the auction algorithm described above returns the optimal allocation $\pi_{ij}$ (for $i=1,\ldots, N$ and $j\in\mathcal{J}_0$) which is equal to one if consumer $i$ matches with a jar of yogurt brand $j$, and zero otherwise. In principle the utility bounds could be solved from the earlier linear programming problem ((ref)), with the matching indicators $\pi_{ij}$ fixed at the optimal allocation. However, that would be inefficient as it doesn't fully exploit our knowledge of the optimal allocation. Here we present a simpler alternative which is much quicker as it converges monotonically to the bounds of $\delta$.
{For the problem ((ref)), given the optimal allocation $\left\{ \pi_{ij}\right\}_{i,j}$, the solutions $(u,\delta)$ satisfy the inequalities $$u_{i}\geq \mathcal{U}_{\varepsilon _{i}j}(\delta _{j})\equiv \delta_j+\varepsilon_{ij}\ \forall i,j; \quad \text{ with equality for $\pi _{ij}>0$}.$$ Accordingly, we construct an operator $T : \mathbb{R}^{\mathcal{I} \cup \mathcal{J} } \to\ \mathbb{R}^{\mathcal{I} \cup \mathcal{J} }$ given by
The set of fixed points of this operator $u_i = T_i(u,\delta),\delta_j = T_j(u,\delta)$ satisfy the inequalities above. To see this, notice $\max (u_{i},\max_{j\in \mathcal{J}_{0}}(\mathcal{U}_{\varepsilon _{i}j}(\delta _{j})))=u_{i}$ if and only if $u_{i}\geq \mathcal{U}_{\varepsilon _{i}j}(\delta _{j})$ for all $j\in \mathcal{J}_{0}$. Similarly, $\max (\delta _{j},\max_{i:\pi _{ij}>0} \mathcal{U}_{\varepsilon _{i}j}^{-1}(u_{i}))=\delta _{j}$ holds if and only if $\delta _{j}\geq \max_{i:\pi _{ij}>0}\mathcal{U}_{\varepsilon_{i}j}^{-1}(u_{i})$ $\Leftrightarrow$ $u_{i}\leq \mathcal{U}_{\varepsilon _{i}j}(\delta_{j})$) for all $i$ such that $\pi _{ij}>0$. Combining these, we obtain that the fixed point satisfies $u_{i}=\mathcal{U}_{\varepsilon _{i}j}(\delta _{j})$ for all $i,j$ for which $\pi _{ij}>0$. } Hence, by iterating on ((ref)) beginning from the initial lowest possible values $\left\{u_i = -\infty;\ \delta_j = -\infty,\ j \neq 0;\ \delta_0 = 0\right\}$, we will obtain a non-decreasing sequence of $\delta$'s converging to $\underline{\delta}$.
Analogously, starting with values of $+\infty $ and iterating on the following operator we will obtain a monotonic non-increasing sequence of $\delta$'s converging to the upper bounds $\bar\delta$:
{ Indeed, $\delta _{j}=\min (\delta _{j},\min_{i\in \mathcal{I}}\mathcal{U} _{\varepsilon _{i}j}^{-1}(u_{i}))$ holds if and only if $\delta _{j}\leq \min_{i\in \mathcal{I}}\mathcal{U}_{\varepsilon _{i}j}^{-1}(u_{i})$ $\Leftrightarrow$ $\mathcal{U}_{\varepsilon _{i}j}\left( \delta _{j}\right) \leq u_{i}$, for all $i\in \mathcal{I}$. Similarly, $u_{i}=\min (u_{i},\min_{j:\pi _{ij}>0}(\mathcal{U}_{\varepsilon _{i}j}(\delta _{j}))$ holds if and only if $u_{i}\leq \min_{j:\pi _{ij}>0}(\mathcal{U} _{\varepsilon _{i}j}(\delta _{j}))$ $\Leftrightarrow$ $u_{i}\leq \mathcal{U}_{\varepsilon _{i}j}(\delta _{j})$, for all $j$ such that $ \pi _{ij}>0$.}\footnote{The iterations over the isotone operators ((ref)) and ((ref)) are instances of the {\em Bellman-Ford algorithm}, used for solving certain types of network flow problems, cf. \citeasnoun{sedgewick2011algorithms}.}
We have developed R packages containing fast and efficient implementations of the algorithms described in this section. They are designed to enable user-friendly access for researchers to popular matching methods, and are used in the next section to benchmark the relative performance of each algorithm. \citeasnoun{github_auction} collects several auction and linear programming algorithms into an R package, utilizing C++ code provided by \citeasnoun{walsh2017general}. Finally, a parallelized implementation of the MSA is contained in a separate package \citeasnoun{github_yogurts}. Links to the packages and installation instructions are provided in the bibliography references.
We test our algorithms on two different models: the first one is the additive pure characteristics model, and the second one is a special case of a pure characteristics model which is {\em not} invertible, so that multiple values of utilities are consistent with a set of market shares.\footnote{While it is beyond the scope of this paper to consider formal statistical testing of equivalence between the bounds $\delta_{\min}=\delta_{max}$, in all our computational and empirical results below we computed the upper and lower bounds for different and increasing values of $N$, to ensure that any distance between $\delta_{min}$ and $\delta_{max}$ is not driven by approximation error due to small $N$.}
In this section we evaluate the performance of our matching-based algorithms in computing the pure characteristics model. \citeasnoun{berry2007pure} (p. 1193) underline that this model is appealing on theoretical grounds,\footnote{Models with logit errors have properties that may be undesirable for welfare analysis: They restrain substitution patterns and utility grows without bounds as the number of products in the market grows. See \citeasnoun{berry2007pure} and \citeasnoun{ackerberg2005unobserved}.} but it is infrequently used in empirical work, arguably due to the computational challenges associated with the non-smooth demand map.
We consider the following specification, which is adapted from \citeasnoun{dube2012improving}: The utility of consumer $i$ who chooses product $j$ in market $m$ is generated by:
where $x_{mjk}, k=1,2,3$ are observed, exogenous product attributes, and $p_{mj}$ is the price of product $j$ in market $m$ that is correlated with the unobserved product attribute $\xi_{mj}$. {Instruments are constructed as noisy nonlinear functions of the exogenous $x$'s. The random coefficients are $(\beta_p,\beta_1,\beta_2,\beta_3)$, distributed independently from normal distributions with means equal to $\bar\beta_p, \bar\beta_1,\bar\beta_2,\bar\beta_3$ and unit variances. Following \citeasnoun{berry2007pure}, the mean price coefficient $\bar\beta_p$ is normalized to -1. Additional details on the simulation setup and implementation are provided in Appendix (ref).
We compare and contrast the performance of several algorithms. Our algorithm, which we call “Matching-LP”, takes the form of a nested iterative procedure a la BLP (\citeasnoun{berry1995automobile}): that is, the procedure alternates between an outer and inner loop. In the outer loop, a GMM objective function is optimized with respect to the model parameters, while the inner loop performs the demand inversion to recover the mean utilities ($\delta$) at the current candidate values of the model parameters. In the inner loop, we utilize the linear programming (LP) algorithm from Section (ref) to perform the demand inversion.}
To benchmark performance, we compare our “Matching-LP” approach to two alternatives from the literature which reflect the current thinking on estimating the pure characteristics model. The first, denoted “BLP-MPEC”, comes from \citeasnoun{berry2007pure}, who suggest smoothing out the non-smooth pure characteristics demand map by adding small logit errors to each alternative, and then using the BLP estimation procedure.\footnote{In implementation, we utilize Dub\'{e}, Fox, and Su's (2012) MPEC algorithm, which has demonstrated speed advantages over nested methods. This speed advantage of MPEC arises in part from the use of Newton-type (gradient-based) iterations in the optimization procedure. As \citeasnoun{LeeSeo2016} point out, Newton iterations have speed gains relative to BLP's original algorithm, which utilizes contraction mapping iterations.} {The second alternative, denoted “PSL”, is the algorithm proposed in \citeasnoun{pang2015constructive} based on reformulating the model as a linear complementarity problem.}
In Table (ref), we report the RMSE, bias, proportion of runs converged, and the average runtime across 20 Monte Carlo repetitions. There are 100 markets and 5 products (including the outside goods). In our simulations, we consider discretizations of the market into both $N=500$ and $N=1000$ agents on each side of the market. We consider two model specifications: In Model I, we estimate the location parameters and fix all scale parameters. In Model II, we estimate the location parameter and the scale parameter associated with the endogenous price, fixing the rest of the scale parameters.
In Model I, Matching-LP and PSL have similar RMSE, which is roughly half of that of BLP-MPEC. In Model II, Matching-LP clearly dominates the other two alternatives: particularly, it delivers nearly an unbiased estimate for the standard deviation of the random coefficient of price ($\sigma_p$), while the other two approaches falter. In terms of computational speed, our method is on average 130 times faster than PSL and 26 times faster than BLP-MPEC in Model I. In model II, our method outperforms PSL by a factor of 7 and outperform BLP-MPEC by a factor of 2. These simulations demonstrate the superior performance of the matching-based approach for estimating the pure characteristics model.
While all three algorithms require random draws by simulating $N$ consumers from the distribution of the random coefficients, there is a fundamental difference in how these algorithms utilize the random draws. Both our matching-based approach and PSL use the random draws to discretize the distribution, whereas the traditional BLP approach averages over the random draws to approximate the market shares. Since simulation can potentially create bias, it is importantly to investigate the relationship between the simulation errors and the number of draws. By comparing Panel I and Panel II of Table (ref), we find that increasing the number of draws noticeably improves the RMSE of both our matching-based algorithm as well as PSL. For BLP-MPEC, however, there is little noticeable improvement.
As a supplementary exercise, we hone in on the performance of our matching algorithm in the demand inversion step itself, and compare the numerical accuracy of our matching-based algorithms to alternative existing approaches. Table (ref) summarizes the numerical performance of three matching-based algorithms: (i) LP, (ii) Auction, and (iii) MSA; the (iv) BLP contraction mapping (which adds logit errors to the utilities of each choice to smooth the demand map) is also included as a benchmark.\footnote{In our simulations we use the most common version of the BLP-contraction mapping algorithm, which utilizes iterations based on successive approximations. \citeasnoun{LeeSeo2016} show that the performance of the algorithm can be improved by utilizing Newton iterations instead. However, both approaches require smoothness in the market-share mapping, which is not satisfied in the pure characteristics model considered here.}
The numerical accuracy is almost identical across all three matching algorithms (LP, Auction, MSA). In comparison, the RMSE of the BLP contraction mapping is about three times larger. Similar to the finding in Table (ref), we find that increasing the number of draws $N$ improves the RMSE of our matching algorithms but not the BLP contraction mapping -- this arises from the additional approximation error due to the introduction of additive logit errors to smooth the mapping.
For computational speed, the auction algorithm is the fastest by a wide margin: even under the most demanding scenario (500 brands and 10,000 simulated consumers), it only takes 5 seconds, which far outstrips other approaches.\footnote{{The computational speed reported in Table (ref) and (ref) are not directly comparable for several reasons: First, Table (ref) only measures the computational time in the demand-inversion step\textemdash the “inner loop” in Table (ref). Second, in Table (ref), the differences between NFXP and MPEC for searching the structural parameters can contribute to the performance difference. Third, in Table (ref), there are 100 markets, whereas in Table (ref), there is only one market. The scalability of different demand-inversion methods also affects the overall computational speed.}}
On the other hand, while MSA is the slowest algorithm, and does not scale up well with the number of brands, it is a general-purpose algorithm that also applies to NARUMs.\footnote{Interestingly, with 5 brands, MSA is faster with 10,000 draws than with 1,000: this may appear counter-intuitive, but increasing the number of draws improves accuracy during the loop and therefore reduces total computation times.} It is therefore not surprising that MSA is not as fast as the other methods since it does not exploit the additive separability in ARUMs.
{For the second simulation exercise, we consider a pure characteristics model which is non-invertible\textemdash that is, there are multiple utility vectors which rationalizes the same set of market shares. It underscores an important contribution of our approach, namely its ability to handle models which are not invertible. Moreover, it also suggests that non-invertibility may be a typical feature of the pure characteristics model. \citeasnoun[pg. 654]{pang2015constructive} likewise note a problem of multiple solutions in results from their estimation procedure for pure characteristics models.
There are three goods $y=1,2,3$, and the unknown parameters are the quality of each good are $\delta_1,\delta_2,\delta_3$, with the normalization $\delta_1=0< \delta_2,\delta_3$. Consumers fall into two segments, which differ in the prices that they face. In segment 1, prices are given by the vector $\mathbf{p}_1$, with $p^1_1<p^1_2<p^1_3$, while in segment 2, prices are given by the vector $\mathbf{p}_2$, with $p^2_1\leq p^2_3<p^2_2$. The utility function is given by $$\mathcal{U}_{\varepsilon j}(\delta_j)=\delta_j - \frac{\varepsilon^b}{\varepsilon^a} p_j^1 + \frac{(1-\varepsilon^b)}{\varepsilon^a} p_j^2,$$ which is a pure characteristics specification. Consumer heterogeneity $\varepsilon\equiv (\varepsilon^a, \varepsilon^b)$ consists of both $\varepsilon^a\sim U[0,1]$, interpreted as willingness-to-pay for quality, and $\varepsilon^b$, an indicator for whether they are in the first segment, which equals 0 or 1 with equal probability.}
Let $s^d_j$ denote the (unobserved) market share of good $j$ among segment $d (\in \left\{ 1,2\right\})$ customers. The observed market shares are mixtures of market shares across both customer segments:
This example typifies a common problem in supermarket scanner datasets, that consumers' transactions prices often differ markedly by products' list prices.\footnote{See \citeasnoun{erdem1998missing} for detailed discussions and modelling approaches to this problem.} In this case, the segment 1 prices $\mathbf{p^1}$ are analogous to "list" prices (ie., the prices posted on the supermarket shelves) while segment 2 customers have a coupon which gives them a discount on good 3.
In the simulation exercise, we set $p^1_1=1$, $p^1_2=2$, and $p^1_3=3$ be the prices in segment 1, and $ p^2_1=1$, $p^2_2=2$, and $p^2_3=1$ in segment 2. The observed market shares are given by $(s_1,s_2,s_3)=(0.25,0.25,0.5)$. Given $ \delta_1=0$, the identified utility set contains multiple values of the quality parameters $(\delta_2,\delta_3)$:
which is a lattice with minimal element $(0,2,1)$ and maximal element $(0,2,3)$.
Computational results using the LP algorithm are given in Table (ref). The algorithm performs as expected; utilizing the linear programming algorithm ((ref)) along with the supplemental program to compute the upper and lower bound of payoffs ((ref)) accurately recovers the upper and lower bounds. For comparison, we also performed the demand inversion exercise using the BLP contraction mapping approach, which requires the demand inverse to be unique. Not surprisingly, we found that the contraction mapping algorithm would not converge for this problem.\footnote{On each trial run, the maximum number of function evaluations was reached without convergence.}
To continue, we consider an expanded version of this model involving 5 segments, and 8 goods. The prices and market shares for this example are given in Table (ref). Since, these market shares were chosen arbitrarily, we do not know a priori whether the identified utility set $\tilde\sigma^{-1}(s)$ is a singleton or contains multiple values.\footnote{ That is, unlike the two-segment example used in Table (ref), we did not start by computing a market equilibrium for given parameter values. Rather we chose the prices and market shares in Table (ref) arbitrarily, and use our approach to determine $\tilde\sigma^{-1}$.}
In the two right-most columns of Table (ref), we report the recovered upper and lower bounds for the $\delta$'s. Clearly, for all entries, the lower and upper bounds coincide at the second or third decimal place, suggesting that the identified utility set $\tilde\sigma^{-1}$ is a singleton. The results here were computed using $N=50000$, a very large value to ensure that the results are not driven by approximation error. In Table (ref) in the appendix, we report results for different values of $N$, demonstrating that these results are robust and that, even with smaller values of $N$, the conclusions do not change.
Finally, we use our matching-based algorithm to estimate an aggregate spatial voting model using data from the 1999 Parliamentary Elections in the European Union countries, following \citeasnoun{MerloDePaula2017}.
We consider a spatial voting framework in which both voters and political parties are characterized by their “location” in the political spectrum, which is the Cartesian plane $\mathbb{R}^2$. Voter $i$ is characterized by her ideal point $t_i\in \mathbb{R}^2$ within this space; likewise, candidate (political party) $j$ has an ideological position $C_j\equiv (C_{j1}, C_{j2})\in \mathbb{R}^2$.
Voters are ideological: voter $i$ from electoral precinct $m$ votes for the party with the platform closest to her ideal point $t_{mi}$. Specifically, her preferred party is:
where $d(,)$: $\mathbb{R}^2\rightarrow \mathbb{R}_{+}$ is the distance function, which is specified as a quadratic function:
$W$ is a $2\times 2$ weighting matrix, which for simplicity we assume to be identity: $W=\mathbb{I}_2$. (This is restrictive as it implies that voters weigh both dimensions of the political spectrum equally.) Unlike \citeasnoun{MerloDePaula2017} who consider the nonparametric identification and estimation of the distribution of voter ideal points $t$, we assume that they come from a bivariate normal distribution, as follows:
where $X_m=(x_{mk}$, $k=1,\dots,K)$, are aggregate demographic and economic variables in precinct $m$, and $\alpha$ and $\beta$ denote $K\times 1$ parameter vectors of interest.\footnote{As usual, we normalize the variance of $\nu_{mi1}$ to one. }
By substituting ((ref)) into ((ref)), the “disutility” that voter $i$ gets from voting for candidate $j$ becomes:
In the discrete-choice setting, only utility components which vary across candidates $j$ will affect choices. From the above, the terms $(\nu^2_{i1},\nu^2_{i2})$ and $(X_{m}'\alpha)\nu_{i1},(X_{m}'\beta)\nu_{i2}$ are individual-specific, and hence do not affect $i$'s choice problem. Therefore, our specification can be simplified into the following pure characteristics form:\footnote{\citeasnoun{MerloDePaula2017} also pointed out the equivalence of the spatial voting and pure characteristics models.}
The parameters in this specification are collectively denoted by $\theta\equiv \left( \alpha, \beta, \Sigma\right)$.
As we pointed out above, the computational difficulties of the pure characteristics model has hampered empirical work utilizing it; indeed, despite the theoretical importance of the spatial voting model in political economy (ever since the pioneering work by \citeasnoun{downs1957economic}), empirical specifications have been relatively sparse. Thus the application here, while primarily illustrative, does have a methodological contribution in showing how the matching-based algorithms introduced in this paper can be used to estimate a work-horse model from political science.
As data we use precinct-level vote shares from the 1999 European Parliament elections. Altogether we have voting data from 822 electoral precincts in 22 regions, which are typically countries but may be sub-national regions distinguished by different sets of political parties.\footnote{The 22 regions are: Austria, Finland, France, Germany, Greece, Italy-Center, Italy-Islands, Italy-Northeast, Italy-Northwest, Italy-South, Portugal, Spain, Sweden, Netherlands, UK-East Midlands, UK-Eastern, UK-London, UK-Northwest, UK-Southeast, UK-Southwest, UK-West Midlands, and UK-Yorkshire.} Parties' ideological positions are taken from \citeasnoun{HixNouryRoland2006}, who computed two ideological positions for each party: $C=(C_{j1}, C_{j2})$, with $C_{j1}$ denoting position on a left-right spectrum, and $C_{j2}$ denoting party's stance on the EU (with larger values denoting, resp. a more right-wing position and more pro-EU stance). We use $K=3$ precinct-specific socio-economic and demographic variables: the female-to-male ratio, the proportion of the population older than 35 years, and the unemployment rate.\footnote{\citeasnoun{MerloDePaula2017} include additionally GDP as a regressor, and hence exclude Austria and Italy from their analysis due to missing values of this variable.} All the data we use are available from the {\em Review of Economic Studies} website.\footnote{\url{https://doi.org/10.1093/restud/rdw046}}
As the quadratic spatial voting model is a pure characteristics model, we use our “Matching-LP” algorithm for estimation, which we also used for the simulations in Section 5.1.\footnote{We focus on the LP algorithm here in order to leverage combining and simultaneously solving the demand inversion problems across different precincts, which saves substantially on computational time. Other algorithms, including the auction algorithm, are not amenable to combining the demand inversion problems.} Essentially, this resembles the \citeasnoun{berry1995automobile} estimation algorithm except that the inner loop utilizes a matching-based algorithm in place of the contraction mapping in BLP. We describe the outer and inner loops in turn.
In each call to the inner loop, for a given parameter vector $\theta$, we solve the demand inversion problems across all precincts simultaneously (see the earlier discussion associated with Eq. ((ref))), by combining all the linear programs across all precincts into the following single large linear program:
Let $\left\{\hat\delta_{mj}(\theta)\right\}_{m,j}$ denote the optimized values of the $\delta_{mj}$'s from this problem.
For the outer loop, we minimize the least-square differences between the $\hat\delta_{mj}(\theta)$'s emerging from the inner loop and the functional form for $\delta_{mj}$, as implied in Eq. ((ref)), to estimate $\theta$:
Table (ref) contains our estimation results for two specifications.\footnote{For this ARUM, without loss of generality, we normalized $\delta_{m1}=0$, corresponding to the party listed first in alphabetical order in each precinct $m$. We implemented this normalization by subtracting, in each market, the covariates $C_{j1}^2 + C_{j2}^2- 2\left(C_{j1}*(X_m'\alpha)\right) - 2\left(C_{j2}*(X_m'\beta)\right)$ for candidate 1 from the utilities for the other candidates $j\neq 1$ (cf. Eq. ((ref))). The pure characteristics model also requires a location normalization (cf.\citeasnoun[footnote 13]{berry2007pure}) which is automatically satisfied as the spatial voting model implies that the constant term in the utility is equal to the squared ideological positions $C_{j1}^2+C_{j2}^2$ which is known by the researcher.} In Model I, we assume that the covariance matrix $\Sigma=\mathbb{I}_2$, thus ruling out correlation between the two ideal point dimensions conditional on precinct characteristics $X_m$. Model II eliminates this restriction and allows for correlation between the dimensions, so that $\Sigma=
$. The estimate for $\rho$ in Model II is negative (coef. -0.66) and significantly different from zero, implying that, after controlling for precinct-level characteristics, voters who are right-leaning (dimension 1) tend to be {\em less} in favorable towards the EU (dimension 2).\footnote{In comparison, the richer model in \citeasnoun{MerloDePaula2017} allows the correlation between voter dimensions to differ by country, and they estimate this correlation to be negative in 4 out of the 10 countries, including France and Germany, the two largest EU countries (cf. Table 3 in \citeasnoun{MerloDePaula2017}).} Given this result, we focus the discussion here to the results from Model II.
The estimated coefficients summarize the contribution of demographic variables on the two dimensions of voters' ideal points. For the first dimension, the coefficient on unemployment rate is negative (-1.76), indicating that left-leaning precincts tend to have higher unemployment rates. Precincts with larger female-to-male ratio tend to be more right-leaning (0.44), while there is no significant relation between age (measured by the proportion of population older than 35 years) on the tendency to be pro-conservative.
For the second dimension, we find that precincts with higher unemployment rate are significantly less supportive of the EU (coef. -1.25). Precincts with higher percentage of older voters are significantly more pro-EU, while those with a higher female-male ratio are less supportive of the EU. Altogether, economic considerations -- as exemplified in the unemployment rate -- appear to be the strongest and most consistent explanator of voters' preferences across European regions.
We also use our algorithms to check whether the demand map is invertible by solving for the upper and lower bounds on the precinct/party qualities $\delta_{mj}$ using the linear program in Eq. ((ref)). At the bottom of Table (ref), we report the maximal (across all precincts and parties) difference between the estimated upper and lower bounds in the $\delta_{mj}$'s, evaluated at the parameter values reported in Table (ref). As is evident, the difference is minuscule, suggesting that multiplicity of these parameters is not an issue for this model.\footnote{ With multiple $\delta$'s, the identification and estimation of the structural parameters (the $\beta$'s and the parameters in the distribution of random coefficients) is an open question, and we do not consider it here. Estimating these parameters typically relies upon instruments, and the associated moment conditions. The literature on identification and inference in moment condition models with possibly partially-identified parameters is still nascent; see \citeasnoun{chen2018monte} for one recent paper. In ongoing work (\citeasnoun{HsiehMonteroShum}) we are tackling this issue in the context of discrete-choice demand models as here, but both the issue regarding identification of $\beta$, as well as the computational and inferential issues associated with estimating $\beta$ in this setting are challenging. } Finally, the combined linear program in Eq. ((ref)) is a big time-saver, as executing the demand inversion problem {\em simultaneously} across all precincts is ten times faster than performing the demand inversion separately for each precinct. This suggests that simultaneous solution of demand inversion problems constitutes a very practical advantage of the linear programming approach.
In this paper we have explored the intimate connection between discrete choice models and two-sided matching models, and used results from the literature on matching under imperfectly transferable utility to derive procedures for demand inversion and estimation of discrete choice models based on the non-additive random utility specification. Although the microeconomics literature distinguishes between \textquotedblleft one-sided\textquotedblright\ and \textquotedblleft two-sided\textquotedblright\ demand problems, our results show that this distinction is immaterial for the purpose of estimating discrete-choice models. Given the matching equivalence, it is as appropriate to consider the discrete choice problem of consumers choosing yogurts as one in which \textquotedblleft yogurts choose consumers\textquotedblright .
The connection between discrete choice and two-sided matching is a rich one, and we are exploring additional implications. For instance, the phenomenon of \textquotedblleft multiple discrete choice\textquotedblright\ (consumers who choose more than one brand, or choose bundles of products on a purchase occasion) is challenging and difficult to model in the discrete choice framework\footnote{ See \citeasnoun{hendel1999estimating}, \citeasnoun{dube2004multiple}, \citeasnoun{fox2013measuring} for some applications.} but is quite natural in the matching context, where \textquotedblleft one-to-many\textquotedblright\ markets are commonplace -- perhaps the most prominent and well-studied being the National Residents Matching Program for aspiring doctors in the United States (cf. \citeasnoun{roth1984evolution}). We are exploring this connection in ongoing work.