New Perspectives on Substitutes

Paris, June 2-3, 2023

Organizers: Alfred Galichon (New York University and Sciences Po) and Larry Samuelson (Yale University)

Substitutability has found itself at the core of modern economic modeling for two reasons.  First, it arises naturally in classes of models such as one-to-one matching, discrete choice, hedonic models, and many others.  Second, it leads to successful numerical methods, such as the greedy algorithm in the discrete case, and the Jacobi algorithm related ones in the continuous case.  Leading experts in the field will gather to make a link between discrete and continuous models and to explore recent theoretical developments and economic applications.

Abstracts can be found here.

Papers can be found here.

Slides can be found here.

The workshop is accessible to the public but registration is mandatory by emailing ag133@nyu.edu.

Friday June 2, 2023

Location: Sciences Po (27 rue Saint Guillaume, room AS)

1230pm-130pm: luncheon buffet (room AS)

Session 1

130pm-215pm: Renato Paes Leme: “Gross Substitutes: Representation and Approximation”

215pm-300pm: Xin Chen / Menglong Li: “S-Convexity and Gross Substitutability”

300pm-330pm: break

Session 2

330pm-415pm: Alexander Teytelboym: TBA

415pm-500pm: Jonathan Weinstein: “Direct Complementarity”

5pm-530pm: break

Session 3

530pm-615pm: Lucas Vernet: “Monotone Comparative Statics for Equilibrium Problems”

615-700pm: Ravi Jagadeesan: “Understanding Demand Types and Discrete Convexity”

700pm-730pm: dinner (invitation only): Chez Francoise, Aérogare des Invalides, 75007 Paris
https://goo.gl/maps/9HEZ9nMkRmcJrWkA6

Saturday June 3, 2023

Location: NYU Paris (57 boulevard Saint-Germain, 75005 Paris)

Session 4

0915am-10am: Faruk Gul: “Efficient Allocation of Indivisible Goods in Pseudo Markets with Constraints”

1000am-1045am: Pawel Dziewulski: “It’s all about parallelograms: comparative statics in quasilinear settings”

1045am-1115am: break

Session 5

1115am-1200pm: Elizabeth Baldwin: “Implementing Walrasian Equilibrium: The Language of Product-Mix Auctions”

1200pm-1245pm: Maxime Sylvestre: “Monotone comparative statics for submodular functions, with an application to aggregated deferred acceptance”

1245pm-130pm: Wolfgang Pesendorfer: “Lindahl Equilibrium as a Collective Choice Rule”

130pm lunch (invitation only): Les Papilles, 30 rue Gay Lussac, 75005 Paris
https://goo.gl/maps/73TVUbfvkG4cieXp7

Lecture series

Two lectures on matching models for family economics

Invited lectures given at the University of Toronto, April 1 and April 8, 2022

Content

The first lecture will cover transferable utility (TU) matching models with logit heterogeneity following the seminal paper by Choo and Siow (JPE 2006), its extension and parametric estimation following Galichon and Salanié (Restud 2022).
The second lecture will discuss the interplay between models of matching and collective models as depicted in Browning and Chiappori’s (Cambridge, 2014) monograph, and how models of imperfectly transferable utility (ITU) and logit or more general heterogeneity are needed to address this new class of problems, as is done in Galichon, Kominers and Weber (JPE, 2019).

Schedule

April 1 and April 8, 10am-12pm Eastern time, online.

Course material

The lecture slides are available from the following github repository.

References

These lectures are based on:
[GS] Galichon and Salanie (2022). Cupids invisible hands: Social Surplus and Identification in Matching Models. Review of Economic Studies.
[GKW] Galichon, Kominers and Weber (2019). Costly Concessions: An Empirical Framework for Matching with Imperfectly Transferable Utility (2019). Journal of Political Economy.
[MEC-OPTIM] Galichon (2022). `math+econ+code’ masterclass on optimal transport and economic applications. https://www.math-econ-code.org/mec-optim
[MEC-EQUIL] Galichon (2022). `math+econ+code’ masterclass on equilibrium transport and matching models in economics. https://www.math-econ-code.org/mec-equil

Outline

Lecture 1: Matching models with transferable utility:
Matching models as an optimization problem / regularized optimal transport / generalized linear models
Lecture 2: Matching models with imperfectly transferable / nontransferable utility:
Matching models as an equilibrium problem with substitutes

Lecture series

Gross substitutes, optimal transport and matching models

Optimal Transport Summer School, the University of Washington, Seattle, June 19-July 1, 2022

Content

Gross substitutes is a fundamental property in mathematics, economics and computation, almost as important as convexity. It is at the heart of optimal transport theory — although this is often underrecognized — and understanding the connection key to understanding the extension of optimal transport to other models of matching.

Schedule

TBD

Course material

The lecture slides are available before each lecture from the following github repository.

References

These lectures will be loosely based on my math+econ+code lectures:
A. Galichon, ‘math+econ+code’ masterclass on equilibrium transport and matching models in economics. June 2021. Available here.

Outline

Lecture 1. Introduction to gross substitutes
M-matrices and M-maps, nonlinear Perron-Froebenius theory, convergence of Jacobi algorithm. A toy hedonic model.

Lecture 2. Models of matching with transfers
Problem formulation, regularized and unregularized case. IPFP and its convergence. Existence and uniqueness of an equilibrium. Lattice structure.
Lecture 3. Models of matching without transfers
Gale and Shapley’s stable matchings. Adachi’s formulation. Kelso-Craford. Hatfield-Milgrom.

Kidney transplant hackaton

a math+econ+code event

When? TBA

Who? participation to this math+econ+code event is open to the public upon request.

What? Kidney transplant problems provide a very interesting real-life examples of dynamic matching problems. A large academic literature exists on the topic, both in economics and in operations research. Because the problem is a difficult problem computationally speaking, a number of algorithms exist out there to try to approximate the best solution. This hackaton will put you in the shoes of the transplant agency: at each period, you will receive the state of your population, which is made of your existing population of patients, plus new patients and minus deceased ones (simulated by our platform). Your role will be write the algorithm that matches donors and receivers, given the constraints on the way transplants can be done (state of the patient, compatibility between donor and receiver, length of transplant chains, etc.)

Each player plays in parallel and is evaluated by a score, which will reflect the state of their population of patients. The game is played over a very large number of periods. The player with the highest final score has come up with the best algorithm and wins the hackaton.

What is required? In order to participate, you need to be familiar with Python programming. Your only input is the matching function that assigns donors to receivers — a function whose length can be less than a hundred lines but can be more depending on your design. All the interfacing is done by the platform.

Interested? contact us at math.econ.code@gmail.com.

EQUIPRICE papers

The following papers benefited from the support of the ERC-sponsored project EQUIPRICE.

Working papers

Stable and extremely unequal. With Octavia Ghelfi and Marc Henry. Manuscript available on arxiv.

Published or forthcoming papers

Yogurts choose consumers? Identification of Random Utility Models via Two-Sided Matching. With Odran Bonnet, Yu-Wei Hsieh, Keith O’Hara, and Matt Shum. Forthcoming, Review of Economic Studies. Available here.
A note on the estimation of job amenities and labor productivity. With Arnaud Dupuy. Forthcoming Quantitative Economics. Available here.
Cupid’s Invisible Hand: Social Surplus and Identification in Matching Models. With Bernard Salanié. Forthcoming, Review of Economic Studies. Available here.
SISTA: learning optimal transport costs under sparsity constraints. With Guillaume Carlier, Arnaud Dupuy and Yifei Sun. Accepted for publication, Communications on Pure and Applied Mathematics. Available here.
On the representation of the nested logit model. Accepted for publication, Econometric Theory. Available here.
Single market nonparametric identification of multi-attribute hedonic equilibrium models. With Victor Chernozhukov, Marc Henry, and Brendan Pass. Accepted for publication, Journal of Political Economy. Available here.
Fritz John’s equation in mechanism design (2021). Economic Theory Bulletin 9, pp. 1–5. Available here.
Taxation in matching markets. With Arnaud Dupuy, Sonia Jaffe, and Scott Kominers. Forthcoming, International Economic Review. Available here.

EQUIPRICE: Equilibrium methods for Resource Allocation and Dynamic Pricing. European Research Council consolidator grant (ERC-CoG) No. 866274, 2020-2025.

EQUIPRICE code

TraMEPy Project

The TraME software (Transportation Methods for Econometrics, http://www.trame-project.com/) is a collection of libraries for solving problems of equilibrium computation and estimation in consumer demand and matching frameworks via the Mass Transportation Approach. It will be completely revamped to accommodate for the equilibrium flow problem in its full generality (beyond bipartite networks), novel equilibrium algorithms added, enhanced HPC capabilities, and a new Python implementation.

EQUIPRICE: Equilibrium methods for Resource Allocation and Dynamic Pricing. European Research Council consolidator grant (ERC-CoG) No. 866274, 2020-2025.

EQUIPRICE scientific agenda

The EQUIPRICE project seeks to build an innovative economic toolbox (ranging from modelling, computation, inference, and empirical applications) for the study of equilibrium models with gross substitutes, with applications to models of matching with or without transfers, trade flows on networks, multinomial choice models, as well as hedonic and dynamic pricing models. While under-emphasized in general equilibrium theory, equilibrium models with gross substitutes are very relevant to these problems as each of these problems can be recast as such.
Thus far, almost any tractable empirical model of these problems typically required making the strong assumption of quasi-linear utilities, leading to a predominance of models with transferable utility in applied work. The current project seeks to develop a new paradigm to move beyond the transferable utility framework to the imperfectly transferable utility one, where the agent’s utilities are no longer quasi-linear.
The mathematical structure of gross substitutes will replace the structure of convexity underlying in models with transferable utility.
To investigate this class of models, one builds a general framework embedding all the models described above, the “equilibrium flow problem.” The gross substitute property is properly generalized and properties (existence of an equilibrium, uniqueness, lattice structure) are derived. Computational algorithms that rely on gross substitutability are designed and implemented. The econometrics of the problem is addressed (estimation, inference, model selection). Applications to various fields such as labor economics, family economics, international trade, urban economics, industrial organization, etc. are investigated.
The project touches upon other disciplines. It will propose new ideas in applied mathematics, offer new algorithms of interest in computer science and machine learning, and provide new methods in other social sciences (like sociology, demography and geography).

Seven scientific challenges

Challenge 1. How to build a single framework to be able to reformulate matching models with or without (or with imperfect) transfers, hedonic models, models of multinomial choice, and models of international trade as problems of competitive equilibrium with gross substitutes?

Challenge 2. How to extend the framework investigated in challenge 1 to handle dynamic, Markov versions of these problems (both in the finite-horizon and stationary case)?

Challenge 3. How to extend the notion of gross substitutes to allow for the possibility of indifference between preferred alternatives, i.e. consider the case of set-valued excess demand / supply?

Challenge 4. Build and analyze a set of algorithms for the equilibrium problem with gross substitutes to handle the problems described in the previous Challenges.

Challenge 5. Implement these algorithms into a compiled, parallelized software library.

Challenge 6. Develop a novel inferential theory based on minimax regret estimation for the estimation of equilibrium models with Gross Substitutes, to handle inference in the previous problems.

Challenge 7. In the minimax regret estimation framework of challenge 6, extend the estimation and inference theory to handle sparsity constraints.

EQUIPRICE: Equilibrium methods for Resource Allocation and Dynamic Pricing. European Research Council consolidator grant (ERC-CoG) No. 866274, 2020-2025.

EQUIPRICE positions

Open positions

Post-doctoral researcher (TBA)

The post-doctoral researcher will be expected to contribute to the intellectual advancement of the project, interact with the PhD students, and participate in the organization of the seasonal events described below. The post-doctoral position is envisioned for four years; however, depending on individual circumstances, it may also be two consecutive two-year positions.

Two doctoral fellows

One doctoral fellow will have a focus on computational economics. The other doctoral fellow will focus on empirical economics.

Research assistants

March 14, 2021: Equiprice is looking for an intern in the field of data science and economics.

EQUIPRICE: Equilibrium methods for Resource Allocation and Dynamic Pricing. European Research Council consolidator grant (ERC-CoG) No. 866274, 2020-2025.

EQUIPRICE workshops

Upcoming workshops

Fall 2021: Workshop on optimal transport with applications to economics and statistics, blended, Sciences Po, Paris.

EQUIPRICE: Equilibrium methods for Resource Allocation and Dynamic Pricing. European Research Council consolidator grant (ERC-CoG) No. 866274, 2020-2025.

EQUIPRICE lectures

Upcoming lectures

February 26 2021, 2pm-4pm (Paris time): estimation of dynamic discrete choice problems

Speaker: Alfred Galichon

• Theory: Rust’s model; estimation; normalization issues
• Coding: maintenance choice.

March 12 2021, 2pm-4pm (Paris time): matrix games

Speaker: Alfred Galichon

• Theory: Nash equilibria; correlated equilibria; zero-sum games and LP formulation
• Coding: soccer data on penalty.

April 9 2021, 2pm-4pm (Paris time): kidney exchange problems

Speaker: Jules Baudet.

• Theory: Roth et al.
• Coding: an interactive multi-player simulator

Special lecture 5 (April 30, 2pm-4pm Paris time): traffic congestion

Speaker: Alfred Galichon

• Theory: Wardrop equilibria; price of anarchy
• Coding: traffic data.

Past lectures

February 5 2021, 2pm-4pm (Paris time): cloud computing

Speakers: Flavien Léger (Equiprice) and James Nesbit (NYU).

EQUIPRICE: Equilibrium methods for Resource Allocation and Dynamic Pricing. European Research Council consolidator grant (ERC-CoG) No. 866274, 2020-2025.