July 23, 2019


July-December 2014
Thematic Program on
Variational Problems in Physics, Economics and Geometry

September 15-19, 2014

Pierre-Andre Chiappori (Columbia)
Alfred Galichon (Ecole Polytechnique)
Robert McCann (Toronto)
Xianwen Shi (Toronto)

Conference Programme

MONDAY Sept 15

Roberto Cominetti (Universidad de Chile)
Recursive Optimal Transport and Fixed-Point Iterations for Nonexpansive Maps

A popular method to compute a fixed point for a non-expansive map $T:C\to C$ is the successive average iteration originally proposed by Krasnoselskii and Mann $$x_{n+1}=(1-\alpha_{n+1})x_n+\alpha_{n+1}Tx_n. \nleq (KM)$$ We establish an unexpected connection between $(KM)$ and optimal transport through a recursive formula that estimates the distance between iterates $\|x_m-x_n\|\leq d_{mn}$. The recursive optimal transport $d_{mn}$ induces a metric on the integers that allows to characterize the rate of convergence of $(KM)$.As a result, we completely settle Baillon and Bruck's conjecture for the rate of convergence of the fixed point residuals, namely, for every non-expansive map in any normed space the following estimate holds with $\kappa=1/\sqrt{\pi}$ $$\|x_n-Tx_n\|\leq \kappa\frac{\mbox{diam}({}C)}{\sqrt{\sum_{i=1}^n\alpha_k(1-\alpha_k)}}.$$ The analysis exploits another surprising connection with discrete probability and combinatorics, related to the Gambler's ruin for a sum of non-homogeneous Bernoulli trials. We will discuss theextent to which the constant $\kappa=1/\sqrt{\pi}$ is sharp.

Deniz Dizdar (University of Montréal)
Two-sided investments and matching with multi-dimensional types and attributes

I study settings in which heterogeneous buyers and sellers, characterized by cost types, must invest in attributes before they compete for partners in a frictionless, continuum assignment market. I define Cole, Mailath and Postlewaite's (2001a) notion of ex-post contracting equilibrium in a general assignment game framework. Ex-ante efficient investment and matching can always be supported in equilibrium.

The main part of the paper sheds light on what enables and what precludes coordination failures resulting in mismatch of agents (from an ex-ante perspective) and/or pairwise inefficient investments. A kind of technological multiplicity is the key source of potential inefficiencies. Absence of technological multiplicity rules out pairwise inefficient investments, and it heavily constrains mismatch in multi-dimensional environments with differentiated agents. An example with simultaneous under -and over- investment shows that even extreme exogenous heterogeneity may not suffice to rule out inefficient equilibria in environments with technological multiplicity.


Guillaume Carlier (Paris)
A Monge-Kantorovich approach to multivariate quantile regression

The aim of this talk is to present a way to extend the quantile regression method of Koenker and Bassett to the multivariate setting. A variant of the classical optimal transport problem with an additional mean-independence constraint plays a crucial role in the analysis. We shall also revisit the classical univariate case in the light of this variational point of view. Joint work with Victor Chernozhukov (MIT) and Alfred Galichon (Sc. Po, Paris).

Ismael Mourifié (Toronto)
Marriage matching with peer effects

Co-Authors:Aloysius Siow

This paper proposes a new static empirical marriage matching function (MMF), the Log Odds MMF. A special case includes marriage matching with peer effects. It also includes the Choo Siow frictionless transferable utility MMF, a MMF with frictional transfers, the Dagsvik Manziel non-transferable utility MMF and Chiappori, Salanie and Weiss MMF. All these cases are empirically testable. Properties of this Log Odds MMF are presented. A new existence and uniqueness proof of the marriage distribution is provided.

Scott Kominers (Harvard)
Generalized Matching Market Design

In recent years, new theoretical discoveries have shown how to generalize two-sided matching algorithms to incorporate contract negotiation and complex market structures. In this talk, I survey these "generalized matching" results, highlighting places where deeper mathematics might be useful in improving our understanding. Specific topics include weakend substitutability conditions, fixed-point characterizations of stable outcomes, and solution concept correspondences.



Eduardo Azevedo (University of Pennsylvania)
Perfect Competition in Markets with Adverse Selection (paper)

Policy makers and economists typically consider adverse selection an important problem in many markets, such as insurance where buyers can be more likely to need more insurance. Governments typically respond to this perceived problem with complicated regulations, which include mandates, but also interventions like subsidies, risk adjustment, and regulation of contract characteristics. Even though these complex interventions seem to be aimed at affecting product characteristics, most economic models are quite limited in determining what types of contracts arise in different markets.

In this talk I will present a model of markets with adverse selection where the characteristics of offered products are determined endogenously, and that allows for realistic patterns of heterogeneity between consumers. I will focus on what equilibrium in this type of market looks like. From a theoretical perspective, this is related to the literatures on "multidimensional screening," "competitive screening," and "signaling games." Towards the end of the talk I will discuss optimal government interventions and their the relationship to policies used in practice. This is joint work with Daniel Gottlieb.

Maria Gualdani (George Washington University)
A price formation model: microscopic derivation, global well-posedness and open problems

In financial markets, the evolution of prices is influenced by the trading system and the nature of players.
In 2006 J.M. Lasry and P.L. Lions introduced in the contest of Mean Field Games a partial differential equations based model, where the price of the good enters in the model as a free boundary. Since then this model has attracted a lot of attention due to its original mathematical structure and interesting open problems.
In this talk we survey the existing literature, with particular attention to microscopic derivation and global well-posedness.

Nizar Touzi (Ecole Polytechnique)

Sonia Jaffe (Harvard University)
Matching Markets with Taxation of Transfers
Coauthors: Scott Duke Kominers

We analyze the effects of taxation on outcomes in matching markets. Taxes can make inefficient outcomes stable by causing workers to prefer firms from which they receive high idiosyncratic match utility, but at which they are less productive. In general, efficiency can be non-monotonic in the tax. However, when agents on one side of the market refuse to match without a positive transfer (wage), increasing taxes always decreases efficiency. In addition to providing a continuous link between canonical models of matching with and without transfers, our model highlights a cost of taxation that does not appear to have been examined previously.

Saeedeh Ketabi (University of Isfahan)
The network expansion problem with non-linear costs
Coauthors: Aashtiani, H. Z., Sharif University of Technology

In this paper the network expansion problem is studied, where the new links’ capacities are designed, without improving the existing link facilities. In this problem the summation of two costs, the performance costs of existing and new links and the construction costs of the new links are minimized. Generally, the performance cost is a convex function of the flow and the construction cost is a concave function of the new capacity. Therefore the network expansion problem is to find the minimum of the difference of convex functions over the linear constraints. Tuy in 1987 proposed a method for the general case; in this method the problem is transformed to a concave minimization over a convex feasible set, firstly. Then at each iteration a relaxation of the problem is solved by the branch and bound type method. In this paper the implementing of the method for efficient solving the network expansion problem, is discussed and the result is presented.

Alpár Richárd Mészáros (University of Paris-Sud)
Variational approach to mean field games with density constraints

The introduction of the recent theory of mean field games is due to J.-M. Lasry and P.-L. Lions. The basic idea behind this theory is to use the mean field approach from statistical physics to study differential games where the number of players is tending to infinity.
In this talk we investigate some mean field game models under density constraints. These constraints are very natural to suppose because in many crowd motion models (with and without strategy in the movement) one wants to avoid the congestion.
Our approach is a variational one, having its roots in the so-called Benamou-Brenier dynamic formulation of optimal transportation. Similar variational models for mean field games without density constraints were studied recently by P. Cardaliaguet and his coauthors. This talk is based on several ongoing joint works with F. Santambrogio (University of Paris-Sud), F. J. Silva (University of Limoges) and P. Cardaliaguet (University of Paris-Dauphine).

Monica G Cojocaru (University of Guelph)
Equilibrium in competitive help models in biological markets

Coauthors: Erin Wild, Univ. of Guelph

In this talk we show the emergence of equilibrium in models of help competition between biological individuals. The model has been introduced a few years back in the sociological context, but we give here a full mathematical analysis of it pointing out existence and properties of its equilibrium states in a dynamical system context. We use both game theory, variational inequalities and agent-based models to derive a complete picture of the model. Last but not least, we give a flavour of how competitive help can be placed in the context of a generalized Nash game.

Brendan Pass (University of Alberta)
Uniqueness and purity in multi-agent matching problems
Coauthors: Young-Heon Kim

This talk is focused on multi-marginal optimal transport, the mathematical theory associated with multi-agent matching problems under transferable utility; that is, matching problems where more than two agents come together to form teams.
In the classical, two agent setting, the generalized Spence-Mirrlees condition ensures uniqueness and purity of stable matches, under a regularity condition on the first marginal. I will present an analogous condition, developed jointly with Y.-H. Kim, which ensures purity and uniqueness in the multi-agent framework. This condition is much stronger than its two marginal counterpart, as I will attempt to illustrate with a handful of examples.


Oksana Pichugina (Brock University)
Functional Representations of Combinatorial Sets and Applications in Optimization

Coauthors: Sergey Yakovlev (Ukraine)

We consider a class of optimization problems on combinatorial sets whose images in the Euclidean space are inscribed into a sphere. This class includes Boolean Programming, Optimization over permutations and other combinatorial configurations. It has many real-world applications.

There are presented different representations of these combinatorial sets as intersection of continuum ones such as intersection of: a) a sphere and a combinatorial polyhedron, b) two or more surfaces.

These representations are used in several original approaches to solving this class problems reducing the initial discrete problem to series of continuous ones. Approach 1 - polyhedral-spherical method for solving combinatorial problems, which uses a continuous representation of the set as an intersection of a sphere and a combinatorial polyhedron as well as an analytical description of the polyhedron. Approach 2 - Penalty Method applicable to the case of: a) differentiable target function, b) availability of strict differentiable functional representation of the combinatorial set and an explicit solution of a linear problem over the set.

It should be noted that in these approaches the Convex Optimization is not always applicable, but in computational algorithms we can essentially use the fact that all functions of functional representations of discrete sets inscribed into a sphere can be considered as convex since for any function defined over such a set there is a convex extension of the function from the set into Euclidean space.

Hanzhe Zhang
(University of Chicago)
Stochastic Investments and Bidimensional Matching: Explaining Marriage Age Patterns and the College Gender Gap

I construct an equilibrium investment-and-matching framework in which people first make investments that yield stochastic returns and then match based on men and women's realized wage and women's reproductive fitness. The framework allows me to expand static marriage market analyses to simultaneously study marital, educational, and occupational choices. Namely, the model explains the evolution of the relationships between marriage age and personal income. The recent global phenomenon that more women than men go to college naturally arises in the unique equilibrium.



Alfred Galichon (Center for Economic Policy Research )
Connecting matching models with and without Transferable Utility, 1 , 2

This lecture aims at providing an empirical framework for matching models with heterogeneity in tastes and general transfer technologies. It is organized in two parts: 1. Generalized Entropy of Choice and Capacity-constrained Discrete Choice. We first revisit the literature on random utility models by emphasizing the role of a proper generalization of the notion of entropy, defined using Legendre transforms. The duality between the selection model and the assignment model follows, as well as the duality between the equilibrium characterization problem and the identification problem. 2. Equilibrium characterization and identification in matching models. The previous theory is then applied to characterize equilibrium and provide identification in matching models with imperfectly transferable utility (ITU), including as special cases both the transferable utility (TU) and nontransferable utility (NTU) models.



Lars Nesheim (University College London)

Minyi Huang (Carleton)

Yeon-Koo Che (Columbia University)(Paper)
Efficiency and Stability in Large Matching Markets

Authors: Yeon-Koo Che (Columbia University), and Olivier Tercieux (Paris School of Economics)

We study efficient and stable mechanisms in matching markets when the number of agents is large and individuals' preferences are drawn randomly from a class of distributions allowing for both common value and idiosyncratic components. In this context, as the market grows large, all Pareto efficient mechanisms (including top trading cycles, serial dictatorship, and their randomized variants) are asymptotically payoff equivalent (``up to the renaming of the agents''), yielding utilitarian upper bound in the limit. If objects' priorities are also randomly drawn but agents' common values for objects are heterogenous, then well-known mechanisms such as deferred acceptance and top trading cycle mechanisms fail either efficiency or stability even in the asymptotic sense. We propose a new mechanism is asymptotically efficient, asymptotically stable and asymptotically incentive compatible.

Keywords: Large matching market, Pareto efficiency, Stability, Fairness, Payoff equivalence, Random graph theory.

Fuhito Kojima (Stanford University)
Stable Matching in Large Economies

Complementarities of preferences have been known to jeopardize the stability of two-sided matching markets, yet they are a pervasive feature in many matching markets. We revisit the stability issue with such preferences in a large market. Workers have preferences over firms while firms have preferences over distributions of workers and may exhibit complementarity. We demonstrate that if each firm's choice changes continuously as the set of available workers changes, then there exists a stable matching even with complementarity. Building on this result, we show that there exists an approximately stable matching in any large finite economy. We apply our analysis to show the existence of stable matchings in probabilistic and time-share matching models with a finite number of firms and workers.

Qingmin Liu (Columbia University)

Gabriel Penagos (Universidad Javeriana)
A Martingale Approach for Portfolio Allocation with Stochastic Volatility and Jumps

A market model composed of a risky asset and a riskless bond is
considered. The risky security satisfies a stochastic differential equation which
includes a jump component with lognormal amplitude change. Volatility is
assumed stochastic and following a mean reverting process. Investors objective
is to maximize the expected utility on terminal wealth, hence, the optimal
allocation rule is derived through the use of martingale and duality techniques.
Weights on assets are found along with the expressions for market price of risk,
market price of volatility risk and the market price of jump risk. The results
are applied to market data, therefore, the conditional characteristic function
associated with the market model is calculated and the first four cumulants
are derived. Exact expressions for the mean, standard deviation, skewness and
excess kurtosis are obtained. Model parameters are estimated by means of
a distance minimization using a discretization of the empirical characteristic

Duality techniques means that I change the primal problem into a dual problem using the Legendre -
Fenchel transform (convex conjugate) in order to find the Equivalent Martingale Measure. The, now, stochastic control problem (a PDE given by the infinitesimal generator) is to find the optimal control (price of risk) when including jumps (apart from brownian motion).

FRIDAY Sept 19

Alexander Kolesnikov (Higher School of Economics)

Arnaud Dupuy (CEPS/INSTEAD)
Migration in China: To work or to wed?
Authors: Arnaud Dupuy, Alfred Galichon, and Liping Zhao

Why do people migrate? In this paper we study the trade-o s between migrating to work and migrating to wed. To this aim, we develop a marriage matching model in which men and women, are initially distributed over various locations, i.e. were born and raised in various locations. To each location corresponds a marriage market and a labor market. Men and women can choose to stay at their current location and enter the local marriage market and labor market or migrate to a diff erent location and enter the marriage market and labor market at that location. Migration induces additional costs but may also generate benefi ts in the form of better labor market perspectives in the destination's labor market. These costs and benefi ts are specifi c to each man and each woman. Our model encompasses the classical matching model a la Becker (1973) and Shapley and Shubik (1972) with the hedonic model a la Rosen (1974). We bring the model to the data and use data from China. Preliminary results indicate that improving mobility may lead to large welfare gains.

Marc Henry (Pennsylvania State University)
Identifying multi-attribute hedonic models

Authors: Victor Chernozhukov, Alfred Galichon and Marc Henry
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. We develop similar shape restrictions in the multi-attribute case and we provide identification results from the observation of a single market. We thereby extend identification results in Matzkin (2003) and Heckman, Matzkin, and Nesheim (2010) to accommodate multiple dimensions of unobserved heterogeneity.

Filippo Santambrogio (Université Paris-Sud)
Urban equilibria and displacement convexity

I will present some classical equilibrium models for the distribution of the population in a urban area where agents want to balance between a cost for land, which depends on the local population density (i.e. agents prefer to be as spread as possible), and an accessing cost (where, on the contrary, if they are too spread they are too far). The equilibrium condition can be seen to be equivalent to be a critical point for a certain global functional (which is not, in general, equal to the total social utility), but the corresponding optimization problem is often non-convex as soon as interaction energies are present. In this case multiple equilibria could be observed, and not all equilibria are optimizers.
Yet, in some cases convexity strikes back, via the notion of displacement convexity introduced by McCann in 1997.

This notion, taken from optimal transport theory, will turn out to be very important even when the equilibrium and optimization problems do not explicitly involve optimal transport notion.
I will discuss general cases where multiple equilibria can or cannot occur, using this notion of convexity, following a joint work with A. Blanchet (Toulouse 1, France) and P. Mossay (Reading, UK).

Back to top