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

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