Equilibrium transport

Description:

The classical theory of optimal transport relies on a very strong basic assumption: that the utilities should be quasi linear in payments, that is, everybody has a valuation expressed in the same monetary unit, which can be transferred without losses. In that case, if the firm pays the worker an extra dollar, the utility of the firm is decreased by one dollar, and the utility of the worker is increased by one dollar. That assumption is, of course, very strong as various nonlinearities may arise in practice; these might be induced by taxes, by regulations such as price caps, by risk aversion, or by other various inefficiencies. Removing this strong assumption requires moving beyond optimal transport theory, and moving into what I call “Equilibrium transport theory”, although this terminology is not standard; economists prefer “matching with imperfectly transferable utility”, and mathematicians usually refer to “prescribed Jacobians equations”. The problem is intrinsically an equilibrium problem, as opposed to an optimization problem; in fact, it has a natural formulation in terms of a nonlinear complementarity problem (NCP). Because this is no longer a linear programming problem, a large share of the insights of optimal transport — in particular, duality theory and everything that relates to optimization — no longer applies. However, an equally large part — in particular, the lattice structure and everything that relates to isotonicity — still applies. In work with Kominers and Weber, we have shown that this is the right framework to unify collective models of the households with matching models, and we provide a key technical tool to handle these, the distance-to-frontier (DTF) function; we also provide algorithms of the Jacobi type to compute an equilibrium in a regularized version of these models. In work with Hsieh, we investigate the case when there are no profitable transfers whatsoever; in this case, it may be necessary for either side of the market to destroy utility fully inefficiently but only for the purposes of sustaining a decentralized allocation. In work with Dupuy, Jaffe and Kominers, we analyse a model of matching with taxes. In the case of a linear tax, the models reformulates as an optimal transport model, which is no longer the case under nonlinear taxes.
A brief description of the equilibrium transport problem can be found in the concluding chapter of my book, Optimal transport methods in economics, chap. 10.4.

My co-authors:

Arnaud Dupuy, Yu-Wei Hsieh, Sonia Jaffe, Scott Kominers, and Simon Weber.

Presentation slides:

Presentation slides can be found here.

Code:

See transfers routines of the TraME library.

References:

Alfred Galichon, Scott Kominers, and Simon Weber (2015). The Nonlinear Bernstein-Schrodinger Equation in Economics. Proceedings of the Second Conference “Geometric Science of Information”, F. Nielsen and F. Barbaresco, eds. Springer Lecture Notes in Computer Sciences 9389, pp. 51-59. Available here.
Alfred Galichon, Scott Kominers, and Simon Weber (2017). Costly Concessions: An Empirical Framework for Matching with Imperfectly Transferable Utility. Revision requested (2nd round), Journal of Political Economy. Available here.
Alfred Galichon, and Yu-Wei Hsieh (2017). A theory of decentralized matching markets without transfers, with an application to surge pricing. Under review. Available here.
Arnaud Dupuy, Alfred Galichon, Sonia Jaffe, and Scott Kominers (2017). Taxation in matching markets. Available here.

Optimal martingale transport

Description:

Optimal transport theory has important applications in finance, more specifically in option pricing theory. Financial derivatives may depend on several underlying assets; this is the case of spread options, for instance, or of basket options. The standard Black-Scholes-Merton theory of option pricing says that if there is a liquid market of vanilla options on a single underlying, then the risk-neutral distribution of the underlying can be recovered from the option prices; and we can therefore obtain a unique price associated with any more complicated single-underlying option. However, in the case of an option on two underlying, the market prices on the single-name options do not imply the joint distribution of two such assets, and one can then define no-arbitrage bounds, which corresponds to the cheapest and most expensive prices of the option that is consistent with the market. These bounds formulate as a Monge-Kantorovich problem, and the dual problem ensures that they correspond to the most expensive sub-replicating (lower bound) and the cheapest super-replicating portfolio (upper bound).
In a number of cases, the two underlying quantities are not the value of two assets at the same date in time, but the price of the same asset at two different dates in the future. There is then an important further restriction on the joint distribution of these assets: they should be the margins of a martingale. Computing the bounds of the option prices leads then to a variant of Monge-Kantorovich theory, where one looks the optimal coupling that is a martingale. This further constraint yields a supplementary term in the dual formulation, which has an interesting interpretation in terms of sub/super-replicating portfolio: the portfolio is not only made of calls and puts at the two maturities (static hedging), but also allows for rebalancing at the earlier maturity, allowing for dynamic hedging.
Moving beyond the static problem, there are interesting dynamic formulation of the problem. In particular, one may consider among the set of semi-martingales that start at a given distribution and end up at a given distribution, those who minimize a the time integral of the expectation of a Lagrangian that depends on the drift and diffusions parameters. This nicely extends the Benamou-Brenier dynamic formulation of optimal transport, and can provide interesting insights on particular solutions to the Skorohod embedding problem.

My co-authors:

Guillaume Carlier, Pierre Henry-Labordere, Nizar Touzi.

Presentation slides:

Presentation slides can be found here.

References:

Guillaume Carlier, and Alfred Galichon (2012). Exponential convergence for a convexifying equation (2012). Control, Optimization and Calculus of Variations 18(3), pp. 611–620. Available here.
Pierre Henry-Labordere, Alfred Galichon, and Nizar Touzi (2014). A stochastic control approach to no-arbitrage bounds given marginals, with an application to lookback options. Annals of Applied Probability 24 (1), pp. 312-336. Available here.

Inverse optimal transport

Description:

Inverse optimal transport is a general method for estimating matching models. Economic agents match because the output they generate together is often higher than the sum of the outputs they would generate individually. This occurs in family economics (couple formation), labour economics (employment), industrial organizations (industrial alliances), finance (mergers), international trade (trade flows), school choice (class formation), among other fields. Complementarities are crucial: the economic approach to marriage, for instance, assumes that two individual decide to match only if the utility they get together if they team up is greater than the utility they get staying single. Matching patterns, i.e. who matches with whom, will be determined by (i) the strength of complementarities, and (ii) by the relative scarcity of a given characteristics on which matching occurs.
The empirical estimation of matching models has had a distinguished tradition in econometrics since the 1950’s with early work by Tinbergen and others, but was revived in the mid­-2000s in the field of family economics by a landmark paper by Choo and Siow on the identification of the “gains from marriage” in a matching model with transferable utility and logit-type heterogeneities. In somewhat general terms, the question is: given the observation of matching patterns (frequency of matches between each pair of types) and sometimes supplementary information such as observations on the surplus generated, or on the transfers between partners, what surplus functions are compatible with the observations?
Choo and Siow’s paper opened up a avenue of possibilities for the estimation of matching models, which we have pursued relentlessly. In initial work with Salanié, we showed that Choo and Siow’s framework can be formulated as a regularized optimal transport problem and we have provided a general estimation framework for the estimation of matching models with any separable heterogeneity structure using a moments-based procedure. With Dupuy, we have introduced affinity estimation which offers a tractable parameterization of the matching surplus function, in a setting which is flexible enough to accommodate both discrete and continuous observable characteristics. Affinity estimation consists of taking a bi-linear parameterization of the surplus function such that the terms of the matrix of complementarities (“affinity matrix”) indicate the amount of attraction (positive or negative) between a pair of characteristics of two agents to be matched. We have shown that the equilibrium conditions in this model can be expressed a gravity equation, so that one can use an approach based on Poisson pseudo-maximum likelihood (PPML) with two-way fixed effects, as is done in the trade literature. This allows us to estimate the affinity matrix which indicates the characteristics on which the sorting primarily occurs. While the classical setting of affinity estimation is bipartite (i.e. the matched partners are drawn from separate populations: men and women, workers and firms, buyers and sellers), it can be extended to the unipartite setting, as we have shown in work with Ciscato and Goussé. This is of particular interest in family economics as it permits to use affinity estimation to analyze same-sex unions. In practice, one often encounters cases when agents’ individual characteristics are high dimensional. In ongoing work with Dupuy and Sun we address this problem by rank-regularization techniques coupled with a cross validation criterion. With Carlier, Dupuy and Sun, we proposed the SISTA algorithm, which combines Sinkhorn steps and gradient descent steps.

My co-authors:

Guillaume Carlier, Edoardo Ciscato, Arnaud Dupuy, Marion Goussé, Bernard Salanié, and Yifei Sun.

Presentation slides:

Slides can be found here.

Code:

See models routines of the TraME library.

References:

Alfred Galichon, and Bernard Salanié (2012). Cupid’s Invisible Hand: Social Surplus and Identification in Matching Models. Revision requested (2nd round), Review of Economic Studies. Available here.
Arnaud Dupuy, and Alfred Galichon (2014). Personality traits and the marriage market. Journal of Political Economy 122 (6), pp. 1271-1319. Winner of the 2015 Edmond Malinvaud prize. Available here.
Arnaud Dupuy, and Alfred Galichon (2015). Canonical Correlation and Assortative Matching: A Remark. Annals of Economics and Statistics 119-120, pp. 375—383. Available here.
Edoardo Ciscato, Alfred Galichon, and Marion Goussé (2017). Like Attract Like? A Structural Comparison of Homogamy Across Same-Sex and Different-Sex Households. Revision requested, Journal of Political Economy. Available here.
Arnaud Dupuy, Alfred Galichon, and Yifei Sun (2017). Estimating matching affinity matrix under low-rank constraints. Available here.

Vector quantiles

Description:

In dimension one, the quantile is the inverse of the cumulative distribution function. Quantiles are extremely useful objects because they fully characterize the distribution of an outcome, and they allow to provide directly a number of statistics of interest such as the median, the extremes, the deciles, etc. They allow to express maximal dependence between two random variables (comonotonicity) and are used in decision theory (rank-dependent expected utility); in finance (value-at-risk and Tail VaR); in microeconomic theory (efficient risksharing); in macroeconomics (inequality); in biometric (growth charts) among other disciplines. Quantile regression, pioneered by Roger Koenker, allows to model the dependence of a outcome with respect to a set of explanatory variables in a very flexible way, and has become extremely popular in econometrics.
The classical definition of quantiles based on the cumulative distribution function, however, does not lend itself well to a multivariate extension, and given the number of applications of the notion of quantiles, many authors have suggested various proposals.
We have proposed a novel definition of multivariate quantiles called “Vector quantiles” based on optimal transport. The idea is that instead of viewing the quantile map as the inverse of the cumulative distribution function, it is more fruitful to view it as the map that rescales a distribution of interest to the uniform distribution over [0,1] in the least possible distortive way, in the sense that the average squared distance between an outcome and its preimage by the map should be minimized. While equivalent to the classical definition in the univariate case, this definition lends itself to a natural multivariate generalization using Monge-Kantorovich theory. We thus define the multivariate quantile map as the one that attains the L2-Wasserstein distance, which is known in the optimal transport literature as Brenier’s map. With Carlier and Santambrogio, we gave a precise connection between vector quantiles and a celebrated earlier proposal by Rosenblatt. We have shown that many of the desirable properties and uses of univariate quantiles extend to the multivariate case if using our definition. With Ekeland and Henry, we have shown that this notion is a multivariate analog of the notion of Tail VaR used in finance. With Henry, we have shown that it allows to construct an extension of Yaari’s rank-dependent utility in decision theory, and have provided an axiomatization for it. With Carlier and Dana, we have shown that this notion extends Landsberger and Meilijson’s celebrated characterization of efficient risksharing arrangements. With Charpentier and Henry, we have shown the connection with Machina’s theory of local utility. With Carlier and Chernozhukov, we have shown that Koenker’s quantile regression can be naturally extended to the case when the dependent variable is multivariate if one adopts our definition of multivariate quantile. With Chernozhukov, Hallin and Henry we have defined empirical vector quantiles and have studied their consistency.
A number of challenges remains. Among these, an empirical process theory for multivariate quantiles (extending the univariate theory of the empirical quantile process) is the obvious next step, although this is highly non-trivial. Invariance issues are also interesting and challenging questions. Finally, while the link with other multivariate quantiles (such as Rosenblatt’s) is by now well understood, the link with other related concepts, such as Tukey’s halfspace depth, remains to be explored.
A brief description of vector quantiles and vector quantile regression can be found in my book, Optimal transport methods in economics, chap. 9.4-9.5.

My co-authors:

Guillaume Carlier, Arthur Charpentier, Victor Chernozhukov, Rose-Anne Dana, Ivar Ekeland, Marc Hallin, Marc Henry, and Filippo Santambrogio.

Presentation slides:

A presentation on vector quantile regression can be found here.

Code:

The code for vector quantile regression can be found in the following Github repository.

References:

Guillaume Carlier, Alfred Galichon, and Filippo Santambrogio (2010). From Knothe’s transport to Brenier’s map. SIAM Journal on Mathematical Analysis 41, Issue 6, pp. 2554-2576. Available here.
Ivar Ekeland, Alfred Galichon, and Marc Henry (2012). Comonotonic measures of multivariate risks. Mathematical Finance 22 (1), pp. 109-132. Available here.
Alfred Galichon and Marc Henry (2012). Dual theory of choice with multivariate risks. Journal of Economic Theory 147(4), pp. 1501–1516. Available here.
Guillaume Carlier, Rose-Anne Dana, and Alfred Galichon (2012). Pareto efficiency for the concave order and multivariate comonotonicity. Journal of Economic Theory 147(1), pp. 207–229. Available here.
Arthur Charpentier, Alfred Galichon, and Marc Henry (2016). Local utility and risk aversion. Mathematics of Operations Research 41(2), pp. 466—476.
Guillaume Carlier, Victor Chernozhukov, and Alfred Galichon (2016). Vector quantile regression: an optimal transport approach.Annals of Statistics 44 (3), pp. 1165–1192. Available here. Software available here.
Victor Chernozhukov, Alfred Galichon, Marc Hallin, and Marc Henry (2016). Monge-Kantorovich Depth, Quantiles, Ranks and Signs. Annals of Statistics. Available here.
Guillaume Carlier, Victor Chernozhukov, and Alfred Galichon (2017). Vector quantile regression beyond correct specification. Journal of Multivariate Analysis. Available here.

The mass transport approach to demand inversion in multinomial choice models

Description:

Multinomial choice models constitute a fundamental toolbox of microeconomic analysis. Although this classification is a bit arbitrary, they usually divide into discrete choice models, in which the choice set is finite (e.g. a consuming choosing a model of car), and hedonic models, in which the choice set is continuous (e.g. a consumer choosing the quality of a wine). An important problem in these models is the problem of demand inversion, namely how to recover the payoffs associated with each alternative based on the corresponding market shares. We have developed a methodology called the “mass transport approach” to perform demand inversion in choice models using matching theory.
Multinomial choice models are usually thought of as conceptually distinct from matching models. The traditional wisdom is that matching models are “two-sided” (on the labor market, workers and firms choose each other), while demand models are “one-sided” (consumers choose yoghurts, but yoghurts don’t choose consumers). In work with Bonnet, O’Hara and Shum, we build on the findings of earlier papers with Salanié and with Chiong and Shum to show that this distinction has no bite, and that in fact, a model where consumers choose yoghurts is observationally equivalent to a (hypothetical) dual model where yoghurts choose consumers, or to a model where consumers “match” with yoghurts. At the heart of the “mass transport” approach to demand inversion lies our equivalence theorem: identifying the systematic payoffs in a multinomial choice model is equivalent to the determining a stable pair in a matching model. We use this reformulation to make use of matching theory in order to provide new theoretical results and new computational techniques in demand models. This finding gives rise to a novel class of efficient computational algorithms to invert multinomial choice models, that are based on matching algorithms. In ongoing work with Chernozhukov, Henry and Pass, we extend these methods to the case when the alternative are continuous, i.e. hedonic models.
See a brief description in my book, Optimal transport methods in economics, chap. 9.2.

My co-authors:

Odran Bonnet, Khai Chiong, Victor Chernozhukov, Marc Henry, Keith O’Hara, Brendan Pass, and Bernard Salanié.

Presentation slides:

Available here.

Code:

See arum routines of the TraME library.

References:

Alfred Galichon, and Bernard Salanié (2012). Cupid’s Invisible Hand: Social Surplus and Identification in Matching Models. Revision requested (2nd round), Review of Economic Studies. Available here.
Khai Chiong, Alfred Galichon, and Matt Shum (2016). Duality in dynamic discrete choice models. Quantitative Economics 7(1), pp. 83—115. Available here.
Odran Bonnet, Alfred Galichon, Keith O’Hara, and Matt Shum (2017). Yogurts choose consumers? Identification of Random Utility Models via Two-Sided Matching. Available here.
Victor Chernozhukov, Alfred Galichon, Marc Henry, and Brendan Pass (2017). Single market nonparametric identification of multi-attribute hedonic equilibrium models. Available here.