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.

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

Working papers

A model of decentralized matching markets without transfers. With Yu-Wei Hsieh. Available here.
Yogurts choose consumers? Identification of Random Utility Models via Two-Sided Matching. With Odran Bonnet, Keith O’Hara, and Matt Shum. Available here.

Papers in revision

Cupid’s Invisible Hand: Social Surplus and Identification in Matching Models. With Bernard Salanié. Revision requested (3rd round), Review of Economic Studies. Available here.

A note on the estimation of job amenities and labor productivity. With Arnaud Dupuy. Revision requested, Quantitative Economics. Available here.

Published or forthcoming papers

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.
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.
Taxation in matching markets. With Arnaud Dupuy, Sonia Jaffe, and Scott Kominers. Forthcoming, International Economic Review. Available here.
Like Attract Like? A Structural Comparison of Homogamy Across Same-Sex and Different-Sex Households (2020). With Edoardo Ciscato and Marion Goussé. Journal of Political Economy 128, no. 2, pp. 740-781. Available here.

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

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.

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.

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.

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

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

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.

‘math+econ+code’ masterclass on equilibrium transport and matching models in economics

June 8-12, 2020

Online course

Description

This very intensive course, part of the ‘math+econ+code’ series, is focused on the computation of competitive equilibrium, which is at the core of surge pricing engines and allocation mechanisms. It will investigate diverse applications such as network congestion, surge pricing, and matching platforms. It provides a bridge between theory, empirics and computation and will introduce tools from economics, mathematical and computer science. Mathematical concepts (such as lattice programming, supermodularity, discrete convexity, Galois connections, etc.) will be taught on a needs basis while studying various economic models. The same is true of computational methods (such as tatonnement algorithms, asynchronous parallel computation, mathematical programming under equilibrium constraints, etc.). Hence there are no prerequisite other than the equivalent of a first-year graduate sequence in econ, applied mathematics or other quantitative disciplines.
The teaching format is somewhat unusual: the course will be taught over five consecutive days, with lectures in the morning and individual assignments in the afternoon. This course is very demanding from students, but the learning rewards are high. The morning lectures will alternate between 1 hour of theory followed by 1 hour of coding. Students are expected to write their own code, and the teaching staff will ensure that it is operational. This course is therefore closer to cooking lessons than to traditional lectures.

Aim of the course

• Provide the conceptual basis of competitive equilibrium with gross substitutes, along with various computational techniques (optimization problems, equilibrium problems). Show how asynchronous parallel computation is adapted for the computation of equilibrium. Applications to hedonic equilibrium, multinomial choice with peer effects, and congested traffic equilibrium on networks.
• Describe analytical methods to analyze demand systems with gross substitutes (Galois connections, lattice programming, monotone comparative statics) and use them to study properties of competitive equilibrium with gross substitutes. Describe the Kelso-Crawford-Hatfield-Milgrom algorithm. Application to stable matchings, and equilibrium models of taxation.
• Derive models of bundled demand and analyze them using notions of discrete convexity and polymatroids. Application to combinatorial auctions and bundled choice.

Instructors

A. Galichon (NYU Econ+Math)

Course material

Course material (lecture slides, datasets, code) will made available before the lectures in this Github repository.

Practical information

• Schedule: June 8-12, 2020. Classes meet 2pm-6pm Paris time / 8am-noon New York time. In addition, supplementary material (approximately 2 hours in length) is made available each day to complement the main lectures.

Part I: Tools
Day 1: Competitive equilibrium with gross substitutes (Monday, 4 hours)
Walrasian equilibrium and gross substitutes. Gradient descent, Newton method; coordinate update method. Isotone convergence and Tarski’s theorem. Parallel computation (synchronous and asynchronous). Fisher-Eisenberg-Gale markets. Hedonic models beyond the quasilinear case.
References:
• Ortega and Rheinboldt (1970). Iterative Solution of Nonlinear Equations in Several Variables. SIAM.
• Heckman, Matzkin, and Nesheim (2010). “Nonparametric identification and estimation of nonadditive hedonic models,” Econometrica.
• Gul and Stacchetti (1999). “Walrasian equilibrium with gross substitutes”. Journal of Economic Theory.
• Jain and Vazirani (2010). “Eisenberg–Gale markets: Algorithms and game-theoretic properties”. Games and Economic Behaviour.
• Cheung and Cole (2016). “A Unified Approach to Analyzing Asynchronous Coordinate Descent and Tatonnement”. Arxiv.

Day 2: Demand beyond quasi-linearity (Tuesday, 4 hours)
Lattices and supermodularity. Veinott’s strong set ordering and Topkis’ theorem; Milgrom-Shannon theorem. Z-maps, P-maps and M-maps. Galois connections and generalized convexity. Equilibrium transport. Models of matching models with imperfectly transferable utility. Stable matchings and Gale and Shapley’s algorithm.
References:
• Veinott (1989). Lattice programming. Unpublished lecture notes, Johns Hopkins University.
• Topkis (1998). Supermodularity and complementarity. Princeton.
• Milgrom and Shannon (1994). “Monotone comparative statics.” Econometrica.
• Rheinboldt (1974). Methods for solving systems of nonlinear equations. SIAM.
• Noeldeke and Samuelson (2018). The implementation duality. Econometrica.
• Kelso and Crawford (1981). Job Matching, Coalition Formation, and Gross Substitutes. Econometrica.
• Roth and Sotomayor (1992). Two-Sided Matching. A Study in Game-Theoretic Modeling and Analysis. Cambdidge.

Day 3: Bundled demand (Wednesday, 4 hours)
Discrete convexity. Lovasz extension; Polymatroids. Hatfield-Milgrom’s algorithm. Combinatorial auctions.
References:
• Fujishige (1991). Submodular functions and optimization. Elsevier.
• Vohra (2011). Mechanism design. A linear programming approach. Cambridge.
• Bikhchandani, Ostroy (2002). The Package Assignment Model”. JET.
• Hatfield and Milgrom (2005). Matching with contracts. AER.
• Danilov, Koshevoy, and Murota (2001). Discrete convexity and equilibria in economies with indivisible goods and money. Mathematical Social Sciences.

Part II: Models
Day 4: Empirical models of demand (Thursday, 4 hours)
Nonadditive random utility models. Strategic complements; supermodular games. Brock-Durlauf’s model of demand with peer effect. Mathematical programming with equilibrium constraints (MPEC).
References:
• Vives, X. (1990). “Nash Equilibrium with Strategic Complementarities,” JME.
• Milgrom and Roberts (1994). “Comparing Equilibria,” AER.
• Berry, Gandhi, Haile (2013). “Connected Substitutes and Invertibility of Demand,” Econometrica.
• Brock, Durlauf (2001). Discrete choice with social interactions. JPE.
• Dubé, Fox and Su (2012), “Improving the Numerical Performance of BLP Static and Dynamic Discrete Choice Random Coefficients Demand Estimation,” Econometrica.
• Bonnet, Galichon, O’Hara and Shum (2018). Yoghurts choose customers? Identification of random utility models via two-sided matching.

Day 5: Empirical models of matching (Friday, 4 hours)
Distance-to-frontier function, matching function equilibrium. Matching models with taxes. Matching with public consumption. Surge pricing.
References:
• Menzel (2015). Large Matching Markets as Two-Sided Demand Systems. Econometrica.
• Legros, Newman (2007). Beauty is a Beast, Frog is a Prince. Assortative Matching with Nontransferabilities. Econometrica.
• Galichon, Kominers, and Weber (2018). Costly Concessions: An Empirical Framework for Matching with Imperfectly Transferable Utility.

Day 6: Equilibrium on networks (Saturday, 4 hours)
Equilibrium on networks. Traffic congestion; Wardrop equilibrium. Braess’ paradox. Price of anarchy.
References:
• Roughgarden, Tardos (2002). How bad is selfish routing? Journal of the ACM.
• Roughgarden (2005). Selfish Routing and the Price of Anarchy. MIT.
• Bourlès, Bramoullé, and Perez‐Richet (2017). Altruism in networks. Econometrica.
• Wardrop (1952). “Some theoretical aspects of road traffic research”. Proc. Inst. Civ. Eng.
• Dafermos (1980). “Traffic Equilibrium and Variational Inequalities.” Transportation Science.
• Nagurney (1993). Network Economics: A Variational Inequality Approach. Kluwer.

Sponsored by:

The National Science Foundation, grant DMS-1716489, “Optimal and equilibrium transport: theory and applications to economics and data science.”

The European Research Council, grant ERC CoG-866274 EQUIPRICE,“Equilibrium methods for resource allocation and dynamic pricing.”

‘math+econ+code’ part one: optimal transport and economic applications

NYU, Courant Institute (Warren Weaver Hall, 251 Mercer) Rm 101, January 20-24, 2020 (30 hours)

Instructor: A. Galichon (NYU Econ+Math). Email: alfred.galichon@nyu.edu. TA: James Nesbit (NYU Econ). Email: jmn425@nyu.edu.

Description

This intensive course, part of the ‘math+econ+code’ series, is focused on models of demand, matching models, and optimal transport methods, with various applications pertaining to labor markets, economics of marriage, industrial organization, matching platforms, networks, and international trade, from the crossed perspectives of theory, empirics and computation. It will introduce tools from economic theory, mathematics, econometrics and computing, on a needs basis, without any particular prerequisite other than the equivalent of a first year graduate sequence in econ or in applied math.
A particular emphasis will be given on HPC computation and parallel computing.
Because it aims at providing a bridge between theory and practice, the teaching format is somewhat unusual: each teaching “block” will be made of 50 minutes of theory followed by 1 hour of coding, based on an empirical application related to the theory just seen. Students are expected to write their own code, and we will ensure that it is operational at the end of each block. This course is therefore closer to cooking lessons than to traditional lectures.
The course is open to graduate students in the fields of economics and applied mathematics, but also in other quantitative disciplines. Students need to bring a laptop with them to the lectures. The knowledge of a particular programming language is not required; students are however expected to have some experience with programming. The language of the course will be Python.
The lecturer is Alfred Galichon (professor of economics and of mathematics at NYU). The TA is James Nesbit (graduate economics student at NYU). Pauline Corblet (graduate economics student at Sciences Po), Octavia Ghelfi and James Nesbit (graduate economics students at NYU) have helped prepare the course material. Support from NSF grant DMS-1716489 is acknowledged.

Suggested preparation readings (optional)

Alfred Galichon (2016). Optimal Transport Methods in Economics. Princeton University Press.

Course material

Available on github here.
Available on NYU’s HPC cluster here.

Course material from past editions available from this Github repository.

Practical information

• Schedule: Monday to Friday, 8:30am-12:30pm and 1:30pm-3:30pm. Location: NYU Courant Institute, Warren Weaver Hall, 251 Mercer St, Room 101.
• Credits: 2, assessed through a take-home exam or a short final paper, at the student’s option.
• A syllabus is available at http://alfredgalichon.com/mec_optim/.
• NYU Students need to register on Albert (code ECON-GA 3503). Students are advised to contact the instructor (alfred.galichon@nyu.edu) ahead of time.

Outline

• Monday: linear programming, dynamic programming, network flows
• Tuesday: optimal transport toolbox 1 (discrete, one-dimensional, semi-discrete cases)
• Wednesday: optimal transport toolbox 2 (continuous transport, convex analysis, entropic regularization)
• Thursday: static and dynamic multinomial choice
• Friday: statistical estimation of models of matching with transfers

Synopsis

SYNOPSIS
Part I: Tools
Day 1: linear programming (Monday)
Block 1. Basics of linear programming (morning 1st half)
• Theory: linear programming duality; complementary slackness; minimax formulation
• Coding: How to eat optimally? Dataset: Stigler’s original diet data (1945).
Block 2. Network flow problems (morning 2nd half)
• Theory: directed graphs and min-cost flow problem
• Coding: How to find the shortest path through a network? Dataset: Paris subway; New York City street network.
Block 3. Dynamic programming as linear programming (afternoon)
• Theory: Bellman’s equation; interpretation of duality; forward induction, backward induction
• Coding: When to repair mechanical engines? Dataset: Rust’s bus maintenance data (1994).

Day 2: optimal transport I (Tuesday)
Block 4. Discrete matching (morning 1st half)
• Theory: Shapley-Shubik duality; stability; decentralized equilibrium
• Coding: How to solve it? Dataset from Dupuy and Galichon (JPE 2014).
Block 5. Positive assortative matching (morning 2nd half)
• Theory: Becker’s model; compensating differentials; comonotonicity
• Coding: What is a CEO worth? Dataset: Gabaix-Landier’s (QJE 2008) CEO pay data.

Block 6. Hotelling’s characteristics model (afternoon)
• Theory: power diagrams, Aurenhammer’s method
• Coding: How to infer the unobservable quality of a car model? Dataset: Feenstra-Levinsohn (Restud 1994) car data.

Day 3: optimal transport II (Wednesday)
Block 7. Continuous multivariate matching (morning 1st half)
• Theory: Knott-Smith criterion; Brenier’s map; McCann’s theorem
• Applications: exercises.
Block 8. A short tutorial on convex analysis (morning 2nd half)
• Theory: convex duality; Fenchel’s inequality; subdifferentials and their inverses
• Application: exercises.
Block 9. Regularized optimal transport (afternoon)
• Theory: optimal transport with entropic regularization, and with other regularizations.
• Coding: coordinate descent and the IPFP algorithm.

Part II. Models
Day 4: models of static and dynamic multinomial choice (Thursday)
Block 10. Basics of static discrete choice (morning 1st half)
• Theory: Dary-Zachary-Williams theorem, generalized entropy of choice, the inversion theorem
• Coding: How to solve it? simulation methods; AR, SARS, and GHK. Dataset: Greene and Hensher (1997) data on choice of travel mode.
Block 11. Demand models, old and new (morning 2nd half)
• Theory: the GEV model; the random coefficient logit model and the pure characteristics models
• Coding: How to estimate demand for automobiles? Dataset: BLP.
Block 12. Dynamic discrete choice methods (afternoon)
• Theory: Rust’s model; estimation; normalization issues
• Coding: maintenance choice.

Day 5: empirical matching models, the quasilinear case (Friday)
Block 13. Separable models of matching (morning 1st half)
• Theory: matching with unobservable heterogeneity
• Coding: Did Roe vs. Wade decrease the value of marriage? Dataset: Choo and Siow (JPE 2006).
Block 14. The gravity equation (morning 2nd half)
• Theory: optimal transport and the gravity equation; generalized linear models and pseudo-Poisson maximum likelihood estimation
• Coding: How to forecast international trade flows? estimating the gravity equation based on WTO international trade data.
Block 15. High-dimensional matching models (afternoon)
• Theory: estimation of rank-constrained models
• Application: Does physical appearance have a price? matching on socioeconomic and anthropomorphic characteristics. Dataset: Chiappori, Oreffice and Quintana-Domeque’s (JPE 2012).