The exact contents of citations.db main_text.text for this paper — one flattened LaTeX string, title through conclusion, appendix excluded, unmodified except for removing email addresses. This is what our citation measures are computed over.
59,985 characters
Structural Estimation of Matching Markets with Transferable Utility
\title{{\bf Structural Estimation of Matching Markets with Transferable Utility}\footnote{This paper is to be published by Cambridge University Press in the volume \emph{Online and Matching-Based Market Design} edited by Federico Echenique,
Nicole Immorlica, and Vijay Vazirani (2022). This arxiv version is not for distribution or use in derivative works. We thank Nikhil Agarwal and Paulo Somaini for their comments and Gabriele Buontempo for superb research assistance.}}
\author{Alfred Galichon\footnote{New York University and Sciences Po. Support from ERC grant EQUIPRICE No. 866274 is acknowledged.} \and Bernard Salani\'e\footnote{Columbia University.}}
\date{\today }
\maketitle
\label{ch:structuraltumodels}
In matching models with transferable utility, the partners in a match
agree to transact in exchange of a transfer of num\'eraire (utility or money) from one side of the match to the other. While transfers may be non zero-sum (if for instance there is diminishing marginal utility, frictions, or other costs) or constrained, we focus in this chapter on the simplest case of \textit{perfectly transferable utility}\index{perfectly transferable utility}, in which the transfers are unlimited and zero-sum: the transfer agreed to by one partner is fully appropriated by the other side.
For simplicity, we also limit our discussion to the one-to-one bipartite
model: each match consists of two partners, drawn from two separate
subpopulations. The paradigmatic example is the
\textit{heterosexual marriage
market}\index{Heterosexual marriage market}, in which the two subpopulations are
men and women. We will use these terms for concreteness.
With perfectly transferable utility, the main object of interest is the \textit{joint surplus function}\index{Joint surplus function}. It maps the characteristics of a man and a woman into the surplus utility created by their match, relative to the sum of the utilities they would achieve by staying single. Knowing the joint surplus function is informative about the preferences of the partners, and about their interaction within the match. It also opens the door to counterfactual analysis, for instance of the impact of policy changes.
We assume that the analyst observes a discrete set of characteristics
for each individual: their education, their age, their income category, etc.
Each combination of the values of these characteristics defines a \emph{type}. In any real-world
application, men and women of a given observed type will also vary in their
preferences and more generally in their ability to create joint surplus in
any match. We will assume that all market participants observe this additional variation, so that it contributes in determining the observed matching. On the other hand, by definition it constitutes \textit{unobserved heterogeneity}\index{Unobserved heterogeneity} for the analyst. The main challenge in this field is to recover the parameters of the joint surplus function without restricting too much this two-sided unobserved heterogeneity.
Matching with transferable utility solves a linear programming problem. In
recent years it has been analyzed with the methods of \textit{optimal
transport}\index{Optimal transport}. Under an additional \textquotedblleft
\textit{separability}\index{Separability}\textquotedblright\ assumption, most functions of interest are
convex; then \textit{convex duality}\index{Convex duality} gives a simple and transparent path to
identification\textit{identification}\index{Identification} of the parameters of these models\footnote{
We collected the elements of convex analysis used in this chapter in
Appendix~A.}. The empirical implementation is especially straightforward when
the unobserved heterogeneity has a \textit{logit}\index{Logit} form and the joint
surplus is linear in the parameters. Then the parameters can be estimated by
minimizing a globally convex objective function.
Section~\ref{ch:structuraltumodels:sec:unobsh} introduces separable matching models. Section~\ref{ch:structuraltumodels:sec:ident} presents assumptions under which data on ``who matches whom'' (the \textit{matching patterns}\index{Matching patterns}) identifies the parameters of the joint surplus function, and possibly also of the distributions of unobserved heterogeneity. We will also show how these parameters can be estimated (Section~\ref{ch:structuraltumodels:sec:estimation}), and how to compute the stable matchings for given parameter values (Section~\ref{ch:structuraltumodels:sec:computation}).
\medskip
\textbf{Notation}. We use bold letters for vectors and matrices. For any doubly-indexed variable
$\bm{z}=(z_{ab})$, we use the notation $\bm{z}_{a\cdot }$ to denote the vector of values
of $z_{ab}$ when $b$ varies; and we use a similar notation for $\bm{z}_{\cdot b}$.
\section{Matching with unobserved heterogeneity}\label{ch:structuraltumodels:sec:unobsh}
\subsection{Population and preferences}
We consider a population of men indexed by $i$ and a population of women indexed by $j$. Each match must consist of one man and one woman; and individuals may remain single.
If a man $i$ and a woman $j$ match, the assumption of
\textit{perfectly transferable utility}\index{Perfectly transferable utility} implies that their respective utilities can
be written as
\begin{align*}
& {\Greekmath 010B} _{ij}+t_{ij} \\
& {\Greekmath 010D} _{ij}-t_{ij}
\end{align*}
where $t_{ij}$ is the (possibly negative) transfer from $j$ to $i$\footnote{If $t_{ij}$ is negative, it should be interpreted as a transfer of $-t_{ij}$ from $i$ to $j$. Also, $t_{i0}=t_{0j}=0$}. Transfers can take all values on the real line, and are costless. We assume that each individual knows the equilibrium values
of the transfers for all matches that (s)he may take part in, as well as his/her pre-transfer utility ${\Greekmath 010B}_{i\cdot}$ or ${\Greekmath 010D}_{\cdot j}$.
One key feature of markets with perfectly transferable utility is that matching patterns do not depend on $\bm{{\Greekmath 010B}}$ and $\bm{{\Greekmath 010D}}$ separately, but only on their sums, which we call the \textit{{\em joint surplus}}\index{Joint surplus}\footnote{Strictly speaking, it only is a ``surplus'' when all ${\Greekmath 010B}_{i0}$ and ${\Greekmath 010D}_{0j}$ are zero. We follow common usage here.}.
\begin{definition}[Joint Surplus]\label{ch:structuraltumodels:def:jointsurp}
The joint surplus of a match is the sum of (pre- or post-transfers) utilities:
\[
\tilde{\Phi}_{ij} = ({\Greekmath 010B}_{ij}+t_{ij})+({\Greekmath 010D}_{ij}-t_{ij})={\Greekmath 010B}_{ij}+{\Greekmath 010D}_{ij}.
\]
We extend the definition to singles with $\tilde{\Phi}_{i0}={\Greekmath 010B}_{i0}$ and $\tilde{\Phi}_{0j}={\Greekmath 010D}_{0j}$.
\end{definition}
To see this, note that any change
\[
({\Greekmath 010B}_{ij}, {\Greekmath 010D}_{ij}) \to ({\Greekmath 010B}_{ij}-{\Greekmath 010E}, {\Greekmath 010D}_{ij}+{\Greekmath 010E})
\]
can be neutralized by adding ${\Greekmath 010E}$ to the transfer $t_{ij}$. This combined change leaves post-transfer utilities unchanged; therefore it does not affect the decisions of the market participants.
A {\em matching\/} is simply a set $\bm{d}$ of 0--1 variables $(d_{ij})$ such that $d_{ij}=1$ if and only if $i$ and $j$ are matched, along with 0--1 variables $d_{i0}$ (resp.\ $d_{0j}$) that equal~1 if and only if man $i$ (resp.\ woman $j$) is unmatched (single). It is {\em feasible\/} if no partner is matched more than once:
for all $i$, $\sum_j d_{ij} + d_{i0}=1$; and for all $j$, $\sum_i d_{ij}+d_{0j}=1$.
\subsection{Stability}\label{ch:structuraltumodels:sub:stabil}
Our notion of equilibrium is \textit{stability}\index{Stability}. Its definition in the context of models with perfectly transferable utility is as follows\footnote{It can be seen as a special case of the more general definition of stability.}.
\begin{definition}[Stability---primal definition]\label{ch:structuraltumodels:def:stability:ptu1}
A feasible matching is stable if and only if
\begin{itemize}
\item no match has a partner who would rather be single
\item no pair of currently unmatched partners would rather be matched.
\end{itemize}
\end{definition}
The first requirement translates into ${\Greekmath 010B}_{ij}-{\Greekmath 010B}_{i0}\leq t_{ij}\leq {\Greekmath 010D}_{ij}-{\Greekmath 010D}_{0j}$ for all matched $(i,j)$, that is if $d_{ij}=1$. The second one is easier to spell out if we define $u_i$ (resp.\ $v_j$) to be the post-transfer utility of man $i$ (resp.\ woman $j$) at the stable matching. Then we require that if $d_{ij}=0$, we cannot find a value of the transfer $t_{ij}$ that satisfies both ${\Greekmath 010B}_{ij}+t_{ij} > u_i$ and ${\Greekmath 010D}_{ij}-t_{ij} > v_j$. Obviously, this is equivalent to requiring that $\tilde{\Phi}_{ij} \leq u_i+v_j$. Note that if $d_{ij}=1$, then this inequality is binding since the joint surplus must be the sum of the post-transfer utilities. Moreover, the first requirement can be rewritten as $u_i \geq {\Greekmath 010B}_{i0}$ for all men and $v_j\geq {\Greekmath 010D}_{0j}$, with equality if man $i$ or woman $j$ is single.
We summarize this in an equivalent definition of \textit{stability}\index{Stability}.
\begin{definition}[Stability---dual definition]\label{ch:structuraltumodels:def:stability:ptu2}
A feasible matching $\bm{d}$ is stable if and only if the post-transfer utilities $u_i$ and $v_j$ satisfy
\begin{itemize}
\item for all $i$, $u_i \geq \tilde{\Phi}_{i0}$, with equality if $i$ is unmatched; and for all $j$, $v_j \geq \tilde{\Phi}_{0j}$, with equality if $j$ is unmatched
\item for all $i$ and $j$, $u_i + v_j \geq \tilde{\Phi}_{ij}$, with equality if $i$ and $j$ are matched.
\end{itemize}
\end{definition}
The conditions in Definition~\ref{ch:structuraltumodels:def:stability:ptu2} are exactly the \textit{Karush-Kuhn-Tucker optimality conditions}\index{Karush-Kuhn-Tucker optimality conditions} of the following maximization program:
\begin{eqnarray}
\max_{\bm{d}\geq 0}
&&\sum_{i, j} d_{ij} \tilde{\Phi}_{ij} +\sum_i d_{i0}\tilde{\Phi}_{i0}+
\sum_j d_{0j}\tilde{\Phi}_{0j} \nonumber\\
s.t.~ &&\sum_j d_{ij} +d_{i0}= 1\;\;\forall i \\
&&\sum_i d_{ij}+d_{0j}=1\;\;\forall j \; \; \; \; \label{ch:structuraltumodels:pgm:primal}
\end{eqnarray}
if $u_i$ and $v_j$ are the multipliers of the feasibility conditions. Thus the stable matchings maximize the total \textit{joint surplus}\index{Joint surplus} under the feasibility constraints. Program~\ref{ch:structuraltumodels:pgm:primal} above is called the \textit{{\em primal program}}\index{Primal program}. Since both the objective function and the constraints are linear, its {\em dual\/} has the same value. It minimizes the sum of the post-transfer utilities under the stability constraints
\begin{eqnarray}
\min_{(u_i), (v_j)}
&&\sum_i u_i +\sum_j v_j \nonumber\\
s.t.~ && u_i \geq \tilde{\Phi}_{i0}\;\;\forall i\nonumber\\
&& v_j \geq \tilde{\Phi}_{0j}\;\;\forall j\nonumber\\
&&u_i+v_j \geq \tilde{\Phi}_{ij}\;\;\forall i, j, \; \; \; \; \label{ch:structuraltumodels:pgm:dual}
\end{eqnarray}
and the multipliers of the constraints equal the $d_{i0}, d_{0j}, d_{ij}$ of the associated stable matching.
From an economic point of view, the linearity of these programs implies that since the feasibility set is never empty (one can always leave all men and women unmatched), there exists a stable matching, it is generically unique, and there always exists a stable matching $\bm{d}$ whose elements are all integers (zero or one). This paints a very different picture from matching with non-transferable utility.
\subsection{Separability}
A proper econometric setting requires that we distinguish carefully what the analyst can observe from
\textit{{\em unobserved heterogeneity}}\index{Unobserved heterogeneity}, which only the market participants observe. Most crucially, the analyst cannot observe all the
determinants of the pre-transfer utilities ${\Greekmath 010B}_{ij}$ and ${\Greekmath 010D}_{ij}$ generated by a
hypothetical match between a man $i$ and a woman $j$. A priori, they could
depend on interactions between characteristics the analyst observes, between these characteristics and unobserved
heterogeneity, and between the unobserved heterogeneity of both partners.
We now define observed characteristics as {\em types \/} $x\in \mathcal{X}$ for men, and $y\in \mathcal{Y}$ for women. These \textit{types}\index{Types} are observed by all market participants as well as the analyst.
There are $n_{x}$ men of type $x$ and $m_{y}$ women of type $y$. The set of
marital options that are offered to men and women is the set of types of
partners on the other side of the market, plus singlehood. We continue to use the
notation $0$ for singlehood and we define $\mathcal{X}_{0}=\mathcal{X}\cup
\{0\}$ and $\mathcal{Y}_{0}=\mathcal{Y}\cup \{0\}$ as the set of
options that are available to respectively women and men.
Men and women of a given type also have other characteristics which are not observed by the analyst. A man $i$ who has observed type $x$, or a woman $j$ who has observed type $y$, may be a more or less appealing partner in any number of ways. In so far as these characteristics are payoff-relevant, they contribute to determining who matches whom. We will assume in this chapter that contrary to the analyst, all participants observe these additional characteristics. To the analyst, they constitute {\em unobserved heterogeneity}. It is important to note that this distinction is data-driven: richer data converts \textit{unobserved heterogeneity}\index{Unobserved heterogeneity} into types.
Much of the literature has settled on excluding interactions between
unobserved characteristics, and this is the path we take here. We impose:
\begin{assumption}[Separability]\label{ch:structuraltumodels:assn:separ}
The joint surplus generated by a match between man $i$ with type $x$ and woman $j$ with type $y$ is
\begin{equation}
\label{ch:structuraltumodels:eq:separ}
\tilde{\Phi}_{ij} = \Phi_{xy} + {\Greekmath 0122}_{iy} + {\Greekmath 0111}_{jx}.
\end{equation}
The utility of
man $i$ and woman $j$ if unmatched are ${\Greekmath 0122} _{i0}$ and ${\Greekmath 0111} _{j0}$
respectively.
\end{assumption}
In the language of analysis of variance models, the \textit{separability}\index{Separability} assumption
rules out two-way interactions between unobserved characteristics,
conditional on observed \textit{types}\index{Types}. While this is restrictive, it still allows
for rich patterns of matching in equilibrium. For instance, all women may
like educated men, but those women who give a higher value to education are more likely
(everything equal) to marry a more educated man, provided that they in turn
have observed or unobserved characteristics that more educated men value
more.
Since the analyst can only observe types, we now redefine a matching as a collection $\bm{{\Greekmath 0116}}$ of non-negative numbers:
${\Greekmath 0116}_{xy}$ denotes the number of matches between men of type $x$ and
women of type $y$, which is determined in equilibrium and observed by the analyst. All men of type $x$,
and all women of type $y$, must be single or matched. This generates the
feasibility constraints:
\begin{align*}
N_{x}(\bm{{\Greekmath 0116}})& :=\sum_{y\in \mathcal{Y}}{\Greekmath 0116} _{xy}+{\Greekmath 0116} _{x0}=n_{x}\;\;\forall
x\in \mathcal{X} \\
M_{y}(\bm{{\Greekmath 0116}})& :=\sum_{x\in \mathcal{X}}{\Greekmath 0116} _{xy}+{\Greekmath 0116} _{0y}=m_{y}\;\;\forall
y\in \mathcal{Y}.
\end{align*}
In the following, we denote $x_i=x$ if man $i$ is of type $x$, and $y_j=y$ if woman $j$ is of type $y$.
\subsection{Equilibrium}
\textit{Convex duality}\index{Convex duality} will be the key to our approach to
\textit{identification}\index{Identification}. We start by rewriting the dual characterization of
the stable matching in~\eqref{ch:structuraltumodels:pgm:dual} as
\begin{eqnarray}
\min_{\substack{ u_{i}\geq {\Greekmath 0122}_{i0} \\ v_{j}\geq {\Greekmath 0111}_{j0}}}
&&\left(\sum_{i} u_i+\sum_{j} v_j\right) \label{ch:structuraltumodels:eq:dualgal} \\
s.t.~ &&u_{i}+v_{j}\geq \tilde{\Phi}_{ij} \; \; \forall i,j. \notag
\end{eqnarray}
Given Assumption~\ref{ch:structuraltumodels:assn:separ}, the constraint in~\eqref{ch:structuraltumodels:eq:dualgal} can
be rewritten as
\begin{equation}
(u_i -{\Greekmath 0122}_{iy})+(v_j -{\Greekmath 0111}_{jx}) \geq \Phi_{x_i y_j} \; \; \forall
i, j. \label{ch:structuraltumodels:eq:keysep}
\end{equation}
Define $U_{xy}=\min_{i: x_{i}=x}\left\{ u_{i}-{\Greekmath 0122} _{iy}\right\} $
and $V_{xy}=\min_{j: y_{j}=y}\left\{ v_{j}-{\Greekmath 0111} _{jx}\right\}$ for $x,y\neq 0$; and without loss of generality, set $U_{x0}=V_{0y}=0$ for $x,y>0$. The
constraint becomes
\begin{equation*}
U_{xy}+V_{xy} \geq \Phi_{xy} \; \; \forall x,y.
\end{equation*}
Moreover, by definition $u_i = \max_{y\in \mathcal{Y}_0}(U_{x_i
y}+{\Greekmath 0122}_{iy})$ and $v_j = \max_{x\in \mathcal{X}_0}(V_{x
y_j}+{\Greekmath 0111}_{jx})$, so that we can rewrite the \textit{dual program}\index{Dual program} as
\begin{eqnarray*}
\min_{\bm{U}, \bm{V}} &&\left(\sum_{i} \max_{y\in \mathcal{Y}_0}(U_{x_i
y}+{\Greekmath 0122}_{iy}) + \sum_j \max_{x\in \mathcal{X}_0}(V_{x
y_j}+{\Greekmath 0111}_{jx})\right) \\
s.t.~ &&U_{xy}+V_{xy}\geq \Phi _{xy} \; \; \forall x,y.
\end{eqnarray*}
Inspection of the objective function shows that the inequality constraint $U_{xy}+V_{xy}\geq
\Phi _{xy}$ can be replaced by an equality; indeed, if it were strict, one could weakly improve the objective function
while satisfying the constraint. Since this implies that $U_{xy}+V_{xy}=\Phi_{xy}$,
we can replace $V_{xy}$ with $
(\Phi_{xy}-U_{xy})$ to obtain a simple formula for the total \textit{joint surplus}\index{Joint surplus}:
\begin{equation}
\label{ch:structuraltumodels:eq:minmax}
\mathcal{W} =
\min_{\bm{U}} \left(\sum_i \max_{y\in \mathcal{Y}_0}(U_{x_i y}+{\Greekmath 0122}_{iy}) +
\sum_j \max_{x\in \mathcal{X}_0}(\Phi_{xy_j}-U_{x y_j}+{\Greekmath 0111}_{jx})\right).
\end{equation}
We just reduced the dimensionality of the problem from the number of
individuals in the market to the product of the numbers of their observed
types. Since the latter is typically orders of magnitude smaller than the
former, this is a drastic simplification. Assumption~\ref{ch:structuraltumodels:assn:separ} was
the key ingredient: without it, we would have an unobserved term ${\Greekmath 0118}_{ij}$ interacting
the unobservables in the joint surplus $\tilde{\Phi}_{ij}$ and~
\eqref{ch:structuraltumodels:eq:keysep} would lose its nice separable structure.
Moreover, the nested min-max in equation~\eqref{ch:structuraltumodels:eq:minmax} is not as complex as it seems. Consider the expression
\[
G_x(U_{x\cdot}):=
\frac{1}{n_x} \sum_{x_i = x} \max_{y\in \mathcal{Y}_0}(U_{x y}+{\Greekmath 0122}_{iy}).
\]
When the number of individuals $n_x$ tends to infinity, $G_x$ converges to the Emax operator, namely
\[
G_x(U_{x\cdot}):=
\mathbb{E} [ \max_{y\in \mathcal{Y}_0}(U_{x y}+{\Greekmath 0122}_{iy}) ].
\]
We shall assume from now on that this {\em large market limit\/} is a good approximation.
Since the maximum is taken over a collection of linear functions of $\bm{U}_{x\cdot}$, its value is a convex function, and so is $G_x$. Defining $H_y(\bm{V}_{\cdot y})$ similarly, we obtain
\begin{equation}
\label{ch:structuraltumodels:eq:WGH}
\mathcal{W} = \min_{\bm{U}} \left(G(\bm{U})+H(\bm{\Phi}-\bm{U})\right)
\end{equation}
where
\begin{align*}
G(\bm{U}) &:= \sum_{x\in \mathcal{X}} n_x G_x(\bm{U}_{x\cdot})\\
H(\bm{V}) &:= \sum_{y\in \mathcal{Y}} m_y H_y(\bm{V}_{\cdot y}).
\end{align*}
These functions play a special role in our analysis. Since $G$ is convex, it has a subgradient everywhere, which is a singleton almost everywhere. It is easy to see that the derivative of $\max_{y\in \mathcal{Y}_0}(U_{x y}+{\Greekmath 0122}_{iy})$ with respect to $U_{xy}$ equals~1 if $y$ achieves a strict maximum, and~0 if it is not a maximum. As a consequence, the subgradient of $G_x$ with respect to $U_{xy}$ is\footnote{Neglecting the measure zero cases where the subgradient is not a singleton.} the proportion of men of type $x$ whose match is of type $y$. We denote this proportion ${\Greekmath 0116}^M_{y\vert x}$. Finally, we note that the subgradient of $G$ with respect to $U_{xy}$ is $n_x$ times the subgradient of $G_x$, that is the number ${\Greekmath 0116}^M_{xy}$ . To conclude (and using similar definitions for $H$):
\begin{align*}
\bm{{\Greekmath 0116}}^M = \partial G(\bm{U})\\
\bm{{\Greekmath 0116}}^W = \partial H(\bm{V}).
\end{align*}
In equilibrium we must have ${\Greekmath 0116}^M_{xy}={\Greekmath 0116}^W_{xy}$ for all $x,y$. This should not come as a surprise as it translates the first-order conditions in~\eqref{ch:structuraltumodels:eq:WGH}:
\[
\partial G(\bm{U})\cap \partial H(\bm{\Phi}-\bm{U}) \neq \emptyset.
\]
\section{Identification}\label{ch:structuraltumodels:sec:ident}
Now let us denote $
G^{\ast }$ the \textit{Legendre-Fenchel transform}\index{Legendre-Fenchel transform} of the convex function $G$:
\begin{equation*}
G^{\ast }({\Greekmath 0116} )=\sup_{\bm{a}}\left( \sum
_{\substack{ x\in \mathcal{X} \\ y\in \mathcal{Y}}}
{\Greekmath 0116}_{xy}a_{xy}-G(a)\right) .
\end{equation*}
It is another convex function; and by the theory of
\textit{convex
duality}\index{convex duality} we know that since
\begin{equation*}
\bm{{\Greekmath 0116}}^{M}= \partial G(\bm{U}),
\end{equation*}
we also have $\bm{U} = G^{\ast }(\bm{{\Greekmath 0116}}^{M})$, that is
\begin{equation}
U_{xy} = \frac{\partial G^\ast}{\partial{\Greekmath 0116}_{xy}}(\bm{{\Greekmath 0116}}^{M}). \label{ch:structuraltumodels:eq:ident:x:types}
\end{equation}
Similarly,
\begin{equation}
V_{xy} = \frac{\partial H^\ast}{\partial{\Greekmath 0116}_{xy}}(\bm{{\Greekmath 0116}}^{W}). \label{ch:structuraltumodels:eq:ident:y:types}
\end{equation}
\subsection{Identifying the Joint Surplus}
In equilibrium, $\bm{{\Greekmath 0116}}^M=\bm{{\Greekmath 0116}}^W:=\bm{{\Greekmath 0116}}$ and $\bm{U}+\bm{V}=\bm{\Phi}$; therefore we obtain
\begin{equation}
\Phi_{xy} = \frac{\partial G^\ast}{\partial {\Greekmath 0116}_{xy}}(\bm{{\Greekmath 0116}})+\frac{\partial H^\ast}{\partial {\Greekmath 0116}_{xy}}(\bm{{\Greekmath 0116}}). \label{ch:structuraltumodels:eq:ident:Phi}
\end{equation}
Observing the matching patterns thus identifies
all values of $U_{xy}$, $V_{xy}$, and $\Phi_{xy}$, provided that we have enough information to evaluate the function $G$. Since the shape of the function $G$ only depends on the distribution of the \textit{unobserved heterogeneity}\index{Unobserved heterogeneity} terms, this is the piece of information we need.
\begin{assumption}[Distribution of the unobserved heterogeneity]\label{ch:structuraltumodels:assn:distrib_unobs}
For any man $i$ of type $x$, the random vector $\bm{{\Greekmath 0122}} _{i\cdot}={
({\Greekmath 0122} _{iy})}_{y\in \mathcal{Y}_{0}}$ is distributed according to $
\mathbb{P}_{x}$.
Similarly, for any woman $j$ of type $y$, the random vector
$\bm{{\Greekmath 0111}} _{j\cdot}={({\Greekmath 0111} _{jx})}_{x\in \mathcal{X}_{0}}$ is distributed according
to $\mathbb{Q}_{y}$.
\end{assumption}
Note that $\eqref{ch:structuraltumodels:eq:ident:Phi}$ is a system of $
\lvert\mathcal{X}\rvert\times \lvert\mathcal{Y}\rvert$ equations. To repeat, it
identifies the $\bm{\Phi}$ matrix in the joint surplus as a function of the
observed matching patterns $(\bm{{\Greekmath 0116}})$ and the shape of the functions $
G^{\ast }$ and $H^{\ast }$. The latter in turn only depend on the distributions $
\mathbb{P}_{x}$ and $\mathbb{Q}_{y}$. It is important to stress that the joint surplus is uniquely identified given any choice of these distributions. Identifying the distributions themselves requires more restrictions and/or more data.
\subsection{Generalized Entropy}
We already know from Section~\ref{ch:structuraltumodels:sub:stabil} that the stable matching maximizes the
total joint surplus. The corresponding \textit{primal program}\index{Primal program} is
\begin{equation}
\mathcal{W}(\bm{\Phi},\bm{n},\bm{m})=\max_{\bm{{\Greekmath 0116}} \geq 0}\left( \sum_{\substack{ x\in
\mathcal{X} \\ y\in \mathcal{Y}}}{\Greekmath 0116} _{xy}\Phi _{xy}-\mathcal{E}\left(\bm{{\Greekmath 0116}}; \bm{n},\bm{m}\right) \right) \label{ch:structuraltumodels:eq:primal:gal}
\end{equation}
where
\begin{equation*}
\mathcal{E}\left(\bm{{\Greekmath 0116}}; \bm{n},\bm{m}\right) =G^{\ast}\left(\bm{{\Greekmath 0116}}; \bm{n}\right) +H^{\ast
}\left(\bm{{\Greekmath 0116}},\bm{m}\right)
\end{equation*}
is the \textit{generalized entropy}\index{generalized entropy} of the matching $\bm{{\Greekmath 0116}}$. It is easy to check that the first-order
conditions in~\eqref{ch:structuraltumodels:eq:primal:gal} (which is globally concave) coincide
with the \textit{identification}\index{Identification} formula~\eqref{ch:structuraltumodels:eq:ident:Phi}.
The two parts of the objective function in~\eqref{ch:structuraltumodels:eq:primal:gal} have a
natural interpretation. The sum $\sum_{x,y}{\Greekmath 0116}_{xy}\Phi_{xy}$ reflects the
value of matching on observed \textit{types}\index{Types} only. The generalized entropy term $-
\mathcal{E}(\bm{{\Greekmath 0116}}; \bm{n},\bm{m})$ is the sum of the values that are generated by
matching unobserved heterogeneities with observed types: e.g.\ men of type $
x $ with a high value of ${\Greekmath 0122}_{iy}$ being more likely to match with
women of type $y$.
We skipped over an important technical issue: the
Legendre-Fenchel transform of $G_x$ is equal to $+\infty $ unless $
\sum_{y\in \mathcal{Y}}{\Greekmath 0116} _{xy}=N_x(\bm{{\Greekmath 0116}})-{\Greekmath 0116}_{x0}\leq n_{x}$. Therefore the
objective function in~\eqref{ch:structuraltumodels:eq:primal:gal} is minus infinity when any of
these feasibility constraints is violated.
There are two approaches for making the problem well-behaved. We can simply
add the constraints to the program. As it turns out, extending the
generalized entropy beyond its domain is sometimes a much better approach, as we will show in Section~\ref{ch:structuraltumodels:sec:estimation}.
\subsection{The Logit Model\label{ch:structuraltumodels:sub:mlogit}}
Following a long tradition in discrete choice models, much of the literature
has focused on the case when the distributions $\mathbb{P}_{x}$ and $\mathbb{
Q}_{y}$ are \textit{standard type~I extreme value (Gumbel)}\index{Gumbel distribution}. Under this
distributional assumption, the $G_{x}$ functions take a very simple and
familiar form:
\begin{equation*}
G_{x}(U_{x\cdot })=\log\left(1+\sum_{t\in \mathcal{Y}}\exp
(U_{xt})\right);
\end{equation*}
and the generalized entropy function $\mathcal{E}$ is just the usual
\textit{entropy}\index{Entropy}:
\begin{equation}
\mathcal{E}\left( \bm{{\Greekmath 0116}}; \bm{n}, \bm{m} \right) =2\sum_{\substack{ x\in \mathcal{X} \\
y\in \mathcal{Y}}}{\Greekmath 0116} _{xy}\log {\Greekmath 0116} _{xy}+\sum_{x\in \mathcal{X}}{\Greekmath 0116}
_{x0}\log {\Greekmath 0116} _{x0}+\sum_{y\in \mathcal{Y}}{\Greekmath 0116} _{0y}\log {\Greekmath 0116} _{0y}.
\label{ch:structuraltumodels:EisEntropy}
\end{equation}
Equation~\eqref{ch:structuraltumodels:eq:ident:Phi} can be rewritten to yield the following
\textit{matching function}\index{Matching function}, which links the numbers of
singles, the joint surplus, and the numbers of matches:
\begin{equation}
{\Greekmath 0116} _{xy}=\sqrt{{\Greekmath 0116} _{x0}{\Greekmath 0116} _{0y}}\exp \left( \frac{\Phi _{xy}}{2}\right).
\label{ch:structuraltumodels:eq:csmmf}
\end{equation}
In the \textit{logit}\index{Logit} model, the distributions $\mathbb{P}_x$ and $
\mathbb{Q}_y$ have no free parameter: the only unknown parameters in the
model are those that determine the joint surplus matrix $\Phi$. Using~
\eqref{ch:structuraltumodels:eq:csmmf} gives
\textit{Choo and Siow's formula}\index{Choo and Siow's formula}:
\begin{equation}
\Phi_{xy}=\log \frac{{\Greekmath 0116}_{xy}^{2}}{{\Greekmath 0116}_{x0}{\Greekmath 0116}_{0y}} \label{ch:structuraltumodels:eq:csident}
\end{equation}
\section{Estimation}\label{ch:structuraltumodels:sec:estimation}
In matching markets, the sample may be drawn from the population at the
individual level or at the match level. Take the marriage market as an
example. With individual sampling, each man or woman in the population would
be a sampling unit. In fact, household-based sampling is more common in
population surveys: when a household is sampled, data is collected on all of
its members. Some of these households consist of a single man or woman, and
others consist of a married couple. We assume here that sampling is at the
household level.
Recall that $\hat{{\Greekmath 0116}}_{xy}$, $\hat{{\Greekmath 0116}}_{x0}$ and $\hat{{\Greekmath 0116}}_{0y}$ are the
number of matches of type $(x,y)$, $(x,0)$ and $(0,y)$, respectively in our sample.
Denote
\begin{equation*}
N_{h}=\sum_{x\in \mathcal{X}}\hat{{\Greekmath 0116}}_{x0}+\sum_{y\in \mathcal{Y}}\hat{{\Greekmath 0116}}
_{0y}+\sum_{\substack{ x\in \mathcal{X} \\ y\in \mathcal{Y}}}\hat{{\Greekmath 0116}}_{xy}
\end{equation*}
the number of households in our sample, and let
\begin{equation*}
\hat{\bm{{\Greekmath 0119}}}_{xy}=\frac{\hat{{\Greekmath 0116}}_{xy}}{N_{h}},\hat{{\Greekmath 0119}}_{x0}=\frac{\hat{{\Greekmath 0116}}
_{x0}}{N_{h}}\relax\protect\ifmmode\expandafter\text@\else\expandafter\mbox\fi{ and }\hat{\bm{{\Greekmath 0119}}}_{0y}=\frac{\hat{{\Greekmath 0116}}_{0y}}{N_{h}}
\end{equation*}
the empirical sample frequencies of matches of type $(x,y)$, $(x,0)$ and $(0,y)$,
respectively. Let $\bm{{\Greekmath 0119}}$ be the population analog of $\hat{\bm{{\Greekmath 0119}}}$.
The estimators of the matching probabilities have an asymptotic distribution
\begin{equation}\label{ch:structuraltumodels:eq:Vpi}
\hat{\bm{{\Greekmath 0119}}}\sim \mathcal{N}\left( 0,\frac{\bm{V_{{\Greekmath 0119}}}}{N_{h}}\right).
\end{equation}
We seek to estimate a \textit{parametric model}\index{Parametric model} of the matching market. This involves specifying functional form for the matrix $\bm{\Phi}$ and choosing families of distributions for the \textit{unobserved heterogeneity}\index{Unobserved heterogeneity} $\mathbb{P}_x$ and $\mathbb{Q}_y$. We denote $\bm{{\Greekmath 0115}}$ the parameters of $\bm{\Phi}$, $\bm{{\Greekmath 010C}}$ the parameters of the distributions, and our aim is to estimate $\bm{{\Greekmath 0112}}=(\bm{{\Greekmath 0115}},\bm{{\Greekmath 010C}})$. Depending on the context, the analyst may choose to allocate more
parameters to the matrix $\Phi$ or to the distributions $\mathbb{P}_x$ and $
\mathbb{Q}_y$. We assume that the model is well-specified in that the data was generated by a matching market with true parameters $\bm{{\Greekmath 0112}}_0$.
We will assume in this section that the analyst is able to compute the stable matching $\bm{{\Greekmath 0116}}^{\bm{{\Greekmath 0112}}}$ for any value of the parameters $\bm{{\Greekmath 0112}}$. We provide several ways to do so efficiently in Section~\ref{ch:structuraltumodels:sec:computation}.
\subsection{The Maximum Likelihood Estimator}
In this setting, the log-likelihood function of the sample is simply the sum over all households of the log-probabilities of the observed matches. Let us fix the value of the parameters of the model at $\bm{{\Greekmath 0112}}$. We denote $\bm{{\Greekmath 0116}}^{\bm{{\Greekmath 0112}}}$ the equilibrium matching patterns for these values of the parameters and the observed margins $\bm{n}$ and $\bm{m}$.
A household may consist of a match between a man of type $x$ and a woman of type $y$, of a single man of type $x$, or of a single woman of type $y$. The corresponding probabilities are respectively ${\Greekmath 0116}^{\bm{{\Greekmath 0112}}}_{xy}/N_h^{\bm{{\Greekmath 0112}}}$, ${\Greekmath 0116}^{\bm{{\Greekmath 0112}}}_{x0}/N_h^{\bm{{\Greekmath 0112}}}$, and ${\Greekmath 0116}^{\bm{{\Greekmath 0112}}}_{0y}/N_h^{\bm{{\Greekmath 0112}}}$, where
\[
N_h^{\bm{{\Greekmath 0112}}}:= \sum_{x,y \in \mathcal{X}\times \mathcal{Y}} {\Greekmath 0116}^{\bm{{\Greekmath 0112}}}_{xy} + \sum_{x\in \mathcal{X}} {\Greekmath 0116}^{\bm{{\Greekmath 0112}}}_{x0}+\sum_{y \in\mathcal{Y}}{\Greekmath 0116}^{\bm{{\Greekmath 0112}}}_{0y}
\]
is the number of households in the stable matching for $\bm{{\Greekmath 0112}}$, which in general differs from $N_h$. The log-likelihood becomes
\begin{align*}\label{ch:structuraltumodels:eq:loglike}
\log L(\bm{{\Greekmath 0112}}) := \sum_{x,y \in \mathcal{X}\times \mathcal{Y}} \hat{{\Greekmath 0116}}_{xy} \log \frac{{\Greekmath 0116}^{\bm{{\Greekmath 0112}}}_{xy}}{N_h^{\bm{{\Greekmath 0112}}}} + \sum_{x\in \mathcal{X}} \hat{{\Greekmath 0116}}_{x0} \log \frac{{\Greekmath 0116}^{\bm{{\Greekmath 0112}}}_{x0}}{N_h^{\bm{{\Greekmath 0112}}}}
+\sum_{y\in \mathcal{Y}} \hat{{\Greekmath 0116}}_{0y} \log \frac{{\Greekmath 0116}^{\bm{{\Greekmath 0112}}}_{0y}}{N_h^{\bm{{\Greekmath 0112}}}}.
\end{align*}
Maximizing this expression gives a \textit{maximum likelihood estimator}\index{Maximum likelihood estimator} that has the usual asymptotic properties: it is consistent, asymptotically normal, and asymptotically efficient. The maximization process may not be easy, however. In particular, the function $\log L$ is unlikely to be globally concave, and it may have several local extrema. This may make other approaches more attractive.
\subsection{The Moment Matching Estimator}\label{ch:structuraltumodels:sub:momatch}
A natural choice of parameterization for $\bm{\Phi}^{\bm{{\Greekmath 0115}}}$ is the linear
expansion
\begin{equation*}
\Phi _{xy}^{\bm{{\Greekmath 0115}}}=\sum_{k=1}^{K}{\Greekmath 0115} _{k}{\Greekmath 011E}_{xy}^{k}
\end{equation*}
where the basis functions ${\Greekmath 011E} _{xy}^{k}$ are given and the ${\Greekmath 0115}_{k}$
coefficients are to be estimated.
The \textit{moment matching estimator}\index{Moment-matching estimator} uses the $K$ equalities
\[
\sum_{x,y} {\Greekmath 0116}^{\bm{{\Greekmath 0112}}}_{xy} {\Greekmath 011E}^k_{xy}= \sum_{x,y} \hat{{\Greekmath 0116}}_{xy} {\Greekmath 011E}^k_{xy}
\]
as its estimating equations. Both sides of these equalities can be interpreted as expected values of the basis function ${\Greekmath 011E}^k$; in this sense, the estimator matches the observed and simulated (first) moments of the basis functions. By construction, it can only identify $K$ parameters. We assume from now on that the values of the parameters of the distribution are fixed at $\bm{{\Greekmath 010C}}$, and we seek to estimate $\bm{{\Greekmath 0115}}$.
Applying the envelope theorem to equation~\eqref{ch:structuraltumodels:eq:primal:gal} shows that the derivative of the total joint surplus with respect to $\Phi_{xy}$ is the value of ${\Greekmath 0116}_{xy}$ for the corresponding stable matching. Using the chain rule, we obtain
\[
\frac{\partial \mathcal{W}^{\bm{{\Greekmath 010C}}}}{\partial{\Greekmath 0115}_k}(\bm{{\Greekmath 0116}}^{\bm{{\Greekmath 0112}}}, \hat{\bm{n}}, \hat{\bm{m}})= \sum_{x,y} {\Greekmath 0116}^{\bm{{\Greekmath 0112}}}_{xy}{\Greekmath 011E}^k_{xy};
\]
this allows us to rewrite the moment matching estimating equations as the first order conditions of
\begin{equation}\label{ch:structuraltumodels:eq:mom:match}
\max_{\bm{{\Greekmath 0115}}}\left(\sum_{x,y} \hat{{\Greekmath 0116}}_{xy}\Phi^{\bm{{\Greekmath 0115}}}_{xy}
-\mathcal{W}^{\bm{{\Greekmath 010C}}}(\bm{{\Greekmath 0116}}^{\bm{{\Greekmath 0112}}}, \hat{\bm{n}}, \hat{\bm{m}})\right).
\end{equation}
Note that the function $\mathcal{W}$ is convex in $\bm{\Phi}$. Since $\bm{\Phi}^{\bm{{\Greekmath 0115}}}$ is linear in $\bm{{\Greekmath 0115}}$, the objective function of~\eqref{ch:structuraltumodels:eq:mom:match} is globally convex. This is of course a very appealing property in a maximization problem.
We still have to evaluate $\mathcal{W}^{\bm{{\Greekmath 010C}}}(\bm{{\Greekmath 0116}}^{\bm{{\Greekmath 0112}}}, \hat{\bm{n}}, \hat{\bm{m}})=\sum_{x,y} {\Greekmath 0116}^{\bm{{\Greekmath 0112}}}_{xy} \Phi^{\bm{{\Greekmath 0115}}}_{xy} -\mathcal{E}^{\bm{{\Greekmath 010C}}}(\bm{{\Greekmath 0116}}^{\bm{{\Greekmath 0112}}}; \hat{\bm{n}}, \hat{\bm{m}})$. It is often possible to circumvent that step, however. To see this, remember that the \textit{generalized entropy}\index{Generalized entropy} is only defined when $\bm{N}(\bm{{\Greekmath 0116}})=\hat{\bm{n}}$ and $\bm{M}(\bm{{\Greekmath 0116}})=\hat{\bm{m}}$. Now take any real-valued functions $f$ and $g$ such that $f(0)=g(0)=0$, and consider the {\em extended entropy\/} function
\[
E^{\bm{{\Greekmath 010C}}}(\bm{{\Greekmath 0116}}; \hat{\bm{n}},\hat{\bm{m}}) = \mathcal{E}^{\bm{{\Greekmath 010C}}}(\bm{{\Greekmath 0116}}; \bm{N}(\bm{{\Greekmath 0116}}),\bm{M}(\bm{{\Greekmath 0116}}))
+f(\bm{N}(\bm{{\Greekmath 0116}})-\hat{\bm{n}})+g(\bm{M}(\bm{{\Greekmath 0116}})-\hat{\bm{m}}).
\]
By construction, this function is well-defined for any $\bm{{\Greekmath 0116}}$, and it coincides with $\mathcal{E}^{\bm{{\Greekmath 010C}}}$ when $\bm{N}(\bm{{\Greekmath 0116}})=\hat{\bm{n}}$ and $\bm{M}(\bm{{\Greekmath 0116}})=\hat{\bm{m}}$. Therefore we can rewrite~\eqref{ch:structuraltumodels:eq:primal:gal} as
\begin{eqnarray*}
\mathcal{W}^{\bm{{\Greekmath 010C}}}(\bm{\Phi},\bm{n},\bm{m})=\max_{\bm{{\Greekmath 0116}} \geq 0}\left( \sum_{\substack{ x\in
\mathcal{X} \\ y\in \mathcal{Y}}}{\Greekmath 0116} _{xy}\Phi _{xy}-E^{\bm{{\Greekmath 010C}}}\left(\bm{{\Greekmath 0116}}; \bm{n},\bm{m}\right) \right) \\
s.t \; \bm{N}(\bm{{\Greekmath 0116}})=\hat{\bm{n}} \; \mbox{ and } \; \bm{M}(\bm{{\Greekmath 0116}})=\hat{\bm{m}}.
\end{eqnarray*}
If moreover we choose $f$ and $g$ to be convex functions, this new program is also convex. As such, it has a dual formulation that can be written in terms
of the Legendre-Fenchel transform $(E^{\bm{{\Greekmath 010C}}})^\ast$ of $E^{\bm{{\Greekmath 010C}}}$. Simple
calculations show that the dual is:
\begin{equation*}
\mathcal{W}^{\bm{{\Greekmath 010C}}}\left(\bm{\Phi},\hat{\bm{n}},\hat{\bm{m}}\right) =\min_{\bm{u},\bm{v}\geq 0}\left(\langle\hat{\bm{n}},\bm{u}\rangle+
\langle\hat{\bm{m}},\bm{v}\rangle+(E^{\bm{{\Greekmath 010C}}})^\ast\left(\bm{\Phi} -\bm{u}-\bm{v},-\bm{u},-\bm{v}\right)\right)
\end{equation*}
where we denote $\bm{\Phi} -\bm{u}-\bm{v}={(\Phi _{xy}-u_{x}-v_{y})}_{x,y}$.
Returning to~\eqref{ch:structuraltumodels:eq:mom:match}, the program that defines the moment matching estimator can now be rewritten as follows:
\begin{equation}\label{ch:structuraltumodels:eq:mm:Estar}
\max_{\bm{{\Greekmath 0115}}, \bm{u}\geq 0, \bm{v}\geq 0}\left(\sum_{x,y} \hat{{\Greekmath 0116}}_{xy}\Phi^{\bm{{\Greekmath 0115}}}_{xy}
-\langle\hat{\bm{n}},\bm{u}\rangle
-\langle\hat{\bm{m}},\bm{v}\rangle-(E^{\bm{{\Greekmath 010C}}})^\ast\left(\bm{\Phi} -\bm{u}-\bm{v},-\bm{u},-\bm{v}\right)\right).
\end{equation}
This is still a globally convex program; and if we can choose $f$ and $g$ such that the extended entropy $(E^{\bm{{\Greekmath 010C}}})^\ast$ has a simple Legendre-Fenchel transform, it will serve as a computationally
attractive estimation procedure.
In addition to estimating the parameters $\bm{{\Greekmath 0115}}$ of the \textit{joint surplus}\index{Joint surplus}, it
directly yields estimates of the expected utilities $\bm{u}$ and $\bm{v}$ of each type. Moreover, after estimation the matching patterns can be obtained by:
\begin{equation}
\left\{
\begin{array}{c}
{\Greekmath 0116}^{\bm{{\Greekmath 0112}}} _{xy}=\frac{\partial (E^{\bm{{\Greekmath 010C}}})^\ast}{\partial z_{xy}}\left(\bm{\Phi}-\bm{u}-\bm{v},-\bm{u},-\bm{v}
\right) \\[3mm]
{\Greekmath 0116}^{\bm{{\Greekmath 0112}}} _{x0}=\frac{\partial (E^{\bm{{\Greekmath 010C}}})^\ast}{\partial z_{x0}}\left(\bm{\Phi}-\bm{u}-\bm{v},-\bm{u},-\bm{v}\right) \\[3mm]
{\Greekmath 0116}^{\bm{{\Greekmath 0112}}} _{0y}=\frac{\partial (E^{\bm{{\Greekmath 010C}}})^\ast}{\partial z_{0y}}\left(\bm{\Phi}-\bm{u}-\bm{v},-\bm{u},-\bm{v}\right)
\end{array}
\right. \label{ch:structuraltumodels:def_pi_theta}
\end{equation}
The logit model of Section~\ref{ch:structuraltumodels:sub:mlogit} provides an illustration of this approach.
\subsection{Estimating the Logit Model}\label{ch:structuraltumodels:sub:logitEstim}
Plugging in estimates $\hat{\bm{{\Greekmath 0116}}}$ of the matching patterns in formula~\eqref{ch:structuraltumodels:eq:csident}
gives a closed-form estimator $\hat{\bm{\Phi}}$ of the \textit{joint surplus}\index{Joint surplus} matrix in the \textit{logit model}\index{Logit}. On
the other hand, determining the equilibrium matching patterns $\bm{{\Greekmath 0116}}$ for
given primitive parameters $\bm{\Phi}, \bm{n}, \bm{m}$ is more involved; and it is
necessary in order to evaluate counterfactuals that modify these primitives
of the model. We will show how to do it in Section~\ref{ch:structuraltumodels:sub:ipfp} below. In
addition, the analyst may want to assume that the joint surplus
matrix $\bm{\Phi}$ belongs in a parametric family $\bm{\Phi}^{{\Greekmath 0115}}$. While this
could be done by finding the value of $\bm{{\Greekmath 0115}}$ that minimize the distance
between $\bm{\Phi}^{{\Greekmath 0115}}$ and the $\hat{\bm{\Phi}}$ obtained from~
\eqref{ch:structuraltumodels:eq:csident}, the approach sketched in Section~\ref{ch:structuraltumodels:sub:momatch} is more appealing.
To construct an \textit{extended entropy}\index{Extended entropy} function $E$ in the logit model, we rely on the primitive of
the logarithm $\mathcal{L}(t)= t\log t-t$; we define $f(\bm{T})= \sum_{x} \mathcal{L}(T_x)$, and similarly for $g$. They are clearly convex functions.
The reason for this a priori non-obvious choice of strictly convex functions
is that many of the terms in the derivatives of the resulting extended
entropy cancel out. In fact, simple calculations give
\begin{equation}
E^{\ast }\left(\bm{z}\right) =2 \sum_{\substack{ x\in \mathcal{X} \\ y\in
\mathcal{Y}}}\exp \left(\frac{z_{xy}}{2}\right) + \sum_{x\in \mathcal{X}
}\exp \left(z_{x0}\right) + \sum_{y\in \mathcal{Y}}\exp \left(z_{0y}\right).
\label{ch:structuraltumodels:Estar-logit}
\end{equation}
Substituting into~\eqref{ch:structuraltumodels:eq:mm:Estar}, the moment matching estimator and associated utilities solve
\begin{equation*}
\min_{\bm{{\Greekmath 0115}}, \bm{u}\geq 0, \bm{v}\geq 0}F\left(\bm{{\Greekmath 0115}},\bm{u}, \bm{v}\right)
\end{equation*}
where
\begin{eqnarray*}
F\left(\bm{{\Greekmath 0115}},\bm{u}, \bm{v}\right) &=&\sum_{x\in \mathcal{X}}\exp \left(
-u_{x}\right) +\sum_{y\in \mathcal{Y}}\exp \left( -v_{y}\right) +2\sum
_{\substack{ x\in \mathcal{X} \\ y\in \mathcal{Y}}}\exp \left( \frac{\Phi
_{xy}^{{\Greekmath 0115} }-u_{x}-v_{y}}{2}\right) \\
&&-\sum_{\substack{ x\in \mathcal{X} \\ y\in \mathcal{Y}}}\hat{{\Greekmath 0119}}
_{xy}\left( \Phi _{xy}^{{\Greekmath 0115} }-u_{x}-v_{y}\right) +\sum_{x\in \mathcal{X}}
\hat{{\Greekmath 0119}}_{x0}u_{x}+\sum_{y\in \mathcal{Y}}\hat{{\Greekmath 0119}}_{0y}v_{y}.
\end{eqnarray*}
This is the objective function of a \textit{Poisson regression}\index{Poisson regression} with two-way fixed effects.
Minimizing $F$ is a very easy task; we give some specialized algorithms in Section~\ref{ch:structuraltumodels:sec:computation}, but problems of moderate size can also be treated using statistical packages handling generalized linear models. Denote $\bm{{\Greekmath 010B}}=(\bm{{\Greekmath 0115}},\bm{u}, \bm{v})$ the set of arguments of $F$. The asymptotic distribution of the estimator of $\bm{{\Greekmath 010B}}$ is given in Appendix~B.
\subsection{The Maximum-score Method}\label{ch:structuraltumodels:sub:max-score}
In most one-sided random utility models of discrete choice, the probability
that a given alternative is chosen increases with its mean utility. Assume
that alternative $k$ has utility $U(x_{kl},{\Greekmath 0112}_0)+u_{kl}$ for individual $
l$. Let $K(l)$ be the choice of individual $l$ and for any given ${\Greekmath 0112}$,
denote
\begin{equation*}
R_l({\Greekmath 0112}) \equiv \sum_{k\neq K(l)} \mathrm{1\kern-.40em 1}
\left(U(x_{l,K(l)},{\Greekmath 0112}) > U(x_{kl},{\Greekmath 0112})\right)
\end{equation*}
the rank (from the bottom) of the chosen alternative $K(l)$ among the mean
utilities. Choose any increasing function $F$. If (for simplicity) the $
u_{kl}$ are iid across $k$ and $l$, maximizing the score function
\begin{equation*}
\sum_l F\left(R_l({\Greekmath 0112})\right)
\end{equation*}
over ${\Greekmath 0112}$ yields a consistent estimator of ${\Greekmath 0112}_0$. The underlying
intuition is simply that the probability that $k$ is chosen is an increasing
function of the differences of mean utilities $U(x_{kl},{\Greekmath 0112}) -
U(x_{k^\prime l},{\Greekmath 0112})$ for all $k^\prime\neq k$.
It seems natural to ask whether a similar property also holds in two-sided
matching with transferable utility: is there a sense in which (under
appropriate assumptions) the probability of a match increases with the
surplus it generates?
If transfers are observed, then each individual's choices is just a
one-sided choice model and the maximum score estimator can be used
essentially as is. Without data on transfers, the answer is not
straightforward. In a two-sided model, the very choice of a single ranking
is not self-evident. In so far as the \textit{optimal matching}\index{Optimal matching} is partly driven by
unobservables, it is generally not true that the optimal matching maximizes
the joint total non-stochastic surplus for instance.
One can give a positive answer in one of the models we have already
discussed: the \textit{logit}\index{Logit} specification of Section~\ref{ch:structuraltumodels:sub:mlogit}. Formula~\eqref{ch:structuraltumodels:eq:csmmf}
implies that for any $(x,x^\prime, y,y^\prime)$, the double log-odds ratio
$2 \log ( ( {\Greekmath 0116}_{xy} {\Greekmath 0116}_{x^\prime y^\prime} ) / ( {\Greekmath 0116}_{x,y^\prime} {\Greekmath 0116}_{x^\prime y} ))$
equals the double difference
\begin{equation*}
D_{\Phi}(x,x^\prime, y,y^\prime) \equiv \Phi_{xy} +
\Phi_{x^\prime y^\prime} - \Phi_{x^\prime y}-\Phi_{x y^\prime}.
\end{equation*}
This direct link between the observed matching patterns and the unknown
surplus function justifies a \textit{maximum-score estimator}\index{Maximum-score method}
\begin{equation*}
\max_{\bm{\Phi}} \sum_{(x,x^\prime, y,y^\prime) \in C} \mathrm{1\kern-.40em 1}
\left(D_{\Phi}(x,x^\prime, y, y^\prime) > 0 \right)
\end{equation*}
where $C$ is a subset of the pairs that can be formed from the data.
More generally, one can prove the following result.
\begin{theorem}[Comonotonicity of double-differences]\label{ch:structuraltumodels:thm:maxscore:exch}
Assume that the
surplus is separable and that the distribution of the unobservable heterogeneity
vectors is exchangeable.
Then for all $(x,y,x^\prime,y^\prime)$, the log-odds
ratio $ D_{\Phi}(x,x^\prime, y, y^\prime) $ and the double difference $ \log ( ( {\Greekmath 0116}_{xy} {\Greekmath 0116}_{x^\prime y^\prime} ) / ( {\Greekmath 0116}_{x,y^\prime} {\Greekmath 0116}_{x^\prime y} ))$ have the same sign.
\end{theorem}
While this is clearly a weaker result than in the
\textit{logit}\index{Logit} model, it is enough to apply the same maximum-score
estimator.
One of the main advantages of the maximum-score method is that it
extends to more complex matching markets. It also allows the
analyst to select the tuples of trades in $C$ to emphasize those that are
more relevant in a given application. The price to pay is double. First, the
maximum-score estimator maximizes a discontinuous function and converges slowly\footnote{
The maximum-score estimator converges at a cubic-root rate.}. Second, the
underlying monotonicity property only holds for distributions of unobserved
heterogeneity that exclude nested logit models and random coefficients for
instance.
\section{Computation}\label{ch:structuraltumodels:sec:computation}
We now turn to the efficient evaluation of the stable matching and the associated utilities for given values of the parameters.
In all of this section, we consider any
distributional parameters $\bm{{\Greekmath 010C}}$ as fixed and we omit them from the notation.
\subsection{Solving for equilibrium with coordinate descent}\label{ch:structuraltumodels:sub:ipfp}
First consider the determination of the equilibrium matching patterns for a given matrix $\bm{\Phi}$. In several important models, this can be done by adapting formula~\eqref{ch:structuraltumodels:eq:mm:Estar}. A slight modification of the arguments that lead to this formula shows that for given $\bm{\Phi}$, maximizing the following function yields the equilibrium utilities of all \textit{types}\index{Types}:
\begin{equation*}
\bar{F}(\bm{u},\bm{v}):= \sum_{x,y} \hat{{\Greekmath 0116}}_{xy}\Phi_{xy}
-\langle\hat{\bm{n}},\bm{u}\rangle
-\langle\hat{\bm{m}},\bm{v}\rangle-E^\ast\left(\bm{\Phi} -\bm{u}-\bm{v},-\bm{u},-\bm{v}\right).
\end{equation*}
\textit{Coordinate descent}\index{Coordinate descent} consists of maximizing $\bar{F}$ iteratively with respect to
the two argument vectors: with respect to $\bm{u}$ keeping $\bm{v}$ fixed, then with
respect to $\bm{v}$ keeping $\bm{u}$ fixed at its new value, etc.
Let $\bm{v}^{(t)}$ be the current value of $\bm{v}$. Minimizing $\bar{F}$ with respect to $\bm{u}$
for $\bm{v}=\bm{v}^{(t)}$ yields a set of $\left\vert \mathcal{X}\right\vert$
equations in $\left\vert \mathcal{X}\right\vert$ unknowns: $u_{x}^{(t+1)}$
is the value of $u_x$ that solves
\begin{align*}
\hat{n}_{x} &=\sum_{y\in \mathcal{Y}}\frac{\partial E^{\ast }}{\partial
z_{xy}}\left(\bm{\Phi}-\bm{u}-\bm{v}^{(t)},-\bm{u}, -\bm{v}^{(t)}\right) \\
&+\frac{\partial E^{\ast}}{\partial z_{x0}}\left(\bm{\Phi}-\bm{u}-\bm{v}^{(t)},-\bm{u}, -\bm{v}^{(t)}\right).
\end{align*}
These equations can in turn be solved coordinate by coordinate: we start
with $x=1$ and solve the $x=1$ equation for $u^{(t+1)}_1$ fixing $
(u_2,\ldots,u_{\lvert\mathcal{X}\rvert})=(u_2^{(t)},\ldots,u_{\lvert\mathcal{X}\rvert
}^{(t)})$; then we solve the $x=2$ equation for $u^{(t+1)}_2$ fixing $
(u_1,u_3,\ldots,u_{\lvert\mathcal{X}\rvert})=(u_1^{(t+1)},u_3^{(t)},\ldots,u_{
\lvert\mathcal{X}\rvert}^{(t)})$, etc. The convexity of the function $E^\ast$
implies that the right-hand side of each equation is strictly decreasing in
its scalar unknown, which makes it easy to solve.
The \textit{logit}\index{Logit} model constitutes an important special case in which
these equations can be solved with elementary calculations, for any joint
surplus matrix $\bm{\Phi}$. Define $S_{xy}:=\exp (\Phi_{xy}/2); a_{x}:=\exp
\left( -u_{x}\right)$; and $b_{y}:=\exp \left( -v_{y}\right)$. It is easy to
see that the system of equations that determines $\bm{u}^{(t+1)}$ becomes
\begin{equation*}
a_{x}^2 +a_{x}\sum_{y\in \mathcal{Y}}b^{(t)}_{y}S_{xy} =n_{x} \; \; \forall
x\in \mathcal{X}.
\end{equation*}
These are $\lvert\mathcal{X}\rvert$ functionally independent quadratic equations,
which can be solved in closed-form and in parallel. Once this is done, a
similar system of independent quadratic equations gives $\bm{b}^{(t+1)}$ from $
\bm{a}^{(t+1)}$. Note that $
a^{(0)}_x=\sqrt{\hat{{\Greekmath 0116}}_{x0}}$ and $b^{(0)}_y=\sqrt{\hat{{\Greekmath 0116}}_{0y}}$ are
obvious good choices for initial values.
This procedure generalizes the
\textit{Iterative Proportional Fitting Procedure (IPFP)}\index{Iterative Proportional Fitting Procedure (IPFP)}, also known as \textit{Sinkhorn's
algorithm}\index{Sinkhorn's
algorithm}. It converges globally and very fast. Once the solutions $\bm{a}$ and $\bm{b}$ are obtained, the equilibrium
matching patterns for this $\bm{\Phi}$ are given by ${\Greekmath 0116} _{x0}=a_{x}^{2}$, ${\Greekmath 0116}
_{0y}=b_{y}^{2}$ and ${\Greekmath 0116} _{xy}=a_{x}b_{y}S_{xy}$.
\subsection{Gradient descent}
Suppose that the analyst has chosen to use~\eqref{ch:structuraltumodels:eq:mm:Estar} for estimation.
The simplest approach to maximizing the objective function is through \textit{gradient descent}\index{Gradient descent}.
Denoting $\bm{{\Greekmath 010B}}=(\bm{{\Greekmath 0115}},\bm{u},\bm{v})$, we start from a reasonable\footnote{In the logit model, $u^{(0)}_x=-\log (\hat{{\Greekmath 0116}}_{x0}/\hat{n}_x)$
and $v^{(0)}_y=-\log (\hat{{\Greekmath 0116}}_{0y}/\hat{m}_y)$ are excellent choices of
initial values.} $\bm{{\Greekmath 010B}}^{(0)}$
and we iterate:
\begin{equation*}
\bm{{\Greekmath 010B}}^{(t+1)}=\bm{{\Greekmath 010B}}^{(t)}-{\Greekmath 010F} ^{(t)}{\Greekmath 0272} F\left(\bm{{\Greekmath 010B}}^{(t)}\right)
\end{equation*}
where ${\Greekmath 010F} ^{(t)}>0$ is a small enough parameter. This gives
\begin{align*}
u_{x}^{(t+1)}&=u_{x}^{(t)}+{\Greekmath 010F} ^{(t)}\left(n_{x}-N_x(\bm{{\Greekmath 0116}}^{(t)})\right)
\\
v_{y}^{(t+1)}&=v_{y}^{(t)}+{\Greekmath 010F} ^{(t)}\left(m_y -M_y(\bm{{\Greekmath 0116}}^{(t)})\right) \\
{\Greekmath 0115} _{k}^{(t+1)}&={\Greekmath 0115} _{k}^{(t)}+{\Greekmath 010F} ^{(t)}\sum_{\substack{
x\in \mathcal{X} \\ y\in \mathcal{Y}}}\left( {\Greekmath 0116} _{xy}^{(t)}-\hat{{\Greekmath 0116}}
_{xy}\right) {\Greekmath 011E} _{xy}^{k},
\end{align*}
denoting $\bm{{\Greekmath 0116}}^{(t)}$ the result of plugging $(\bm{u}^{(t)},\bm{v}^{(t)},\bm{{\Greekmath 0115}}^{(t)})$
into~(\ref{ch:structuraltumodels:def_pi_theta}).
This algorithm has a simple intuition: we adjust $u_{x}$ in proportion of
the excess of $x$ \textit{types}\index{Types}, $v_{y}$ in proportion of the excess of $y$ types,
and $\bm{{\Greekmath 0115}}$ in proportion of the mismatch between the $k$-th moment
predicted by $\bm{{\Greekmath 010B}}$ and the observed $k$-th moment.
\subsection{Hybrid Algorithms}
The approaches in the previous two subsections can also be combined. \cite{carlier2020sista} suggest alternating between
coordinate descent steps on $\bm{u}$ and $\bm{v}$ and gradient descent steps on $
\bm{{\Greekmath 0115}}$. In the \textit{logit}\index{Logit}
model, this would combine the updates
\begin{equation*}
\left\{
\begin{array}{l}
\left(a^{(t+1)}_{x}\right)^2 +a^{(t+1)}_{x}\sum_{y\in \mathcal{Y}
}b^{(t)}_{y}S^{(t)}_{xy} =n_{x} \\
\left(b^{(t+1)}_{y}\right)^2 +b^{(t+1)}_{y}\sum_{x\in \mathcal{X}
}a^{(t+1)}_{y} S^{(t)}_{xy} =m_y \\
{\Greekmath 0115} _{k}^{(t+1)}={\Greekmath 0115} _{k}^{(t)}+{\Greekmath 010F} ^{(t)}\sum_{\substack{ x\in
\mathcal{X} \\ y\in \mathcal{Y}}}\left(a_{x}^{(t+1)}b_{y}^{(t+1)}
S_{xy}^{(t)} -\hat{{\Greekmath 0116}}_{xy}\right) {\Greekmath 011E}_{xy}^{k}
\end{array}
\right.
\end{equation*}
where $S_{xy}^{(t)} =\exp(\sum_{k=1}^K {\Greekmath 011E}_{xy}^k {\Greekmath 0115}^{(t)}_k/2)$.
A proof of convergence of hybrid algorithms is given in~\cite
{carlier2020sista}, in a more general setting that allows for model
selection based on penalty functions.
\section{Other Implementation Issues}
Let us now very briefly discuss three issues that often crop up in
applications.
\subsection{Continuous Types}
While we modeled types as discrete-valued in this chapter, there are
applications where this is not appropriate. It is possible to
incorporate continuous types in a separable model that feels very similar to the logit model of Section~\ref{ch:structuraltumodels:sub:mlogit}. The idea is to model the choice of possible partners as generated by
the points of a specific \textit{Poisson process}\index{Poisson process}. An interesting special case has a bilinear \textit{joint surplus function}\index{Joint surplus function} $\Phi(x,y) = x^{\top} A y$. It is easy to see that at the optimum, the Hessian of the logarithm of the matching patterns equals $A$ everywhere: for all $x\in \mathbb{R}^{d_{x}}$
and $y\in \mathbb{R}^{d_{y}}$,
\begin{equation*}
\frac{\partial ^{2}\ln {\Greekmath 0116}}{\partial x \partial y} \left( x,y\right)
=\frac{A}{2}.
\end{equation*}
As a consequence, the model is overidentified and therefore testable. Among other things, it makes it possible to test for the rank of the matrix $A$. If it is some $r<\min(d_x, d_y)$, then one can identify the ``salient'' combination of types that generate the joint surplus.
If moreover the distribution $P$ of $x$ and the distribution $Q$ of $y$ are Gaussians, that the \textit{optimal matching}\index{Optimal matching} $\left(X,Y\right)$ is a Gaussian vector whose
distribution can be obtained in closed form. Suppose for instance that $
d_{x}=d_{y}=1$; $P=\mathcal{N}\left( 0,{\Greekmath 011B} _{x}^{2}\right)$; $Q=\mathcal{N
}\left( 0,{\Greekmath 011B} _{y}^{2}\right)$; and $\Phi \left( x,y\right) =axy$, Then
at the optimum $V X ={\Greekmath 011B} _{x}^{2}$, $VY ={\Greekmath 011B} _{y}^{2}$, and $
\mbox{corr}\left( X,Y\right) ={\Greekmath 011A}$ where ${\Greekmath 011A}$ is related to $a$ by
\begin{equation*}
a{\Greekmath 011B} _{x}{\Greekmath 011B} _{y}=\frac{{\Greekmath 011A} }{1-{\Greekmath 011A} ^{2}}.
\end{equation*}
\subsection{Using Several Markets}\label{ch:structuraltumodels:sub:Using Several Markets}
We have focused on the case when the
analyst has data on one market. If data on several markets is available;
matches do not cross market boundaries; and some of the primitives of the
model coincide across markets, then this can be used to relax the conditions
necessary for \textit{identification}\index{Identification}.
As an example, \cite{csw:17} pooled Census data on thirty cohorts in the US
in order to study the changes in the marriage returns to education. To do
this, they assumed that the supermodularity module of the function $\Phi$
changed at a constant rate over the period.
\cite{foxyanghsu} show how given enough markets, one can identify the
distribution of the \textit{unobserved heterogeneity}\index{Unobserved heterogeneity} if it is constant across
markets.
\subsection{Using Additional Data}
In applications to the labor market for instance, the analyst often has some
information on transfers---wages in this case. This information can be used
in estimating the underlying matching model. It is especially useful if it
is available at the level of each individual match. Aggregate data on
transfers has more limited value \citep{salanieidentobstransfers:15}.
\section{Notes}
Matching with perfectly transferable utility was introduced by~\cite{kb:57} and its theoretical properties were elucidated by \cite{ss:72}. \cite{becker:73, becker:74} made it the cornerstone of his analysis of marriage.
Sections~\ref{ch:structuraltumodels:sec:ident} and~\ref{ch:structuraltumodels:sec:estimation} of this chapter are based on
the approach developed in~\cite{cupid:20}. The extension of the logit model to continuous types was proposed by~\cite{dg:14}, following~\cite
{dagsvik:00}. They applied it to study how the joint surplus from marriage depends on the Big Five psychological traits of the partners. \cite{grst:20} combine continuous and discrete types to model mergers between European firms. The results for the bilinear Gaussian models appear in~\cite{bojilov:16}.
The maximum-score method for matching models was proposed by~\cite
{fox:identmatchinggames}, taking inspiration from~\cite{ManskiMaxScore:75}'s classic paper on one-sided discrete choice models. \cite
{bajarifox} used this estimator to study the FCC spectrum auctions. \cite{graham:hdbk,graham:hdbkerrata} proved Theorem~\ref{ch:structuraltumodels:thm:maxscore:exch} for independent and identically distributed variables and~\cite{fox:qe18} extended it to exchangeable variables.
\bibliographystyle{cambridgeauthordate}
\bibliography{Matching}