Search

This chapter explores the role of substitutability in economic models, particularly in the context of optimal transport and matching models. In equilibrium models with substitutability, market-clearing prices can often be recovered using coordinate update methods such as Jacobi's algorithm. We provide a detailed mathematical analysis of models with substitutability through the lens of Z- and M-functions, in particular regarding their role in ensuring the convergence of Jacobi's algorithm. The chapter proceeds by studying matching models using substitutability, first focusing on models with (imperfectly) transferable utility, and then on models with non-transferable utility. In both cases, the text reviews theoretical implications as well as computational approaches (Sinkhorn, Gale--Shapley), and highlights a practical economic application.

In this paper, we examine matching models with imperfectly transferable utility (ITU). We provide motivating examples, discuss the theoretical foundations of ITU matching models and present methods for estimating them. We also explore connected topics and provide an overview of the related literature. This paper has been submitted as a draft chapter for the Handbook of the Economics of Matching, edited by Che, Chiappori and Salani\'e.

Matching problems with linearly transferable utility (LTU) generalize the well-studied transferable utility (TU) case by relaxing the assumption that utility is transferred one-for-one within matched pairs. We show that LTU matching problems can be reframed as nonzero-sum games between two players, thus generalizing a result from von Neumann. The underlying linear programming structure of TU matching problems, however, is lost when moving to LTU. These results draw a new bridge between non-TU matching problems and the theory of bimatrix games, with consequences notably regarding the computation of stable outcomes.

For a broad class of choice and ranking models based on Luce's choice axiom, including the Bradley--Terry--Luce and Plackett--Luce models, we show that the associated maximum likelihood estimation problems are equivalent to a classic matrix balancing problem with target row and column sums. This perspective opens doors between two seemingly unrelated research areas, and allows us to unify existing algorithms in the choice modeling literature as special instances or analogs of Sinkhorn's celebrated algorithm for matrix balancing. We draw inspirations from these connections and resolve important open problems on the study of Sinkhorn's algorithm. We first prove the global linear convergence of Sinkhorn's algorithm for non-negative matrices whenever finite solutions to the matrix balancing problem exist. We characterize this global rate of convergence in terms of the algebraic connectivity of the bipartite graph constructed from data. Next, we also derive the sharp asymptotic rate of linear convergence, which generalizes a classic result of Knight (2008), but with a more explicit analysis that exploits an intrinsic orthogonality structure. To our knowledge, these are the first quantitative linear convergence results for Sinkhorn's algorithm for general non-negative matrices and positive marginals. The connections we establish in this paper between matrix balancing and choice modeling could help motivate further transmission of ideas and interesting results in both directions.

We propose new results for the existence and uniqueness of a general nonparametric and nonseparable competitive equilibrium with substitutes. These results ensure the invertibility of a general competitive system. The existing literature has focused on the uniqueness of a competitive equilibrium assuming that existence holds. We introduce three properties that our supply system must satisfy: weak substitutes, pivotal substitutes, and responsiveness. These properties are sufficient to ensure the existence of an equilibrium, thus providing the existence counterpart to Berry, Gandhi, and Haile (2013)'s uniqueness results. For two important classes of models, bipartite matching models with full assignment and discrete choice models, we show that both models can be reformulated as a competitive system such that our existence and uniqueness results can be readily applied. We also provide an algorithm to compute the unique competitive equilibrium. Furthermore, we argue that our results are particularly useful for studying imperfectly transferable utility matching models with full assignment and non-additive random utility models.

We propose monotone comparative statics results for maximizers of submodular functions, as opposed to maximizers of supermodular functions as in the classical theory put forth by Veinott, Topkis, Milgrom, and Shannon among others. We introduce matrons, a natural structure that is dual to sublattices that generalizes existing structures such as matroids and polymatroids in combinatorial optimization and M-sets in discrete convex analysis. Our monotone comparative statics result is based on a natural order on matrons, which is dual in some sense to Veinott's strong set order on sublattices. As an application, we propose a deferred acceptance algorithm that operates in the case of divisible goods, and we study its convergence properties.

This paper introduces a maximum likelihood estimator of the value of job amenities and labor productivity in a single matching market based on the observation of equilibrium matches and wages. The estimation procedure simultaneously fits both the matching patterns and the wage curve. While our estimator is suited for a wide range of assignment problems, we provide an application to the estimation of the Value of a Statistical Life using compensating wage differentials for the risk of fatal injury on the job. Using US data for 2017, we estimate the Value of Statistical Life at \$ 6.3 million (\$2017).

Galichon, Samuelson and Vernet (2022) introduced a class of problems, equilibrium flow problems, that nests several classical economic models such as bipartite matching models, minimum-cost flow problems and hedonic pricing models. We establish conditions for the existence of equilibrium prices in the equilibrium flow problem, in the process generalizing Hall's theorem., Comment: arXiv admin note: text overlap with arXiv:2207.06731

We introduce a notion of substitutability for correspondences and establish a monotone comparative static result, unifying results such as the inverse isotonicity of M-matrices, Berry, Gandhi and Haile's identification of demand systems, monotone comparative statics, and results on the structure of the core of matching games without transfers (Gale and Shapley) and with transfers (Demange and Gale). More specifically, we introduce the notions of 'unified gross substitutes' and 'nonreversingness' and show that if Q is a supply correspondence defined on a set of prices P which is a sublattice of R^N, and Q satisfies these two properties, then the set of prices yielding supply vector q is increasing (in the strong set order) in q; and it is a sublattice of P.

In this paper we propose two simple methods to estimate models of matching with transferable and separable utility introduced in Galichon and Salani\'e (2022). The first method is a minimum distance estimator that relies on the generalized entropy of matching. The second relies on a reformulation of the more special but popular Choo and Siow (2006) model; it uses generalized linear models (GLMs) with two-way fixed effects., Comment: 22 pages, 2 figures

The problem of demand inversion - a crucial step in the estimation of random utility discrete-choice models - is equivalent to the determination of stable outcomes in two-sided matching models. This equivalence applies to random utility models that are not necessarily additive, smooth, nor even invertible. Based on this equivalence, algorithms for the determination of stable matchings provide effective computational methods for estimating these models. For non-invertible models, the identified set of utility vectors is a lattice, and the matching algorithms recover sharp upper and lower bounds on the utilities. Our matching approach facilitates estimation of models that were previously difficult to estimate, such as the pure characteristics model. An empirical application to voting data from the 1999 European Parliament elections illustrates the good performance of our matching-based demand inversion algorithms in practice., Comment: Forthcoming, Review of Economic Studies

This paper provides an introduction to structural estimation methods for matching markets with transferable utility., Comment: This paper is to be published by Cambridge University Press in the volume Online and Matching-Based Market Design, edited by Federico Echenique, Nicole Immorlica, and Vijay Vazirani (2022)

We show the role that an important equation first studied by Fritz John plays in mechanism design., Comment: Dedicated to Nicholas Yannelis on his 65th birthday

We highlight the tension between stability and equality in non transferable utility matching. We consider many to one matchings and refer to the two sides of the market as students and schools. The latter have aligned preferences, which in this context means that a school's utility is the sum of its students' utilities. We show that the unique stable allocation displays extreme inequality between matched pairs.

Optimal transport has become part of the standard quantitative economics toolbox. It is the framework of choice to describe models of matching with transfers, but beyond that, it allows to: extend quantile regression; identify discrete choice models; provide new algorithms for computing the random coefficient logit model; and generalize the gravity model in trade. This paper offer a brief review of the basics of the theory, its applications to economics, and some extensions., Comment: Submitted to the proceeding of the 2020 World Congress of the Econometric Society

We investigate a model of one-to-one matching with transferable utility and general unobserved heterogeneity. Under a separability assumption that generalizes Choo and Siow (2006), we first show that the equilibrium matching maximizes a social gain function that trades off exploiting complementarities in observable characteristics and matching on unobserved characteristics. We use this result to derive simple closed-form formulae that identify the joint matching surplus and the equilibrium utilities of all participants, given any known distribution of unobserved heterogeneity. We provide efficient algorithms to compute the stable matching and to estimate parametric versions of the model. Finally, we revisit Choo and Siow's empirical application to illustrate the potential of our more general approach., Comment: 85 pages, 8 figures, 6 tables

We investigate in this paper the theory and econometrics of optimal matchings with competing criteria. The surplus from a marriage match, for instance, may depend both on the incomes and on the educations of the partners, as well as on characteristics that the analyst does not observe. Even if the surplus is complementary in incomes, and complementary in educations, imperfect correlation between income and education at the individual level implies that the social optimum must trade off matching on incomes and matching on educations. Given a flexible specification of the surplus function, we characterize under mild assumptions the properties of the set of feasible matchings and of the socially optimal matching. Then we show how data on the covariation of the types of the partners in observed matches can be used to test that the observed matches are socially optimal for this specification, and to estimate the parameters that define social preferences over matches., Comment: 62 pages, 7 figures

In this paper, we first revisit the Koenker and Bassett variational approach to (univariate) quantile regression, emphasizing its link with latent factor representations and correlation maximization problems. We then review the multivariate extension due to Carlier et al. (2016, 2017) which relates vector quantile regression to an optimal transport problem with mean independence constraints. We introduce an entropic regularization of this problem, implement a gradient descent numerical method and illustrate its feasibility on univariate and bivariate examples., Comment: 35 pages, 19 figures, 4 tables. arXiv admin note: text overlap with arXiv:1610.06833

We provide a test for the specification of a structural model without identifying assumptions. We show the equivalence of several natural formulations of correct specification, which we take as our null hypothesis. From a natural empirical version of the latter, we derive a Kolmogorov-Smirnov statistic for Choquet capacity functionals, which we use to construct our test. We derive the limiting distribution of our test statistic under the null, and show that our test is consistent against certain classes of alternatives. When the model is given in parametric form, the test can be inverted to yield confidence regions for the identified parameter set. The approach can be applied to the estimation of models with sample selection, censored observables and to games with multiple equilibria., Comment: 49 pages, 7 figures

We propose a computationally feasible way of deriving the identified features of models with multiple equilibria in pure or mixed strategies. It is shown that in the case of Shapley regular normal form games, the identified set is characterized by the inclusion of the true data distribution within the core of a Choquet capacity, which is interpreted as the generalized likelihood of the model. In turn, this inclusion is characterized by a finite set of inequalities and efficient and easily implementable combinatorial methods are described to check them. In all normal form games, the identified set is characterized in terms of the value of a submodular or convex optimization program. Efficient algorithms are then given and compared to check inclusion of a parameter in this identified set. The latter are illustrated with family bargaining games and oligopoly entry games., Comment: 54 pages, 23 figures, 2 tables

This paper contributes to the literature on hedonic models in two ways. First, it makes use of Queyranne's reformulation of a hedonic model in the discrete case as a network flow problem in order to provide a proof of existence and integrality of a hedonic equilibrium and efficient computation of hedonic prices. Second, elaborating on entropic methods developed in Galichon and Salani\'{e} (2014), this paper proposes a new identification strategy for hedonic models in a single market. This methodology allows one to introduce heterogeneities in both consumers' and producers' attributes and to recover producers' profits and consumers' utilities based on the observation of production and consumption patterns and the set of hedonic prices., Comment: 18 pages

In the context of the Beckerian theory of marriage, when men and women match on a single-dimensional index that is the weighted sum of their respective multivariate attributes, many papers in the literature have used linear canonical correlation, and related techniques, in order to estimate these weights. We argue that this estimation technique is inconsistent and suggest some solutions., Comment: 11 pages

Which and how many attributes are relevant for the sorting of agents in a matching market? This paper addresses these questions by constructing indices of mutual attractiveness that aggregate information about agents' attributes. The first k indices for agents on each side of the market provide the best approximation of the matching surplus by a k-dimensional model. The methodology is applied on a unique Dutch households survey containing information about education, height, BMI, health, attitude toward risk and personality traits of spouses., Comment: 72 pages, 5 tables

In this paper, we extend Gary Becker's empirical analysis of the marriage market to same-sex couples. Becker's theory rationalizes the well-known phenomenon of homogamy among different-sex couples: individuals mate with their likes because many characteristics, such as education, consumption behaviour, desire to nurture children, religion, etc., exhibit strong complementarities in the household production function. However, because of asymmetries in the distributions of male and female characteristics, men and women may need to marry "up" or "down" according to the relative shortage of their characteristics among the populations of men and women. Yet, among same-sex couples, this limitation does not exist as partners are drawn from the same population, and thus the theory of assortative mating would boldly predict that individuals will choose a partner with nearly identical characteristics. Empirical evidence suggests a very different picture: a robust stylized fact is that the correlation of the characteristics is in fact weaker among same-sex couples. In this paper, we build an equilibrium model of same-sex marriage market which allows for straightforward identification of the gains to marriage. We estimate the model with 2008-2012 ACS data on California and show that positive assortative mating is weaker for homosexuals than for heterosexuals with respect to age and race. Our results suggest that positive assortative mating with respect to education is stronger among lesbians, and not significantly different when comparing gay men and married different-sex couples. As regards labor market outcomes, such as hourly wages and working hours, we find some indications that the process of specialization within the household mainly applies to different-sex couples., Comment: 48 pages, 8 tables

In many economic contexts, agents from a same population team up to better exploit their human capital. In such contexts (often called "roommate matching problems"), stable matchings may fail to exist even when utility is transferable. We show that when each individual has a close substitute, a stable matching can be implemented with minimal policy intervention. Our results shed light on the stability of partnerships on the labor market. Moreover, they imply that the tools crafted in empirical studies of the marriage problem can easily be adapted to many roommate problems., Comment: 30 pages

Using results from convex analysis, we investigate a novel approach to identification and estimation of discrete choice models which we call the Mass Transport Approach (MTA). We show that the conditional choice probabilities and the choice-specific payoffs in these models are related in the sense of conjugate duality, and that the identification problem is a mass transport problem. Based on this, we propose a new two-step estimator for these models; interestingly, the first step of our estimator involves solving a linear program which is identical to the classic assignment (two-sided matching) game of Shapley and Shubik (1971). The application of convex-analytic tools to dynamic discrete choice models, and the connection with two-sided matching models, is new in the literature., Comment: 42 pages, 8 figures

We revisit Machina's local utility as a tool to analyze attitudes to multivariate risks. We show that for non-expected utility maximizers choosing between multivariate prospects, aversion to multivariate mean preserving increases in risk is equivalent to the concavity of the local utility functions, thereby generalizing Machina's result in Machina (1982). To analyze comparative risk attitudes within the multivariate extension of rank dependent expected utility of Galichon and Henry (2011), we extend Quiggin's monotone mean and utility preserving increases in risk and show that the useful characterization given in Landsberger and Meilijson (1994) still holds in the multivariate case., Comment: 18 pages

This article proposes a generalized notion of extreme multivariate dependence between two random vectors which relies on the extremality of the cross-covariance matrix between these two vectors. Using a partial ordering on the cross-covariance matrices, we also generalize the notion of positive upper dependence. We then proposes a means to quantify the strength of the dependence between two given multivariate series and to increase this strength while preserving the marginal distributions. This allows for the design of stress-tests of the dependence between two sets of financial variables, that can be useful in portfolio management or derivatives pricing., Comment: 20 pages, 8 figures

We propose a methodology for constructing confidence regions with partially identified models of general form. The region is obtained by inverting a test of internal consistency of the econometric structure. We develop a dilation bootstrap methodology to deal with sampling uncertainty without reference to the hypothesized economic structure. It requires bootstrapping the quantile process for univariate data and a novel generalization of the latter to higher dimensions. Once the dilation is chosen to control the confidence level, the unknown true distribution of the observed data can be replaced by the known empirical distribution and confidence regions can then be obtained as in Galichon and Henry (2011) and Beresteanu, Molchanov and Molinari (2011)., Comment: 32 pages, 1 figure

We characterize solutions for two-sided matching, both in the transferable and in the nontransferable-utility frameworks, using a cardinal formulation. Our approach makes the comparison of the matching models with and without transfers particularly transparent. We introduce the concept of a no-trade matching to study the role of transfers in matching. A no-trade matching is one in which the availability of transfers do not affect the outcome., Comment: 29 pages, 2 figures

This paper provides closed-form formulas for a multidimensional two-sided matching problem with transferable utility and heterogeneity in tastes. When the matching surplus is quadratic, the marginal distributions of the characteristics are normal, and when the heterogeneity in tastes is of the continuous logit type, as in Choo and Siow (J Polit Econ 114:172-201, 2006), we show that the optimal matching distribution is also jointly normal and can be computed in closed form from the model primitives. Conversely, the quadratic surplus function can be identified from the optimal matching distribution, also in closed-form. The closed-form formulas make it computationally easy to solve problems with even a very large number of matches and allow for quantitative predictions about the evolution of the solution as the technology and the characteristics of the matching populations change., Comment: 30 pages

We propose a multivariate extension of a well-known characterization by S. Kusuoka of regular and coherent risk measures as maximal correlation functionals. This involves an extension of the notion of comonotonicity to random vectors through generalized quantile functions. Moreover, we propose to replace the current law invariance, subadditivity and comonotonicity axioms by an equivalent property we call strong coherence and that we argue has more natural economic interpretation. Finally, we reformulate the computation of regular and coherent risk measures as an optimal transportation problem, for which we provide an algorithm and implementation., Comment: 33 pages, 6 figures

A general framework is given to analyze the falsifiability of economic models based on a sample of their observable components. It is shown that, when the restrictions implied by the economic theory are insufficient to identify the unknown quantities of the structure, the duality of optimal transportation with zero-one cost function delivers interpretable and operational formulations of the hypothesis of specification correctness from which tests can be constructed to falsify the model., Comment: 19 pages

We propose an easily implementable test of the validity of a set of theoretical restrictions on the relationship between economic variables, which do not necessarily identify the data generating process. The restrictions can be derived from any model of interactions, allowing censoring and multiple equilibria. When the restrictions are parameterized, the test can be inverted to yield confidence regions for partially identified parameters, thereby complementing other proposals, primarily Chernozhukov et al. [Chernozhukov, V., Hong, H., Tamer, E., 2007. Estimation and confidence regions for parameter sets in econometric models. Econometrica 75, 1243-1285]., Comment: 31 pages

We provide a geometric formulation of the problem of identification of the matching surplus function and we show how the estimation problem can be solved by the introduction of a generalized entropy function over the set of matchings., Comment: 11 pages

This paper exhibits a duality between the theory of Revealed Preference of Afriat and the housing allocation problem of Shapley and Scarf. In particular, it is shown that Afriat's theorem can be interpreted as a second welfare theorem in the housing problem. Using this duality, the revealed preference problem is connected to an optimal assignment problem, and a geometrical characterization of the rationalizability of experiment data is given. This allows in turn to give new indices of rationalizability of the data, and to define weaker notions of rationalizability, in the spirit of Afriat's efficiency index., Comment: 19 pages

I show that the structure of the firm is not neutral in respect to regulatory capital budgeted under rules which are based on the Value-at-Risk., Comment: 4 Pages

We present a class of one-to-one matching models with perfectly transferable utility. We discuss identification and inference in these separable models, and we show how their comparative statics are readily analyzed., Comment: 10 pages

We propose a multivariate extension of Yaari's dual theory of choice under risk. We show that a decision maker with a preference relation on multidimensional prospects that preserves first order stochastic dominance and satisfies comonotonic independence behaves as if evaluating prospects using a weighted sum of quantiles. Both the notions of quantiles and of comonotonicity are extended to the multivariate framework using optimal transportation maps. Finally, risk averse decision makers are characterized within this framework and their local utility functions are derived. Applications to the measurement of multi-attribute inequality are also discussed., Comment: 22 pages

We argue that models coming from a variety of fields, such as matching models and discrete choice models among others, share a common structure that we call matching function equilibria with partial assignment. This structure includes an aggregate matching function and a system of nonlinear equations. We provide a proof of existence and uniqueness of an equilibrium and propose an efficient algorithm to compute it. For a subclass of matching models, we also develop a new parameter-free approach for constructing the counterfactual matching equilibrium. It has the advantage of not requiring parametric estimation when computing counterfactuals. We use our procedure to analyze the impact of the elimination of the Social Security Student Benefit Program in 1982 on the marriage market in the United States. We estimate several candidate models from our general class of matching functions and select the best fitting model using information based criterion.

This paper surveys recent applications of methods from the theory of optimal transport to econometric problems.

In this paper, we describe a novel iterative procedure called SISTA to learn the underlying cost in optimal transport problems. SISTA is a hybrid between two classical methods, coordinate descent ("S"-inkhorn) and proximal gradient descent ("ISTA"). It alternates between a phase of exact minimization over the transport potentials and a phase of proximal gradient descent over the parameters of the transport cost. We prove that this method converges linearly, and we illustrate on simulated examples that it is significantly faster than both coordinate descent and ISTA. We apply it to estimating a model of migration, which predicts the flow of migrants using country-specific characteristics and pairwise measures of dissimilarity between countries. This application demonstrates the effectiveness of machine learning in quantitative social sciences.

We give a two-line proof of a long-standing conjecture of Ben-Akiva and Lerman (1985) regarding the random utility representation of the nested logit model, thus providing a renewed and straightforward textbook treatment of that model. As an application, we provide a closed-form formula for the correlation between two Fr\'echet random variables coupled by a Gumbel copula.

This article presents a set of tools for the modeling of a spatial allocation problem in a large geographic market and gives examples of applications. In our settings, the market is described by a network that maps the cost of travel between each pair of adjacent locations. Two types of agents are located at the nodes of this network. The buyers choose the most competitive sellers depending on their prices and the cost to reach them. Their utility is assumed additive in both these quantities. Each seller, taking as given other sellers prices, sets her own price to have a demand equal to the one we observed. We give a linear programming formulation for the equilibrium conditions. After formally introducing our model we apply it on two examples: prices offered by petrol stations and quality of services provided by maternity wards. These examples illustrate the applicability of our model to aggregate demand, rank prices and estimate cost structure over the network. We insist on the possibility of applications to large scale data sets using modern linear programming solvers such as Gurobi. In addition to this paper we released a R toolbox to implement our results and an online tutorial (http://optimalnetwork.github.io)

This paper derives conditions under which preferences and technology are nonparametrically identified in hedonic equilibrium models, where products are differentiated along more than one dimension and agents are characterized by several dimensions of unobserved heterogeneity. With products differentiated along a quality index and agents characterized by scalar unobserved heterogeneity, single crossing conditions on preferences and technology provide identifying restrictions in Ekeland, Heckman and Nesheim (2004) and Heckman, Matzkin and Nesheim (2010). We develop similar shape restrictions in the multi-attribute case. These shape restrictions, which are based on optimal transport theory and generalized convexity, allow us to identify preferences for goods differentiated along multiple dimensions, from the observation of a single market. We thereby derive nonparametric identification results for nonseparable simultaneous equations and multi-attribute hedonic equilibrium models with (possibly) multiple dimensions of unobserved heterogeneity. One of our results is a proof of absolute continuity of the distribution of endogenously traded qualities, which is of independent interest., Comment: Journal of Political Economy (2021)

In this paper, we address the problem of estimating transport surplus (a.k.a. matching affinity) in high dimensional optimal transport problems. Classical optimal transport theory specifies the matching affinity and determines the optimal joint distribution. In contrast, we study the inverse problem of estimating matching affinity based on the observation of the joint distribution, using an entropic regularization of the problem. To accommodate high dimensionality of the data, we propose a novel method that incorporates a nuclear norm regularization which effectively enforces a rank constraint on the affinity matrix. The low-rank matrix estimated in this way reveals the main factors which are relevant for matching.

This paper studies vector quantile regression (VQR), which is a way to model the dependence of a random vector of interest with respect to a vector of explanatory variables so to capture the whole conditional distribution, and not only the conditional mean. The problem of vector quantile regression is formulated as an optimal transport problem subject to an additional mean-independence condition. This paper provides a new set of results on VQR beyond the case with correct specification which had been the focus of previous work. First, we show that even under misspecification, the VQR problem still has a solution which provides a general representation of the conditional dependence between random vectors. Second, we provide a detailed comparison with the classical approach of Koenker and Bassett in the case when the dependent variable is univariate and we show that in that case, VQR is equivalent to classical quantile regression with an additional monotonicity constraint.