Econometrics, Quantitative Economics, Data Science

Author Archive

equiprice_workshops

EQUIPRICE workshops

Upcoming workshops

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

EQUIPRICE logo

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

equiprice_lectures

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 logo

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

equiprice_team

EQUIPRICE: Equilibrium methods for Resource Allocation and Dynamic Pricing

European Research Council consolidator grant (ERC-CoG) No. 866274, 2020-2025

CORE Equiprice team

Principal investigator:

Postdoctoral researchers:

Research assistants:

Jules Baudet (Masters student at ENS).
Projects: math+econ+code, equiprice lunches, replication, data analytics
Gabriele Buontempo (Masters student at Sciences Po). Projects: data analytics, dissemination
Nour Cherif (College student at Sciences Po). Projects: math+econ+code, dissemination
Akshaya Jose Devasia (Masters student at Sciences Po). Projects: math+econ+code, dissemination
Bastien Patras (Masters student at Sciences Po, Centrale-Supélec and ENS Paris-Saclay). Projects: replication, data analytics

mec_equil_archive_2020-06

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

June 8-12, 2020

Online course

 

MEC logo
An event part of the ‘math+econ+code’ series.


 

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.

Outline

• Monday 5/21: competitive equilibrium with gross substitutes
• Tuesday 5/22: demand beyond quasi-linearity
• Wednesday 5/23: bundled demand
• Thursday 5/24: empirical models of demand and matching
• Friday 5/25: network congestion

Synopsis

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.”

mec_optim_archive_2020-01

ECON-GA 3503

‘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).

equiprice_lunch-seminars

EQUIPRICE lunch seminars

Equiprice lunch seminars are hybrid (in person and / or virtual, depending on the COVID context) lunch seminars designed to serve as technical tutorials or presentation of work in progress in relation to the scientific agenda of the ERC-sponsored project EQUIPRICE. Unless noted ‘internals,’ seminars are public and open to all, but registration to the in person event is required 48 hours before.

Note: All times indicated on this page refer to the Paris time zone.

Upcoming talks:

Past talks:

  • February 10 2022, 12pm-1pm (online), Mert Unsal (Ecole Polytechnique) will present ‘running C++ on jupyter notebook: the xeus cling kernel’.
  • February 3 2022, 12pm-1pm (online), Professor Claire Mathieu (CNRS, Irif) will present “Stable Matching in Practice”.

  • ***Wednesday*** January 12 2022, *** 2pm-3pm *** (online), Dr. Antoine Jeanjean (OPT2A) will present “Operations research: a love story between mathematics and computer science.”
  • December 16 2021, 12pm (online), Dr. Denis Merigoux (INRIA) will present “Turning law into micro-simulation code with the Catala programming language”.

  • December 9 2021, 12pm (online), Anatole Gallouet (Grenoble INP) will present “Numerical resolution of semi-discrete Generated Jacobian equations”.

  • November 25 2021, 12pm (hybrid), Professor Benoit Rottembourg (INRIA) will present “Dynamic pricing: constraints, elasticity and algorithmic manipulation”. 
  • November 18 2021, 12pm (hybrid). Professor César Ducruet (Paris-Nanterre University) will present “Inter-city networks: a maritime perspective”.
  • October 7, 2021. Reading of Roth,  Rothblum and Vande Vate’s Stable Matchings, Optimal Assignments, and Linear Programming.
  • September 12 2021, 12:30pm. Pauline Corblet’s job market paper’s practice talk.
  • July 15 2021, 1pm. Loan Tricot on Bertsekas’ auction algorithm.
  • ***WEDNESDAY*** June 23 2021, ***12.30pm-2pm***. Pauline Corblet. Job market practice talk.
  • June 17, 1pm. Loan Tricot on “Reconstructing the order flow with optimal transport”.

  • June 3 2021, 1pm. Bastien Patras on BLP and MPEC.
  • *** Tuesday*** May 25 2021, 1pm. Reading of The Contraction Mapping Approach to the Perron-Frobenius Theory: Why Hilbert’s Metric?.
  • May 20 2021, 1pm (public). Professor Guillaume Carlier (Paris-Dauphine University), on “the linear convergence of the multi-marginal Sinkhorn algorithm.”
  • April 29 2021, 1pm. Reading of Bubeck and Cesa-Bianchi’s Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems  chapters 1-3.
  • April 15 2021, 1pm. Flavien Léger on Bregman divergence and gradient descent (part 2).
  • April 8 2021, 1pm. Flavien Léger on Bregman divergence and gradient descent (part 1).
  • March 25 2021, 1pm. Pauline Corblet on the link between Gale and Shapley and some iterative methods in applied mathematics.
  • March 18 2021, 1pm. Jules Baudet on course allocation mechanisms (continued).
  • March 4 2021, 1pm. Pauline Corblet on many-to-one matching problems.
  • February 18 2021, 1pm (public). Jules Baudet on course allocation mechanisms (continued).
  • February 11 2021, *** 5pm *** (public). Professor Xin Chen (University of Illinois) on S-convexity.
  • January 14 2021, 1pm (public). Flavien Léger on Chambolle-Pock.
  • January 7 2021, 1pm (public). Jules Baudet on “the multi-unit assignment problem: matching students to course schedules”.
  • December 10 2020, *** 5pm *** (public). Professor Pierre-Olivier Weill (UCLA) on optimal transport in asset pricing problems.
  • November 26 2020, 1pm (public). Flavien Léger on computing large-scale regularized optimal transport problems.
  • November 12 2020, 1pm. Alfred Galichon on ‘EQUIPRICE: research program and challenges’.
  • October 29 2020, 1pm (public). Jules Baudet will be presenting on ‘Cloud Computing and Containers part 3: Understanding Docker containers, continued’.
  • October 22 2020, 1pm (public). Jules Baudet will be presenting on ‘Cloud Computing and Containers part 2: Understanding Docker containers’
  • October 15 2020, 1pm (public). Jules Baudet on kidney exchanges.
  • October 8 2020, 1pm (public). Flavien Léger on ‘The back-and-forth method in optimal transport’
  • September 24 2020, 1pm (public). Jules Baudet on ‘Cloud Computing and Containers part 1: Understanding Docker containers’

Sponsored by the European Research Council grant EQUIPRICE

EQUIPRICE logo

world-congress


Slides for my talk ‘Optimal transport in Economics’, session ‘Frontiers of Modern Econometrics,’ World congress of the Econometric society, August 17, 2020.

equiprice

European Research Council consolidator grant (ERC-CoG) No. 866274, 2020-2025

Funded by the EU

Project description

This 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.  Applications to various fields such as labor economics, family economics, international trade, urban economics, industrial organization, etc. are investigated.

This project is hosted by the department of economics at Sciences Po.

The scientific agenda

The EQUIPRICE project is built upon a rigorous scientific agenda at the intersection of economics, data science, mathematics and computation. See here.

Events

EQUIPRICE Lunch Seminars

The EQUIPRICE team meets bimonthly on Thursdays for lunch seminars that hold in person or remotely to discuss research in progress by the team members, or summarize existing research on a topic. Occasionally, an external researcher is invited to present. Some of these meetings are public. See schedule here.

Seasonal events

Winter: ‘math+econ+code’ January masterclass

A ‘math+econ+code’ masterclass is held over one week in the month of January. Topics usually revolve around the economic applications of optimal transport. Find out more information here.

Spring: EQUIPRICE lectures

Topical lectures by EQUIPRICE team members and invited researchers are given during the Spring semester. See a schedule here.

Summer: ‘math+econ+code’ June masterclass

Another ‘math+econ+code’  masterclass is held in June, on a theme which is in general complementary to the January class, typically dealing with Walrasian equilibrium with gross substitutes. More information here.

Fall: EQUIPRICE workshops

A research workshop is organized yearly in the Fall. See a list of past and upcoming workshops here.

EQUIPRICE code & Papers

Open-source code is developed a product of the EQUIPRICE research effort. Find out more here.

Publicly available manuscript version of the papers written with the support of EQUIPRICE are listed here.

The team

The core EQUIPRICE team is made of a principal investigator, post-doctoral researchers, and graduate student assistants. Meet the equiprice team!

Job posting for the EQUIPRICE project are advertised here.

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





PSE lectures

Short course

Optimal transport and economic applications

PSE summer school, June 22-26, 2020

Content

This short course is focused on optimal transport theory and matching models and their applications to economics, in various fields such as labor markets, economics of marriage, industrial organization, matching platforms, networks, and international trade. It will provide the crossed perspectives of theory, empirics and computation. A particular emphasis will be given on computation (R and Python). This course is partly based on Galichon’s 2016 monograph, Optimal Transport Methods in Economics. Princeton University Press.

Schedule

Wednesday, June 24, 9am-12:30pm
Thursday, June 25, 9am-12:30pm
Friday, June 26, 9am-11am

Course material

The lecture slides will be available before each lecture.

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

• intro to optimal transport (3h)
• multinomial choice (3h)
• matching models (3h)

mec_equil_archive_2018-05

ECON-GA 3503

‘math+econ+code’ masterclass on competitive equilibrium

NYU Courant Insitute, May 21-26, 2018 (30 hours)

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 six 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.
This NYU course has no equivalent in peer universities. An earlier course with a different focus but sharing the same format and philosophy was taught at NYU in January 2018; it was very popular and was attended by students from a number of other universities.

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.

Teaching staff

A. Galichon (NYU Econ+Math): morning lectures
K. O’Hara (NYU Econ): afternoon presentations (coding)
Y. Sun (NYU Math): afternoon presentations (machine learning)
O. Ghelfi (NYU Econ): research assistantship

Course material

A Github repository containing the course material (lecture slides, datasets, code) will made available at the start of the course. Coding assignments will be uploaded on a separate repository located here.

Practical information

• Schedule: Mon 5/21 — Sat 5/26, 2018, 9am-1pm (morning); 2pm-3pm (afternoon). Location: Courant building (251 Mercer St), room 202.
• Credits: 2, assessed through participation in the coding assignments or a short final paper, at the student’s option.
• NYU students will need to register on Albert. Non-NYU students need to contact the lecturer: galichon@cims.nyu.edu.

Course material

Available before the lectures.

Outline

• Monday 5/21: competitive equilibrium with gross substitutes
• Tuesday 5/22: demand beyond quasi-linearity
• Wednesday 5/23: bundled demand
• Thursday 5/24: empirical models of demand
• Friday 5/25: empirical models of matching
• Saturday 5/26: equilibrium on networks

Synopsis

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.