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.
59,985 characters · 23 sections · 18 citation commands
Structural Estimation of Matching Markets with Transferable Utility
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 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 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 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 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 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 optimal transport\index{Optimal transport}. Under an additional \textquotedblleft separability\index{Separability}\textquotedblright\ assumption, most functions of interest are convex; then convex duality\index{Convex duality} gives a simple and transparent path to identificationidentification\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 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) introduces separable matching models. Section (ref) presents assumptions under which data on “who matches whom” (the 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)), and how to compute the stable matchings for given parameter values (Section (ref)).
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}$.
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 perfectly transferable utility\index{Perfectly transferable utility} implies that their respective utilities can be written as
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 {\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.}.
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$.
Our notion of equilibrium is 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.}.
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 stability\index{Stability}.
The conditions in Definition (ref) are exactly the Karush-Kuhn-Tucker optimality conditions\index{Karush-Kuhn-Tucker optimality conditions} of the following maximization program:
if $u_i$ and $v_j$ are the multipliers of the feasibility conditions. Thus the stable matchings maximize the total joint surplus\index{Joint surplus} under the feasibility constraints. Program (ref) above is called the {\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
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.
A proper econometric setting requires that we distinguish carefully what the analyst can observe from {\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 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 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:
In the language of analysis of variance models, the separability\index{Separability} assumption rules out two-way interactions between unobserved characteristics, conditional on observed 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:
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$.
Convex duality\index{Convex duality} will be the key to our approach to identification\index{Identification}. We start by rewriting the dual characterization of the stable matching in (ref) as
Given Assumption (ref), the constraint in (ref) can be rewritten as
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
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 dual program\index{Dual program} as
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 joint surplus\index{Joint surplus}:
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) 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 (ref) would lose its nice separable structure.
Moreover, the nested min-max in equation (ref) 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
where
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$):
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 (ref): \[ \partial G(\bm{U})\cap \partial H(\bm{\Phi}-\bm{U}) \neq \emptyset. \]
Now let us denote $ G^{\ast }$ the Legendre-Fenchel transform\index{Legendre-Fenchel transform} of the convex function $G$:
It is another convex function; and by the theory of convex duality\index{convex duality} we know that since
we also have $\bm{U} = G^{\ast }(\bm{{\Greekmath 0116}}^{M})$, that is
Similarly,
In equilibrium, $\bm{{\Greekmath 0116}}^M=\bm{{\Greekmath 0116}}^W:=\bm{{\Greekmath 0116}}$ and $\bm{U}+\bm{V}=\bm{\Phi}$; therefore we obtain
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 unobserved heterogeneity\index{Unobserved heterogeneity} terms, this is the piece of information we need.
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.
We already know from Section (ref) that the stable matching maximizes the total joint surplus. The corresponding primal program\index{Primal program} is
where
is the generalized entropy\index{generalized entropy} of the matching $\bm{{\Greekmath 0116}}$. It is easy to check that the first-order conditions in (ref) (which is globally concave) coincide with the identification\index{Identification} formula (ref).
The two parts of the objective function in (ref) have a natural interpretation. The sum $\sum_{x,y}{\Greekmath 0116}_{xy}\Phi_{xy}$ reflects the value of matching on observed 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 (ref) 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).
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 standard type I extreme value (Gumbel)\index{Gumbel distribution}. Under this distributional assumption, the $G_{x}$ functions take a very simple and familiar form:
and the generalized entropy function $\mathcal{E}$ is just the usual entropy\index{Entropy}:
Equation (ref) can be rewritten to yield the following matching function\index{Matching function}, which links the numbers of singles, the joint surplus, and the numbers of matches:
In the 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 (ref) gives Choo and Siow's formula\index{Choo and Siow's formula}:
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
the number of households in our sample, and let
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
We seek to estimate a 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 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).
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
Maximizing this expression gives a 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.
A natural choice of parameterization for $\bm{\Phi}^{\bm{{\Greekmath 0115}}}$ is the linear expansion
where the basis functions ${\Greekmath 011E} _{xy}^{k}$ are given and the ${\Greekmath 0115}_{k}$ coefficients are to be estimated.
The 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 (ref) 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
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 (ref) 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 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 (ref) as
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:
where we denote $\bm{\Phi} -\bm{u}-\bm{v}={(\Phi _{xy}-u_{x}-v_{y})}_{x,y}$.
Returning to (ref), the program that defines the moment matching estimator can now be rewritten as follows:
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 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:
The logit model of Section (ref) provides an illustration of this approach.
Plugging in estimates $\hat{\bm{{\Greekmath 0116}}}$ of the matching patterns in formula (ref) gives a closed-form estimator $\hat{\bm{\Phi}}$ of the joint surplus\index{Joint surplus} matrix in the 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) 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 (ref), the approach sketched in Section (ref) is more appealing.
To construct an 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
Substituting into (ref), the moment matching estimator and associated utilities solve
where
This is the objective function of a 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), 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.
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
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
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 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 logit\index{Logit} specification of Section (ref). Formula (ref) 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
This direct link between the observed matching patterns and the unknown surplus function justifies a maximum-score estimator\index{Maximum-score method}
where $C$ is a subset of the pairs that can be formed from the data.
More generally, one can prove the following result.
While this is clearly a weaker result than in the 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.
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.
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 (ref). 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 types\index{Types}:
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
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 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
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 Iterative Proportional Fitting Procedure (IPFP)\index{Iterative Proportional Fitting Procedure (IPFP)}, also known as 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}$.
Suppose that the analyst has chosen to use (ref) for estimation. The simplest approach to maximizing the objective function is through 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:
where ${\Greekmath 010F} ^{(t)}>0$ is a small enough parameter. This gives
denoting $\bm{{\Greekmath 0116}}^{(t)}$ the result of plugging $(\bm{u}^{(t)},\bm{v}^{(t)},\bm{{\Greekmath 0115}}^{(t)})$ into ((ref)).
This algorithm has a simple intuition: we adjust $u_{x}$ in proportion of the excess of $x$ 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.
The approaches in the previous two subsections can also be combined. carlier2020sista suggest alternating between coordinate descent steps on $\bm{u}$ and $\bm{v}$ and gradient descent steps on $ \bm{{\Greekmath 0115}}$. In the logit\index{Logit} model, this would combine the updates
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 carlier2020sista, in a more general setting that allows for model selection based on penalty functions.
Let us now very briefly discuss three issues that often crop up in applications.
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). The idea is to model the choice of possible partners as generated by the points of a specific Poisson process\index{Poisson process}. An interesting special case has a bilinear 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}}$,
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 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
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 identification\index{Identification}.
As an example, 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.
foxyanghsu show how given enough markets, one can identify the distribution of the unobserved heterogeneity\index{Unobserved heterogeneity} if it is constant across markets.
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 salanieidentobstransfers:15.
Matching with perfectly transferable utility was introduced by kb:57 and its theoretical properties were elucidated by ss:72. becker:73, becker:74 made it the cornerstone of his analysis of marriage. Sections (ref) and (ref) of this chapter are based on the approach developed in cupid:20. The extension of the logit model to continuous types was proposed by dg:14, following dagsvik:00. They applied it to study how the joint surplus from marriage depends on the Big Five psychological traits of the partners. grst:20 combine continuous and discrete types to model mergers between European firms. The results for the bilinear Gaussian models appear in bojilov:16.
The maximum-score method for matching models was proposed by fox:identmatchinggames, taking inspiration from ManskiMaxScore:75's classic paper on one-sided discrete choice models. bajarifox used this estimator to study the FCC spectrum auctions. graham:hdbk,graham:hdbkerrata proved Theorem (ref) for independent and identically distributed variables and fox:qe18 extended it to exchangeable variables.