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.
55,965 characters · 12 sections · 22 citation commands
Transferable Utility Matching Beyond Logit: Computation and Estimation with General Heterogeneity
Empirical work on matching has reshaped how economists measure sorting, evaluate policy, and interpret the formation of two-sided relationships such as marriages, employment, and college admissions. The model by ChooSiow2006, in particular, has become a popular framework to analyze markets under the transferable utility (TU) assumption. The appeal of this framework lies in large part in its analytical tractability: when the agents' idiosyncratic preference shocks are assumed to be i.i.d.\ extreme value type-I (Gumbel), equilibrium matching patterns admit a closed-form logit structure that maps directly from surplus parameters to observed match frequencies. This assumption has fostered a vast empirical literature on assortative matching by education, income, age, ethnicity, and other attributes ChiapporiSalanieWeiss2017, GousseJacquemetRobin2017, BisinTura2019, Ciscato2025.
Yet the same assumption that ensures tractability can also be a serious limitation. In modern datasets of the marriage market for instance, types can usually be defined as the intersection of several observable attributes since large administrative data now allow rich cross-classifications. As the number of attributes grows, it becomes increasingly implausible that an individual's unobserved preferences for all composite options are independent. For instance, a person's idiosyncratic value for a highly educated urban partner is likely to be correlated with her value for a highly educated rural partner, since both options share the same education component. When independence is imposed by construction, substitution patterns and counterfactual responses become mechanically constrained, and estimates of sorting strength or welfare effects may be distorted.
This paper develops a general and computationally tractable framework that relaxes the i.i.d.\ Gumbel assumption while retaining the economic structure that underlies the original Choo--Siow model. Our framework allows for arbitrary distributions of the idiosyncratic preference shocks, including rich correlation structures induced by multi-attribute types. For example, we can let the shock for a composite type $y=(y_1,y_2)$ decompose additively across its attributes, $\varepsilon_{i,y}=\varepsilon_{i,y_1}+\varepsilon_{i,y_2}$, where the attribute-level shocks are independent. This simple construction introduces correlation across composite options that share such attributes and encompasses a wide class of probit and nested-logit specifications without committing to any closed-form functional form.
Our contribution is essentially twofold. In a first step, we propose an algorithm to solve in practice large-scale optimal assignment problems à la Shapley-Shubik1971. This method is grounded in tools developed to solve large-scale linear programs, specifically the Dantzig--Wolfe decomposition DantzigWolfe1960. We discuss the natural economic interpretation of our algorithm as a series of discrete choice problems, and we use numerical simulations to demonstrate its performance in solving large optimal assignment problems. Depending on the scale of the problem to solve, we record up to 25 times computational gains for our algorithm compared to a state-of-the-art general-purpose solver.
In a second step, we build on this formulation to provide a method for estimating the matching surplus, which is suited to large-scale data and general distributions. Following GalichonSalanie2022, we recover (a parametrized version of) the systematic surplus matrix $\Phi$ from observed type-by-type match frequencies using a moment-matching approach. When the idiosyncratic shocks are i.i.d.\ Gumbel, estimation can be performed using closed-form formulas. In general however it cannot, and we therefore rely on a method by simulation. We show that the problem of estimating the matching surplus is then equivalent to a finite assignment problem with simulated agents, which we can solve using our algorithm discussed above. Again using numerical experiments, we demonstrate the consistency of our estimator on an example with probit errors, and exhibit a consistent bias when using a misspecified error distribution.
Our approach relates to several strands of the literature. Within the TU matching tradition, our methodology builds directly on ChooSiow2006 and GalichonSalanie2022, maintaining separability but dispensing with the distributional restrictions that yield logit formulas. In spirit, our treatment of correlated unobserved heterogeneity parallels advances in single-agent discrete-choice models, where probit and nested-logit specifications generalized the logit without sacrificing interpretability McFadden1981, Train2009. Our estimator also takes inspiration from the method of simulated moments developed by McFadden1989. Existing works have generalized the Choo--Siow model in other dimensions. GalichonSalanie2022 analyze the TU model of Choo and Siow under general distributional assumptions of the heterogeneity, although they do not explore the practical computational aspects studied here. GualdaniSinha2023, coincidentally also using techniques from linear programming, investigate partial identification of the matching surplus when the distributions of the preference heterogeneity is not known. \citet*{ChiapporiNguyenSalanie2019} investigate the bias which can result from mistakenly imposing the separability assumption.
The paper proceeds as follows. Section (ref) presents the model and motivates the role of separability under general error distributions. Section (ref) introduces the type-aggregated formulation and the RROA algorithm, establishes its convergence, and documents its computational performance. Section (ref) extends the analysis to estimation, defining the simulated social surplus and showing how the same algorithmic structure delivers an efficient simulated moment-matching estimator. Together, these results demonstrate that credible empirical matching with many attributes need not rely on the i.i.d.\ Gumbel assumption: flexible heterogeneity and large-scale data are now compatible within the transferable utility framework. Proofs for our formal statements can be found in appendix (ref).
We study a bipartite, one-to-one matching market with transferable utility à la ChooSiow2006. Matching is static, frictionless, and individuals have complete information on potential partners' types. The crucial difference between our framework and the one from ChooSiow2006 concerns the distribution of the individual heterogeneity: While they assume that shocks are i.i.d.\ Gumbel, we remain agnostic regarding their distribution. In this respect, our framework is closest to GalichonSalanie2022.
\paragraph{Matching.} Consider a population of women $i \in I$ and men $j \in J$, where $I$ and $J$ are finite sets. Each woman or man belongs to a type $x \in X$ or $y \in Y$, respectively; occasionally we may denote $x_i$ the type of woman $i$, and $y_j$ the type of man $j$. Because the population is finite, the number of observed types must also be finite. But beyond that, we think about the type sets $X$ and $Y$ as being orders of magnitude smaller than the populations $I$ and $J$. This reflects two facts. First, in empirical practice, types are defined as intersections of observed characteristics, which typically yield fewer types than individuals. Second, types are kept intentionally coarse in order to preserve statistical power.
A matching specifies who matches with whom. In our finite-population framework, it is simply a matrix $\tilde \pi = (\tilde \pi_{ij})$ of size $|I \times J|$ with non-negative entries such that
Conditions (ref)--(ref) have different interpretations depending on whether the matching is pure or fractional. A matching $\pi$ is called pure when $\tilde \pi_{ij} \in \{0,1\}$ for all $ij$. In this special case, we can interpret each $\tilde \pi_{ij}$ as the indicator that $i$ and $j$ are matched, hence conditions (ref)--(ref) mean that any individual should be matched to at most one partner. Individual-level data on married couples, for instance, typically involves pure matchings. When a matching is not pure however, it is called fractional. When fractional matchings are allowed, $\tilde \pi_{ij}$ can be interpreted instead as the fraction of time that $i$ is matched with $j$, and conditions (ref)--(ref) mean that any individual has a single unit of time to dispense across partners. Such data could occur for instance on labor markets with part-time workers. Even though our framework accommodates both pure and fractional matchings, we will often speak as if $\tilde \pi_{ij}$ were the indicator that $i$ and $j$ are matched to keep exposition simple.
\paragraph{Surplus and individual heterogeneity.} We now turn to the value created by a match. When woman $i$ and man $j$ form a pair, they generate a joint economic value $\tilde \Phi_{ij}$. Following ChooSiow2006, we assume that this joint value is separable in the following sense.
According to Assumption (ref), the joint value $\tilde \Phi_{ij}$ is the sum of three terms: a systematic part $\Phi_{xy}$, which only depends on the type pair $xy$ of the matched agents; and two idiosyncratic preference shocks $\varepsilon_{iy}$ and $\eta_{xj}$ of the agents over potential partner types. The systematic part $\Phi_{xy}$ is called the systematic surplus of the match. \footnote{The match surplus is $\tilde \Phi_{ij} - \varepsilon_{i0} - \eta_{0j} = \Phi_{xy} + (\varepsilon_{iy} - \varepsilon_{i0}) + (\eta_{xj} - \eta_{0j})$, so the name systematic surplus for $\Phi_{xy}$ is warranted as long as $\mathbf E [\varepsilon_{iy} - \varepsilon_{i0}] = 0$ and $\mathbf E [\eta_{xj} - \eta_{0j}] = 0$. This is however without loss of generality, since we can redefine $\varepsilon_{iy}' = \varepsilon_{iy} - \mathbf E [\varepsilon_{iy} - \varepsilon_{i0}]$, $\eta_{xj}' = \eta_{xj} - \mathbf E [\eta_{xj} - \eta_{0j}]$, and $\Phi_{xy}' = \Phi_{xy} + \mathbf E [\varepsilon_{iy} - \varepsilon_{i0}] + \mathbf E [\eta_{xj} - \eta_{0j}]$. } The separability assumption notably entails that individuals are indifferent between all potential partners of the same type. It is crucial to the identification of the systematic surplus $\Phi_{xy}$ GalichonSalanie2022.
ChooSiow2006 go further than Assumption (ref) since they assume that the error terms $\varepsilon_{iy}, \varepsilon_{i0}, \eta_{xj}, \eta_{0j}$ are i.i.d.\ Gumbel (extreme value type I), leading to convenient closed-form estimates of the systematic surplus. We wish to generalize their approach, and as such we do not make any ex ante assumption on the distribution of these error terms for most of our analysis. To see why considering such general distributions may be important, consider the following example where correlation in the idiosyncratic preferences arises naturally from the structure of the type sets $X$ and $Y$.
\paragraph{Example.} Consider a marriage market where each agent's observable type $x \in X$ (and symmetrically $y \in Y$) is defined by two characteristics, $x = (x_1, x_2)$. For instance, $x_1$ could be the education level (whether the agent has a college diploma), and $x_2$ the region of origin (whether the individual is from a rural or urban background). In the standard Choo--Siow framework, the idiosyncratic preference for, say, a highly educated urban woman is assumed to be independent of that for a highly educated rural woman. Now consider a more structured alternative, where the idiosyncratic shock attached to the composite type $x = (x_1, x_2)$ is the sum of two independent components drawn at the level of each attribute: \[ \eta_{xj} = \eta_{x_1, j} + \eta_{x_2, j}. \] This natural formulation induces correlation in idiosyncratic preferences across composite types sharing common characteristics. This captures, for instance, that an agent's preference over partners' education levels may be systematically related across regions of origin.
\paragraph In the spirit of the previous example, general distributions of the idiosyncratic preferences allow us to consider a wide range of models beyond the i.i.d.\ Gumbel case, such as probit models with arbitrary covariance matrices or nested logit models.
In this section we study the optimal assignment problem and its computation when the population size becomes very large. The computational tools that we introduce here lay the groundwork for the estimation method that we present in section (ref).
Given realized match values $\tilde \Phi_{ij}$ and singlehood utilities $\varepsilon_{i0}$ and $\eta_{0j}$, the optimal assignment problem consists in finding a matching $\tilde \pi$ which maximizes the total surplus in the population:
We call such a matching $\tilde \pi$ an optimal matching. It is well known since Shapley-Shubik1971 that any optimal matching can be decentralized as the equilibrium of a matching problem with transferable utility (TU), whereby the value $\tilde \Phi_{ij}$ created by a match $ij$ is split additively between the two partners. Crucially, the resulting utilities $u_i$ and $v_j$ are recovered in the optimal assignment problem (ref) as the Lagrange multipliers of the constraints indexed by $i$ and $j$ respectively. The TU assumption thus means that $u_i + v_j = \tilde \Phi_{ij}$ as soon as $\tilde \pi_{ij} > 0$.
We are interested in solving the optimal assignment problem (ref) when the size of the population becomes large. This is a linear program with $|I \times J|$ variables and $|I + J|$ constraints, hence its size $|I||J| \times |I + J|$ is cubic in the population size. If, for instance, we consider a typical dataset as having around 10,000 individuals for $I$ and $J$, the problem's size is of order $10^{12}$, rendering it intractable for standard linear solvers. We therefore need an alternative method to tackle the problem.
As a first step towards solving (ref), we show that we can leverage the separability assumption in order to reduce the problem's size. We introduce some notations: let $\delta_{ix} = \mathbf 1(x_i = x)$ and $\delta_{jy} = \mathbf 1(y_j = y)$ be indicators of individuals' type, and define
The value $\alpha_{iy}$ is the utility obtained by woman $i$ when she matches with a man of type $y$, under the assumption that systematic surplus is split equally between partners. \footnote{This equal splitting the surplus by default is an arbitrary convention chosen to maintain symmetry: how surplus is actually divided between partners does not matter for the purpose of maximizing the total surplus.} Similarly, $\gamma_{xj}$ is the utility obtained by man $j$ when he matches with a woman of type $x$.
Notice that, under Assumption 1, individuals are indifferent between potential partners of the same type, and therefore a matching need not keep track of exactly which $i$ matches with which $j$, but only of which type each individual is matched with. This leads us to introduce the new aggregated variables
indicating respectively whether woman $i$ is matched with a man $y$, and whether man $j$ is matched with a woman $x$. Similarly, we introduce the singlehood indicators
indicating respectively whether woman $i$ and man $j$ are unmatched. Using these aggregated variables, the optimal assignment problem (ref) admits the alternative formulation
Problem (ref) includes individual feasibility constraints indexed by $i$ and $j$, similar to those in (ref). Their Lagrange multipliers still correspond to the utilities $u_i$ or $v_j$ obtained by each individual. The novelty lies in the balance condition $\sum_i \delta_{ix} \pi_{iy} = \sum_j \delta_{jy} \pi_{xj}$, which requires there to be as many women of type $x$ matched with men of type $y$, as there are men $y$ matched with women $x$. This new constraint is a simple consequence of type aggregation. Interestingly, the Lagrange multiplier associated with this constraint, which we denote $T_{xy}$, has a natural interpretation as the systematic transfer from women to men in matches $xy$. This transfer is such that if a woman $i$ of type $x$ and a man $j$ of type $y$ are matched, then their respective utilities are
The equivalence between the two problems (ref) and (ref) is made precise by the following result.
In the following, we focus on the formulation (ref), which we also refer to as the optimal assignment problem. Its solutions are also called optimal matchings.
Aside from questions of interpretation, the main advantage of formulation (ref) compared to (ref) is that its size has been reduced by one order of magnitude: this is now a linear program with $|I | |Y + 1| + |J| |X + 1|$ variables and $|XY| + |I + J|$ constraints, for a total size which is quadratic in the number of individuals. Even this size reduction can only get us so far, however: again with around 10,000 individuals in $I$ and $J$, the problem's size is of order $10^8$, which might still be tractable. However, larger datasets with hundreds of thousands or even millions of individuals (e.g.\ in the case of exhaustive country data) brings us back into intractable territory. For these large-scale problems, we still require more tools.
In this section we present an algorithm which is able to solve the optimal assignment problem (ref) even when $I$ and $J$ are large. Our procedure not only takes advantage of the structure of the optimal assignment problem to solve it efficiently, it also has an intuitive economic interpretation as a series of two-sided discrete choice problems. In essence, the algorithm consists of a repeated optimal assignment procedure in which the set of allowed matches, initially restricted, expands iteratively by adding each individual's favorite option. Our algorithm has links with existing tools in optimization, since it can be seen as a particular case of the Dantzig--Wolfe decomposition (a general algorithm for large-scale linear programming, see DantzigWolfe1960) applied to the assignment problem (ref).
\paragraph{Restricted optimal assignment and choice sets.} First, we define precisely what we mean by a restricted problem. For all women $i$, let $Y_i \subset Y$. We think of $Y_i$ as the subset of men types $y$ that woman $i$ is allowed to match with. Similarly, let $X_j \subset X$ the subset of women types $x$ that man $j$ is allowed to match with. We call the sets $Y_i$ and $X_j$ the choice sets of woman $i$ and man $j$, respectively. For any such $(Y_i)$ and $(X_j)$, we define the restricted optimal assignment problem associated with the choice sets $(Y_i)$ and $(X_j)$ as
The problem (ref) is nothing more than an assignment problem between women $i$ and men $j$, with the twist that agents can only be matched to types in their choice sets. To see this, observe that (ref) is obtained from the assignment problem (ref) by adding the constraints that $\pi_{iy} = 0$ whenever $y \notin Y_i$ and $\pi_{xj} = 0$ whenever $x \notin X_j$.
Consider a simple example as illustration. When choice sets are empty, i.e.\ $Y_i = X_j = \emptyset$ for all $i$ and $j$, problem (ref) only features the variables $\pi_{i0}$ and $\pi_{0j}$. The individual feasibility constraints write as $\pi_{i0} = 1$ and $\pi_{0j} = 1$. The balance conditions (indexed by $xy$) involve empty sums and are thus trivially verified. The solution to (ref) is thus the matching where every agent remains single. This is of course consistent with all choice sets being empty, i.e.\ no match being allowed.
We call any solution to the restricted optimal assignment problem (ref), a restricted optimal matching. On the one hand, restricted optimal matchings are typically faster to compute than (unrestricted) optimal matchings, because (ref) has fewer variables than (ref). But on the other hand, it is clear that restricted optimal matchings are not optimal in general. The following result provides a simple criterion to determine when a restricted optimal matching actually coincides with an optimal matching.
The logic behind Proposition (ref) comes from the standard Walrasian equilibrium interpretation of the assignment problem. Given the transfers $T_{xy}$ which support the matching, the value $\alpha_{iy} - \sum_i \delta_{ix} T_{xy}$ is the utility woman $i$ would get from matching with a man of type $y$. The inequality in (ref) thus compares her current utility $u_i$ to her best option among types she is currently not allowed to match with, i.e.\ $y \in Y \setminus Y_i$. The same interpretation applies symmetrically to men. Hence, condition (ref) imposes that, under the current transfers, everyone is already matched to their favorite type.
\paragraph{Algorithm.} In fact, Proposition (ref) does more than certify optimality; it also indicates how to improve the choice sets when optimality fails. Suppose we start from given choice sets $(Y_i)$ and $(X_j)$, solve the restricted problem (ref), and find that woman $i$ would strictly prefer some type $y \notin Y_i$ under the current transfers. We should therefore expand her choice set $Y_i$ to include that type $y$. Symmetrically, if some man $j$ would strictly prefer type $x \notin X_j$, we should add the type $x$ to $X_j$. Following this logic, we obtain Algorithm 1.
Notice that in Algorithm (ref), the agents' choice sets expand monotonically, hence the algorithm must eventually converge. At every step, at least one agent whose inequality in (ref) is violated gains a new admissible type in their choice set. Since there is a finite number of agents and of possible types, this process can only repeat finitely many times; specifically, $|I| |X| + |J| |Y|$ times. When no choice set expands anymore, all inequalities in (ref) are satisfied, and by Proposition (ref), the current restricted optimal matching is globally optimal. We can thus state the following result.
The monotonicity of the choice sets as a convergence condition is not without recalling Gale--Shapley's deferred acceptance algorithm to find stable matchings GaleShapley1962. In Gale--Shapley however, suitors' choice sets start full and progressively shrink as suitors get turned down by their most preferred match, as opposed to starting empty and expanding in our case. Of course, another difference is that Gale--Shapley applies to problems with nontransferable utility, whereas our algorithm targets problems with transferable utility.
To conclude this section on the optimal assignment problem, we benchmark the performance of our RROA procedure (Algorithm (ref)) against a state-of-the-art, general-purpose solver (Gurobi). We run numerical experiments for different parameter values and population sizes and compare the time needed to reach a solution using these two methods. Details about the hardware and software specifications we used can be found in Appendix (ref).
To compare the two methods, we consider several sizes for the type sets $X$ and $Y$ and for the populations $I$ and $J$. Then, for given sizes of these sets, we generate 10 random problems and solve them separately using RROA and Gurobi. For each problem we compute the relative performance of RROA as the ratio of the two solving times. Finally, we average this relative performance over the 10 trials to obtain a measure of the relative performance for these population and type sets sizes.
By default, Gurobi runs multiple LP solvers concurrently until one of them terminates. In order to make the comparison between methods easier, in this section we present the results when Gurobi is restricted to use a single method at a time, namely the Dual Simplex and Barrier methods. These two methods were chosen since they were the two methods consistently used by Gurobi in our experiments. By doing this, we isolate the RROA's advantage over these families of solvers. The benchmarking against Gurobi with its default, adaptive method also yielded significant computational improvements; these results are presented in Appendix (ref).
The results are displayed in Figure (ref) and (ref). We immediately notice that the computational gains of RROA are highly dependent on the size of the sets $X$, $Y$, $I$, and $J$. Against the Dual Simplex method, RROA's speedups steadily grow as scale increases and eventually achieve up to 25x speedups for larger number of types. In absolute terms, this corresponded to computing times of around 2 minutes for our RROA method, vs.\ 42 minutes for Gurobi with the Dual Simplex method to solve one problem. Against the Barrier method, smaller type sets achieve speedups up to 3--5x before declining closer to 1x for larger scales. In contrast, for higher number of types, the advantage becomes substantial, and the algorithm achieves up to 15x speedups. In absolute terms, this corresponded to computing times of around 90 seconds for our RROA method, vs.\ 23 minutes for Gurobi with the Barrier method to solve one problem. These results suggest that the RROA method is most efficient on a large scale when there are sufficiently many types.
We limited the simulations up to a $2^8$ population scale due to hardware computational constraints. (At the higher scale, solving a single assignment problem with Gurobi lasted around 40min.) Although we cannot directly perform the numerical experiments for larger population sizes, the steady increase in relative performance for larger number of types strongly suggests that the performance gap would continue to increase as the population size increases further.
Overall, the numerical evidence suggests that our proposed RROA algorithm is highly efficient for solving problems with large population sizes and rich type sets, significantly outperforming state-of-the-art linear programming solvers.
In section (ref) we saw how to solve the optimal assignment problem for given systematic surpluses $\Phi_{xy}$ and arbitrary idiosyncratic preference shocks $\varepsilon_{iy}$ and $\eta_{xj}$, even as the population size grows large. In this section we tackle the inverse problem: Given an observed matching and a distributional assumption on the idiosyncratic shocks, we want to recover the systematic surpluses $\Phi_{xy}$.
We assume the analyst observes a population partitioned into observable types, with $n_x$ women of type $x$ and $m_y$ men of type $y$. The data consist of an aggregate matching, that is, a matrix $\hat \mu = (\hat \mu_{xy})$ whose entries $\hat \mu_{xy}$ record the number of observed matches between women $x$ and men $y$. Given these observed matches, the number or singles of each type is therefore $\hat \mu_{x0} = n_x - \sum_y \hat \mu_{xy}$ for women $x$, and $\hat \mu_{0y} = m_y - \sum_x \hat \mu_{xy}$ for men $y$.
In this section, we will also assume that the systematic surplus follows a linear parametrization which depends on a parameter vector $\lambda$.
We assume that the surplus vectors $\phi_k$ are observable. In practice, these dimensions $k$ could include fixed effects for the types $x$ and $y$, as well as interaction terms representing for instance type proximity. As long as the basis of surplus vectors is rich enough, it will be able to reconstruct any surplus matrix $\Phi$.
In order to build our estimator of the systematic surplus, we start by considering a continuous population approximation of the assignment problem (ref). In this approximation, each individual from the finite population problem is replaced by a unit mass of individuals with the same type. Given a matrix $\Phi = (\Phi_{xy})$ of systematic surpluses, we then define the social surplus as
where $\mathcal E (\mu)$ is the entropy of matching for the aggregate matching $\mu$, that is, the maximal contribution of the idiosyncratic shocks which is consistent with $\mu$. This entropy is additively separable in each type. This is because, once the aggregate matching $\mu$ is fixed, maximizing the contribution of the idiosyncratic shocks boils down to assigning individuals within each observable type to singlehood or to partner types.
For example, consider women of type $x$. The aggregate matching vector $\mu$ tells us exactly how much mass of women $x$ must match with men $y$, and how much must remain single. The only freedom left is therefore to assign each woman $i$ of type $x$ across these options in a way that maximizes the total contribution of their idiosyncratic shocks, while respecting the aggregate masses $\mu_{xy}$. With this logic, the expression for the entropy of matching for women $x$ is
The entropy of matching $\mathcal E_y (\mu)$ for men $y$ has an analogous expression. The total entropy of matching is then obtained by adding the entropy of matching for all types, \[ \mathcal E (\mu) = \sum_x \mathcal E_x (\mu) + \sum_y \mathcal E_y (\mu). \]
In a few cases, the entropy of matching has an explicit analytical expression. In particular, when $\mathbf P_x$ and $\mathbf Q_y$ are the distributions of i.i.d.\ Gumbel preference shocks, $\mathcal E (\mu)$ is the usual entropy. \footnote{That is to say, $\mathcal E (\mu) = \sum_{xy} \mu_{xy} \ln \mu_{xy}$ up to a constant. See GalichonSalanie2022 for details.} However, for general distributions there is no simple expression for the entropy of matching. In this case, we can instead approximate it using a sample equivalent of (ref). Specifically, we draw a sample $(\varepsilon_i)$ of size $n_x$ from $\mathbf P_x$ and compute the sample equivalent of (ref) as
We similarly obtain $\widehat{\mathcal E}_y (\mu)$ by drawing a sample $(\eta_j)$ of size $m_y$ from $\mathbf Q_y$. We then define the simulated entropy of matching as $\widehat{\mathcal E} (\mu) = \sum_x \widehat{\mathcal E}_x (\mu) + \sum_y \widehat{\mathcal E}_y (\mu)$, which we can rewrite as a single maximization program:
In turn, we define the simulated social surplus $\widehat{\mathcal W} (\Phi)$ by replacing the entropy $\mathcal E (\mu)$ by its simulated counterpart $\widehat{\mathcal E} (\mu)$ in the definition (ref) of the social surplus $\mathcal W (\Phi)$. As expected, the simulated social surplus simply corresponds to the value of the optimal assignment problem associated with the simulated population.
Since we are interested in general distributions $\mathbf P_x$ and $\mathbf Q_y$, and therefore cannot rely on the entropy having an analytical expression, the simulated social surplus will play an important role in our estimation procedure. In this respect, Proposition (ref) already hints at the fact that the computation method developed for solving the optimal assignment problem in section (ref) will be useful for estimation as well.
In this section we consider that Assumption (ref) holds, so that the surplus is parametrized as $\Phi = \phi \lambda$, where $\phi = (\phi_{xyk})$ is observed by the analyst and $\lambda = (\lambda_k)$ is a vector of parameters to be estimated. From the social surplus (ref), we derive a method of moments estimator for $\lambda$ which will serve as the basis for our estimation procedure. Denote $\mu^\lambda$ the solution to (ref) when $\Phi = \phi \lambda$. The envelope theorem applied to $\mathcal W(\phi \lambda)$ yields \[ \phi^\top \nabla \mathcal W(\phi \lambda) = \phi^\top \mu^\lambda. \] It is therefore natural to consider the estimator tied to the moment conditions $\phi^\top \mu^\lambda = \phi^\top \hat \mu$. Furthermore, observe that these moment conditions are simply the first-order conditions of the convex optimization problem:
The solution to problem (ref) is thus the moment-matching estimator for $\lambda$.
As the solution to a convex optimization problem, the moment-matching estimator should in theory be straightforward to compute. Recall, however, that the social surplus function $\mathcal W (\phi \lambda)$ is itself obtained as the value of an optimization problem. Moreover, it involves the entropy of matching $\mathcal E (\mu)$ which, as we discussed above, typically does not have an analytical expression. For this reason, we will focus on a simulated moment-matching estimator, which is obtained by replacing these quantities with their simulated counterparts introduced in the previous section.
Observe that the definition of the SMM estimator in fact relies of three nested optimization problems: the outer problem in (ref), an intermediate one in the definition of $\widehat{\mathcal W} (\phi \lambda)$, and an inner one in the expression (ref) of $\widehat{\mathcal E} (\mu)$. By collapsing these three optimization problems into a single one, we obtain the following result.
Proposition (ref) states that the SMM estimator is obtained by solving a linear program which closely resembles an optimal assignment problem. Indeed, the program (ref) differs from (ref) in only two ways. First, its objective only includes the individual heterogeneity components of the utility from matching, and not the systematic utilities obtained from splitting the systematic surplus. Second, it includes one more set of constraints (those indexed by $k$), which exactly correspond to the $k$ moment-matching conditions of our estimator.
We now use the result of Proposition (ref) as the basis for a method to compute the SMM estimator $\hat \lambda$. Since the linear program (ref) closely resembles the optimal assignment problem, we can reasonably expect that a method similar to Algorithm (ref) would work as well. This is in fact the case: after doing the legwork of building the RROA algorithm for the optimal assignment problem, it now suffices to adjust that method while accounting for the modified objective and new set of constraints.
As in section (ref), we consider choice sets $Y_i$ and $X_j$ for all individuals. We then define the restricted version of the estimation problem (ref) associated with such choice sets:
By a reasoning similar to that developed in section (ref), we obtain Algorithm (ref).
Similar to Algorithm (ref), this version terminates in at most $|I| |Y| + |J| |X|$ steps.
We now present the accuracy of the estimation using the RROA algorithm. Since the structure of the problem is quite similar to that of solving the optimal assignment problem, the computational results are analogous from those of section (ref). We thus focus instead on the consistency of our estimator as the population size grows.
As in section (ref), we run numerical experiments for different sizes of the population $I$ and $J$. We fixed the size of the basis of surplus vectors to $K=5$. For each simulation, a true parameter vector $\lambda$ was simulated, as well as a basis of surplus vectors $\phi$, and finally idiosyncratic shocks drawn i.i.d.\ from $\mathcal N (0, 10^{-2})$. We then solved the optimal assignment problem associated with the surplus matrix $\Phi = \phi \lambda$ over these simulated individuals using Algorithm (ref), yielding an optimal matching. Aggregating it, we obtained a matrix $\hat \mu$ which can serve as the matrix of observed matches for the estimation.
We then estimate $\lambda$ using this data by redrawing a new set of shocks. In one case, we draw these shocks from the accurate data generating distribution $\mathcal N (0, 10^{-2})$. In another case, we draw them from a misspecified distribution, namely a Gumbel distribution with same mean and variance. We then compute our estimator of $\lambda$ by solving (ref) in those two cases. We finally compute the Normalized Root Mean Square Error (NRMSE) of our two estimators, which is a measure of the distance from the estimator to the true value of $\lambda$. We repeat this process 100 times for each value of $I,J$, and compute the average NRMSE over these 100 trials.
The results of these simulations are displayed in Figure (ref). We observe that the estimation accuracy improves steadily as population size grows, suggesting that our estimator is consistent. When the model is well-specified, that is, when the errors used in the estimation are drawn from the true normal distribution, the NRMSE eventually drops below 1% for the highest population size we investigated. When, instead, the model is misspecified and errors are drawn from a Gumbel distribution, the NRMSE stabilizes at around 7%, suggesting a persistent bias due to the misspecification.
We develop a tractable framework for the empirical analysis of matching markets with transferable utility that dispenses with the i.i.d.\ Gumbel assumption while preserving the separability structure of ChooSiow2006. On the computational side, our Repeated Restricted Optimal Assignment (RROA) algorithm solves large assignment problems orders of magnitude faster than off-the-shelf LP solvers. On the econometric side, we show how the same structure yields a simulated moment-matching estimator that remains feasible under general error distributions, and we document (i) consistency under correct specification and (ii) systematic bias when a logit error is misspecified for probit.
Future work will first investigate probit specifications in more details,with rich cross-attribute covariance (including factor structures), and quantify how correlation shapes substitution patterns and welfare relative to logit. Second, it will replicate canonical TU matching results (education, income, ethnicity) under probit and nested-logit errors to assess the robustness of estimated sorting and counterfactuals. Third, it will develop inference (standard errors, over-identification tests) for the simulated moment-matching estimator.