ECON-GA 3503

‘math+econ+code’ in Paris: A masterclass on optimal transport, choice and matching models

NYU Paris (57 bd St-Germain, 75005 Paris), June 17-21, 2019 (30 hours)

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

** Note: Interested students must contact the instructor ahead of time.**

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.
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 course can be taken for credit or as a registered auditor.
The lecturer is Alfred Galichon (professor of economics and of mathematics at NYU). Pauline Corblet (graduate economics student at Sciences Po) and Octavia Ghelfi and James Nesbit (graduate economics students at NYU) have helped prepare the course material. The course is partly based on Galichon’s book, Optimal Transport Methods in Economics.

Support from NSF grant DMS-1716489 is acknowledged.

Course material

Available on Github here.

Practical information

• Schedule: Monday to Friday, 8am-12noon and 2pm-4pm. Location: NYU Paris, 57 boulevard Saint-Germain, 75005 Paris, Room TBA.
• 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). Non-NYU student can be allowed to audit the course. All students need 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).

ECON-GA 3503.1410

‘math+econ+code’ masterclass on optimization in economics: optimal transport, demand models and matching models

NYU Courant Institute, January 14-18, 2019 (30 hours)

Instructor: A. Galichon (NYU Econ+Math)

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.
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, jointly offered by NYU Econ and the Courant Institute, 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 course can be taken for credit or as a registered auditor.
The lecturer is Alfred Galichon (professor of economics and of mathematics at NYU). James Nesbit (graduate Economics student at NYU) helped prepare the course material. The course is partly based on Galichon’s book, Optimal Transport Methods in Economics.

Support from NSF grant DMS-1716489 is acknowledged.

Course material

Available on Github here.

Practical information

• Schedule: Mon 1/14 — Fri 1/18, 2019, 9am-1pm and 2pm-4pm. Location: WWH 101 in the Courant building (251 Mercer St)
• 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/matheconcode/.
• Students need to register on Albert (code ECON-GA 3503.1410). For more information please contact: galichon@cims.nyu.edu.

Outline

• Monday: linear programming, dynamic programming, network flows
• Tuesday: optimal transport toolbox
• Wednesday: convex analysis, nonlinear inverse problems, and multivariate quantiles
• 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).

ARCHIVE

Current version to be found here.

ECON-GA 3002.015 and MATH.GA 2840.002

‘math+econ+code’ masterclass on optimization in economics: optimal transport, demand models and matching models

NYU Courant Institute, January 15-20, 2018 (36 hours)

Instructors: A. Galichon (NYU Econ+Math), Keith O’Hara (NYU Econ) and Yifei Sun (NYU Math)

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.
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 the teaching staff 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, jointly offered by NYU Econ and the Courant Institute, 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 course can be taken for credit or as a registered auditor.
The teaching staff is Alfred Galichon (professor of economics and of mathematics at NYU), Keith O’hara (economics graduate student at NYU and R and C++ guru), and Yifei Sun (mathematics graduate student at NYU focusing on machine learning). They are authors of the TraME library (https://github.com/TraME-Project), a toolbox for inference and simulation of discrete choice and matching problems. The course is based on Galichon’s popular graduate classes previously taught at NYU, and on his recent book, Optimal Transport Methods in Economics.

Support from NSF grant DMS-1716489 is acknowledged.

Course material

Available on Github here.

Practical information

• Schedule: Mon 1/15 — Sat 1/20, 2018, 8am-12 noon and 1pm-3pm. Location: WWH 102 in the Courant building (251 Mercer St)
• Credits: 3, assessed through a take-home exam or a short final paper, at the student’s option.
• A syllabus is available at http://alfredgalichon.com/matheconcode/.
• Students need to register on Albert (MATH-GA 2840.002 or ECON-GA 3002.015). For more information please contact: galichon@cims.nyu.edu.

Outline

• Monday 1/15: linear programming, dynamic programming, network flows
• Tuesday 1/16: optimal transport toolbox
• Wednesday 1/17: convex analysis, nonlinear inverse problems, and multivariate quantiles
• Thursday 1/18: static and dynamic multinomial choice
• Friday 1/19: statistical estimation of models of matching with transfers
• Saturday 1/20: more general models of matching

Synopsis

SYNOPSIS
Part I: Tools
Day 1: linear programming (Monday Jan 15)
Block 1. Basics of linear programming (8am-9:50am)
• 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 (10:10am-noon)
• 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 (1pm-2:50pm)
• 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 Jan 16)
Block 4. Discrete matching (8am-9:50am)
• Theory: Shapley-Shubik duality; stability; decentralized equilibrium
• Coding: How to solve it? Dataset from Dupuy and Galichon (JPE 2014).
Block 5. Positive assortative matching (10:10am-noon)
• 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 (1pm-2:50pm)
• 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 Jan 17)
Block 7. Continuous multivariate matching (8am-9:50am)
• Theory: Knott-Smith criterion; Brenier’s map; McCann’s theorem
• Coding: How to solve it? the iterated proportional fitting procedure (IPFP). Dataset from Dupuy and Galichon (JPE 2014).
Block 8. Convex analysis and nonlinear inverse problems (10:10am-noon)
• Theory: convex duality; Fenchel’s inequality; subdifferentials and their inverses
• Coding: How to optimize with big data? Proximal gradient algorithms; LASSO; stochastic gradient algorithms.
Block 9. Quantiles methods (1pm-2:50pm)
• Theory: Rosenblatt’s quantiles; vector quantiles; vector quantile regression
• Coding: How to predict demand? vector quantile regression. Dataset: Engel’s (1857) original food expenditure data.

Part II. Models
Day 4: models of static and dynamic multinomial choice (Thursday Jan 18)
Block 10. Basics of static discrete choice (8am-9:50am)
• 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 (10:10am-noon)
• 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 (1pm-2:50pm)
• Theory: Rust’s model; estimation; normalization issues
• Coding: career choice.

Day 5: empirical matching models, the quasilinear case (Friday Jan 19)
Block 13. Separable models of matching (8am-9:50am)
• 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 (10:10am-noon)
• 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 (1pm-2:50pm)
• 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).

Day 6: empirical matching models beyond quasilinearity (Saturday Jan 20)
Block 16. Matching with imperfectly transferable utility (8am-9:50am)
• Theory: Galois connections, distance-to-frontier function, nonlinear complementary slackness, equilibrium transport
• Application: How do taxes affect matching patterns and wages? Dataset: Football coach data from Dupuy, Galichon, Jaffe and Kominers (2017).
Block 17. Integrating matching models and collective models of intrahousehold bargaining (10:10am-noon)
• Theory: collective models, Pareto weights, sharing rule
• Application: Do people marry for consumption or companionship? Dataset: Galichon, Kominers and Weber (2017).
Block 18. Matching with nontransferable utility (1pm-2:50pm)
• Theory: the Dagsvik-Menzel model; nonprice rationing and the NTU-logit separable model
• Application: Revisiting Choo and Siow’s data.

Lecture series

Optimal transport methods in economics: an introduction

UCLA, April 16 and 20, 2018

Content

These lectures will provide an introduction to optimal transport and its applications in economics.

Schedule

Monday, April 16, 2018, 9am-11am
Friday, April 20, 2018, 9am-11am

Course material

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

References

These lectures will be based on my text:
Galichon, A. (2016). Optimal transport methods in economics. Princeton.

Other references include:
∙ For mathematical foundations:
– [OTON] C. Villani, Optimal Transport: Old and New, AMS, 2008.
– [OTAM] F. Santambrogio, Optimal Transport for Applied Mathematicians, Birkhäuser, 2015.
∙ For an introduction with a fluid mechanics point of view:
– [TOT] C. Villani, Topics in Optimal Transportation, AMS, 2003.
∙ With a computational focus:
– [NOT] G. Peyré, M. Cuturi (2018). Numerical optimal transport, Arxiv.
∙ With a family economics focus:
– [MWT] P.-A. Chiappori. Matching with Transfers: The Economics of Love and Marriage, Princeton, 2017.

Outline

L1. The labor market as an optimal transport problem: efficiency and equilibrium
L2. Multivariate quantile methods using optimal transport

Mini-course

Matching models with general transfers

Summer school “Optimal transport and economics,” Hausdorff Center, Bonn, July 23-27, 2018 (4h30)

Content

These lectures will deal with optimal and equilibrium transport, and applications to matching models in economics.
In order to introduce the Monge-Kantorovich theorem of optimal transport theory in lecture 1, we consider a stylized assignment problem. Assume that a central planner (say, a plant manager) needs to assign workers to machines in order to maximize total output. Workers vary by their individual characteristics, and machines come in various sorts, where the set of characteristics of workers and firms may be either discrete or continuous. The output of a worker assigned to a machine depends on both the worker’s and the machine’s characteristics, so some workers may be better with some machines, and worse with some others. The central planner’s problem, which is the optimal transport problem, consists of assigning workers to machines in a way such that the total output is maximized. It will predict the equilibrium wages and the assignment of workers to machine.
Lecture 2 will introduce additional heterogeneity in preferences, so that the surplus of a match is the sum of a deterministic and a random term. We shall show that this leads to a regularized optimal transport problem, with an additional regularization term which is an entropy in the case when random utility belong in the logit specification, but can be characterized much more generally as a generalized entropy beyond that case. We will discuss implications for identification, comparative statics and the estimation of these models. This model can be used to estimate the structural parameters of the matching market, i.e. workers’ productivity and job amenity.
In lecture 3, we shall discuss a far-reaching extension of this setting called equilibrium transport. The classical theory of optimal transport relies on the 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. That assumption is, of course, very strong as various nonlinearities may arise in practice, from taxes for example. Removing this strong assumption requires moving beyond optimal transport theory, to “Equilibrium transport theory”, which is strongly connected with the theory of “prescribed Jacobians equations”. We will see 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, and we will study in detail a regularized version of this problem.

Schedule

L1: Monday 11am-12:30pm
L2: Monday 2pm-3:30pm
L3: Wednesday 9am-10:30am

Course material

The lecture slides will be available before each lecture on the following github repository.

References

Galichon, A. (2016). Optimal transport methods in economics. Princeton.

Outline

L1. The labor market as an optimal transport problem: Monge-Kantorovich duality
L2. Introducing unobserved heterogeneity among agents: regularized optimal transport
L3. Introducing taxes: equilibrium transport

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

Format: online + in person (situation allowing)

Please visit the new webpage of the course

https://www.math-econ-code.org/june2021

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, between 8am and 12noon (US Eastern time). 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 and Sciences Po)

Course material

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

How to apply

Interested individuals should apply through this form and enclose a CV and letter of motivation. Applicants must also have their faculty mentor send a letter of reference on their behalf to math.econ.code@gmail.com. Application material should be received in full before May 15th. Please note the course is interactive, which makes active participation an important requirement. We will let you know the status of your application by May 31st.

Outline

• Monday: competitive equilibrium with gross substitutes
• Tuesday: demand beyond quasi-linearity
• Wednesday: bundled demand
• Thursday: empirical models of demand and matching
• Friday: network congestion

Synopsis

Supported by:

• The European Research Council, grant ERC CoG-866274 EQUIPRICE,“Equilibrium methods for resource allocation and dynamic pricing.” (2020-2025)
• The National Science Foundation, grant DMS-1716489, “Optimal and equilibrium transport: theory and applications to economics and data science.” (2017-2020)

MATH+ECON+CODE MASTERCLASS SERIES

Data science meets economics

VISIT THE NEW M+E+C WEBSITE AT https://www.math-econ-code.org/

Alfred Galichon (NYU Econ+Math and Sciences Po Econ)

Innovative, Intensive, Interdisciplinary

An immersive learning experience
The ‘math+econ+code’ masterclasses are very intensive classes in which the students are immersed over five consecutive days on a topic at the interaction between mathematics, economics and computation. These classes are innovative in several respects: the condensed format, the mix of theoretical, computational and empirical components, and the emphasis on coding. The classes focus on the acquisition of an operational knowledge: throughout the week, students will learn the mathematical structures, the economic models, and how to code them in practice. The course relies on scientific context-based learning: mathematical concepts and computational methods are introduced on a needs basis while studying various economic models, and thus there are no prerequisite other than the equivalent of a first-year graduate sequence in econ, applied mathematics or other quantitative disciplines.

A very active area of research
The intersection between economics, mathematics and computation is coming back as a major area of current research. There are at least two reasons for this. The first one is the emergence of online platforms, which act as central planners and need to solve complex computational problems such as matching service providers with customers, introducing potential dating partners, performing dynamic pricing tasks, etc. The second reason is that econometric methods have been cross-fertilized by novel techniques from machine learning, that heavily rely on computational tools.

“Closer to cooking lessons than to traditional lectures”

The teaching format of a ‘math+econ+code’ series is somewhat unusual: a class is typically taught over six consecutive days, with a lesson in the morning (alternating between theory blocks and coding blocks); a guest lecture in the early afternoon; followed by individual work on computational assignments in the last part of the afternoon. These classes are very demanding from students, but the learning rewards are also very high. Students are expected to write their own code, and the teaching staff will ensure that it is operational at the end of the day. In complete opposition to the trend of ‘massively open online courses’ (MOOCS), these classes place instead a particular emphasis on personal interactions between teaching staff and students. They are therefore closer to cooking lessons than to traditional lectures. Without equivalent elsewhere, these series are experiencing growing popularity and draw graduate students across various quantitative disciplines and universities.

Classes offered

‘math+econ+code’ masterclass on optimal transport and economic applications. Next edition: online, Jan 18-22, 2021. Past editions: NYU New York, Jan 20-24, 2020. NYU Paris, June 17-21, 2019, NYU NY, Jan 14-18, 2019, NYU NY, Jan 15-20, 2018.

‘math+econ+code’ masterclass on equilibrium transport and matching models in economics. Next edition: June 21-25, 2021. Past editions: Paris+online, June 8-12, 2020, NYU NY, May 21-26, 2018.

‘math+econ+code’ masterclass on submodular optimization in economics. TBA.

‘math+econ+code’ masterclass on networks economics. TBA

Diffusion list

To be added to the ‘math+econ+code’ diffusion list, and to be updated on the upcoming classes, enter your e-mail below:

Subscribe to our mailing list

* indicates required Email Address *

KECD 2195

Advanced topics in microeconometrics: Matching Models and their Applications

Sciences Po, Economics Department, PhD Course Spring 2018

Course information

Instructor: Alfred Galichon.

Schedule: Mondays, 8am-10am, starting January 29, 2016.

Class meets: Jan 29, Feb 5,12,19, Mar 5(+),12,19(+),26, Apr 9,16,23,30.

Location: 28 SP, H103.

Course material: Available on this github repository.

Texts
The first part of the course will be based on my (optional) text:
[OTME] A. Galichon (2016). Optimal Transport Methods in Economics, Princeton University Press.

Other textbooks used for reference (although not required) are:
[TSM] A. Roth and M. Sotomayor. Two-Sided Matching A study in Game-Theoretic Modeling and Analysis, Monographs of the Econometrics Society, 1990.
[DCMS] K. Train. Discrete Choice Methods with Simulation. 2nd Edition. Cambridge University Press, 2009.
[TOT] C. Villani, Topics in Optimal transportation, AMS, 2003.
Course material
Available after each lecture on the class webpage at url http://alfredgalichon.com/microeconometrics2018s.
Description of the Course
This course provides the mathematical and computational tools needed for an operational knowledge of discrete choice models, matching models, and network flow models. A number of economic applications of these concepts will be discussed.
The first part of the course will introduce basic results around Optimal Transportation theory: the Monge-Kantorovich duality, the Optimal Assignment Problem, basic results in Linear Programming, and Convex Analysis. Those concepts will serve as building blocks in the sequel.
The second part will cover discrete choice models, from the classical theory to more recent advances. The classical Generalized Extreme Value (GEV) specification will be recalled, as well as Maximum Likelihood estimation in the parametric case. Comparative statics results will be derived using tools from Convex Analysis, and nonparametric identification will be worked out using Optimal Transport theory. Simulation methods will be covered. A computationally intensive application will be demonstrated.
The third part will be devoted to matching models with stochastic utility, starting with the Transferable Utility (TU) case which is then generalized to Imperfectly Transferable Utility (ITU) including Non-transferable Utility (NTU). Equilibrium computation in the general case will be worked out using techniques from General Equilibrium. The more specific, but empirically relevant logit case, will be efficiently addressed using more the specific techniques or Iterative Fitting. Various algorithms will be described and compared in practice. Moment Matching Estimation and Maximum Likelihood Estimation will be worked out and compared. Several applications, to Collective Models of Family Economics, and to Labor Markets with taxes, will be described.
Time permitting, the fourth and last part will provide an introduction to problems on networks. The basic tools to describe the topology on a network will be described: discrete differential operators, diffusions on networks, shortest paths on networks. The Optimal Transport problem on networks will be formulated, along with its extension to stochastic utility.

Textbooks
The first part of the course will be based on my textbook:
• [OTME] Optimal Transport Methods in Economics (Princeton University Press, in press), a draft of which is available at http://papers.ssrn.com/sol3/papers.cfm?abstract_id=2699381.
Other textbooks used for reference (although not required) are:
• [TSM] A. Roth and M. Sotomayor, Two-Sided Matching A study in Game-Theoretic Modeling and Analysis, Monographs of the Econometrics Society, 1990.
• [DCMS] Train, K.. Discrete Choice Methods with Simulation. 2nd Edition. Cambridge University Press, 2009.
• [TOT] C. Villani, Topics in Optimal transportation, AMS, 2003.
Organization of the Course
Part I: An introduction to Optimal Transport theory
L1. Monge-Kantorovich duality
• Primal and dual formulations
• The Monge-Kantorovich theorem
• Equilibrium and Optimality
Reference: [OTME] chapters 1 and 2.
Complements: [TOT], chapter 1.
L2. The optimal assignment problem
• Linear programming duality
• Purity, Stability
• Computation
Reference: [OTME], ch. 3, [TSM], Ch 8.
Complements: Shapley & Shubik (1972).
L3. The Becker model
• Copulas and comonotonicity
• Positive Assortative Matching
• The Wage Equation
Reference: [OTME], ch. 4. [TOT], Ch. 2.2
L4. Convex conjugacy
• Basics of convex analysis: Convex conjugates, Subdifferential, Fenchel-Young inequality
• Brenier’s theorem
Reference: [OTME], ch. 6. [TOT], ch. 2.1.

Part II: Discrete Choice models
L5. The logit model and its extensions
• The Logit model and its parametric estimation
• The Generalized Extreme Value (GEV) model
• The Daly-Zachary-Williams theorem
Reference: [DCMS], ch. 2-4, Anderson, de Palma & Thisse, Ch. 3, Carlier (2010).
L6. Identification of discrete choice models
• Reformulation as an Optimal Transport problem
• Consequences on the structure of the identifed set
• The Random Scalar Coefficient Model
• Incorporating peer effects
Reference: Hotz and Miller (1993), Chiong et al. (2014), Galichon and Salanie (2015).
L7. Simulation methods
• Simulation methods for parametric estimation
• Probit and the GHK simulator
• Simulation methods for nonparametric estimation
Reference: [DCMS], ch. 5 and 9, Chiong et al. (2014).

Part III: Matching models
L8. Models with transferable utility
• The TU-logit model of Choo and Siow
• Beyond Logit: general heterogeneity
• Simulation methods
• Moment matching estimation; Maximum Likelihood Estimation
Reference: Choo and Siow (2006), Galichon and Salanie (2015).
L9. Estimation of complementarity
• Index models
• Affinity matrix estimation
• Application: marital preference estimation
Reference: Chiappori, Oreffice and Quintana-Domeque (2012), Dupuy and Galichon (2014).
L10. Models with imperfectly transferable utility
• Equilibrium: Existence and Uniqueness
• The ITU-logit model
• Computation
• Maximum Likelihood Estimation
Reference: Galichon, Kominers and Weber (2015).
L11. Models with non-transferable utility
• Models with no idiosyncratic utility shocks
• Models with idiosyncratic utility shocks
Reference: Dagsvik (2000), Menzel (2015), Galichon and Hsieh (2015).

Part IV: Network models
L12. Optimal flow problems
• Basic concepts
• Min-cost flow problem
• Incorporating Stochastic Utility
Reference: [OTME], ch. 8. Koopmans (1949).
L13. Equilibrium flow problems
• Traffic equilibrium with congestion
• The Equilibrium Flow Problem.
Reference: Carlier (2010).
L14. Hedonic models
• Hedonic Equilibrium: definition and existence
• Estimation
Chiappori, McCann & Nesheim (2010), Ekeland, Heckman & Nesheim (2004), Dupuy, Galichon & Henry (2014).

Bibliography
• Anderson, de Palma, and Thisse (1992). Discrete Choice Theory of Product Differentiation. MIT Press.
• Aurenhammer, F. (1987). “Power diagrams: properties, algorithms and applications,” SIAM Journal on Computing.
• Becker, G. (1973). “A theory of marriage, part I,” Journal of Political Economy.
• Carlier, G. (2010). Lecture notes on “Optimal Transportation and Economic Applications.”.
• Chiong, K, Galichon, A., Shum, M. “Duality in dynamic discrete choice models.” Quantitative Economics, forthcoming.
• Choo, E., and Siow, A. (2006). “Who Marries Whom and Why,” Journal of Political Economy.
• Chiappori, P.-A., McCann, R., and Nesheim, L. (2010). “Hedonic price equilibria, stable matching, and optimal transport: equivalence, topology, and uniqueness,” Economic Theory.
• Pierre-André Chiappori, Sonia Oreffice and Climent Quintana-Domeque, C. (2012). “Fatter Attraction: Anthropometric and Socioeconomic Matching on the Marriage Market,” Journal of Political Economy 120, No. 4, pp. 659-695.
• Dagsvik, J. (2000) “Aggregation in matching markets,” International Economic Review 41, 27-57.
• Dupuy, A., and Galichon, A. (2014). “Personality traits and the marriage market,” Journal of Political Economy.
• Dupuy, A., Galichon, A. and Henry, M. (2014). “Entropy Methods for Identifying Hedonic Models,” Mathematics and Financial Economics.
• Ekeland, I., J. Heckman, and L. Nesheim (2004): “Identification and estimation of hedonic models,” Journal of Political Economy.
• Galichon, A. (2016). Optimal Transport Methods for Economics. Princeton University Press, in press.
• Galichon, A., Hsieh, Y.-W. (2015). “Love and Chance: Equilibrium and Identification in a Large NTU matching markets with stochastic choice”.
• Galichon, A., Kominers, S., and Weber, S. (2015). Costly Concessions: An Empirical Framework for Matching with Imperfectly Transferable Utility.
• Galichon, A., and Salanié, B. (2014). “Cupid’s Invisible Hand: Social Surplus and Identification in Matching Models”. Working paper.
• Heckman, J., R. Matzkin, and L. Nesheim (2010). “Nonparametric identification and estimation of nonadditive hedonic models,” Econometrica.
• Hotz, V.J. and Miller, R.A. (1993). “Conditional Choice Probabilities and the Estimation of Dynamic Models”. Review of Economic Studies 60, No. 3 , pp. 497-529.
• Koopmans, T. C. (1949), “Optimum utilization of the transportation system”. Econometrica.
• Menzel, K. (2015). Large Matching Markets as Two-Sided Demand Systems. Econometrica 83 (3), pages 897–941.
• Roth, A., and Sotomayor, M. (1990). Two-Sided Matching A study in Game-Theoretic Modeling and Analysis.
• Shapley, L. and Shubik, M. (1972) “The assignment game I: the core”. International Journal of Game Theory.
• Train, K. (2009). Discrete Choice Methods with Simulation. Cambridge University Press.
• Villani, C. (2003). Topics in Optimal transportation. Lecture Notes in Mathematics, AMS.
• Vohra, R. (2011). Mechanism Design. A Linear Programming Approach. Cambridge University Press.

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.