Lectures on matching and market design
(summer 2015)
Office Hours: by appointment
Instructor: Fuhito Kojima
fuhitokojima1979 “at” gmail.com (replace “at” with @)
http://sites.google.com/site/fuhitokojimaeconomics/
Syllabus
How to match people to other people or goods is an important problem in society. Just think of some examples such as (1) student placement in schools, (2) labor markets where workers and firms are matched, and (3) organ donation, in which patients are matched to potential donors. The economics of “matching and market design” has analyzed these problems and improved real-life institutions in recent years. For example, economists have helped (1) NYC and Boston design their school choice programs, (2) medical communities reorganize their hiring procedure, and (3) organize systematic kidney exchange mechanisms to give kidneys to as many patients as possible. This is a subject that attracted much attention in 2012, as the Nobel Prize in economics was awarded to Alvin Roth at Stanford and Lloyd Shapley at UCLA who are pioneers in matching and market design.
This course introduces the theory of matching and market design, and discusses how the theory can be applied to these and other applications. I will put emphasis on recent advances in the topic and present open questions so that interested students can promptly come to the frontier and begin their own research.
The basic textbook is Two-Sided Matching by Roth and Sotomayor (1990) from Cambridge University Press, but I will also cover recent journal articles and working papers. I have just finished a survey paper, Recent Developments in Matching Theory and its Practical Applications to appear in "Advances in Economics and Econometrics: 11th World Congress", and this will be highly relevant to this class as well. Comments are greatly appreciated!
Grading A final paper. Page limit is 5 pages, and due at 3pm on July 31st (send an electric file to my email). You should write a critical review of one paper of your choice from the Reading List for Final Papers at the bottom of this website.
Prerequisite
Basic knowledge in microeconomics and game theory is useful, but it's not required. A solid background in mathematics is essential to the course: In terms of specific knowledge, I use limit operations, simple analysis such as differentiation and optimization occasionally, but not much is needed. However, I do stress proofs, and math in market design is somewhat unique, in the sense that it uses a lot of discrete math arguments. It is very important that you have willingness to follow a long chain of arguments of proofs, although each step tends to be preliminary.
Class Slides
Lecture Topics: The schedule is tentative and evolving.
Topic 1: Introduction: preliminary discussion of how matching theory is applied to real world problems.
(i) Two-sided matching: basic theory
(ii) Design of labor markets: National Resident Matching Program (NRMP)
Topic 2: Random assignment; Using Lottery for Fair Allocations
(i) Basic models
(ii) Applications
Topic 3: Matching with Constraints
(i) Basic questions
(ii) Theory
References
Topic 1
Alvin E. Roth (2002) The Economist as Engineer: Game Theory, Experimentation,
and Computation as Tools for Design Economics. Econometrica 70, 1341-1378.
*Roth, Alvin E. "What have we learned from market design?" Hahn Lecture, Economic Journal, 118 (March), 2008, 285–310.
Al Roth’s webpage
http://kuznets.fas.harvard.edu/~aroth/alroth.html
discusses many topics in market design and is worth seeing.
*David Gale and Lloyd Shapley (1962), “College Admissions and the Stability of Marriage” American Mathematical Monthly, 69, 9-15.
*Alvin E. Roth and Marilda Sotomayor (1990) Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis, Econometric Society Monograph Series, Cambridge University Press. Chapters 1,2,4,5
Tayfun Sonmez, “Manipulation via Capacities in Two-Sided Matching Markets,” Journal of Economic Theory, 1997, 77, 197–204.
Tayfun Sonmez, “Can Pre-arranged Matches be Avoided in Two-Sided Matching Markets?” Journal of Economic Theory, 1999.
Immorlica, N. and Mahdian, M. (2005), “Marriage, Honesty, and Stability,” SODA 2005, pp. 53–62.
*Kojima, F. and Pathak, P. A. (2008), “Incentives and Stability in Large Two-Sided Matching Markets,” forthcoming, American Economic Review.
*Alvin E. Roth and Elliott Peranson (1999) “The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design,” American Economic Review, 89 (4) September, 748-780
I. Ashlagi, M. Braverman, and A. Hassidim (2014) “Stability in Matching Markets with Complementarities,” Operations Research
B. Klaus and F. Klijn (2005): “Stable Matchings and Preferences of Couples,” Journal of Economic Theory, 121(1), 75-106.
B. Klaus, F. Klijn, T. Nakamura (2007): “Corrigendum: Stable Matchings and Preferences of Couples,” Journal of Economic Theory.
Fuhito Kojima, “Finding All Stable Matchings with Couples,” mimeo
F. Kojima, P.A. Pathak, and Alvin E. Roth (2013), “Matching with Couples: Stability and Incentives,” Quarterly Journal of Economics
SangMok Lee, (2014) Incentive Compatibility of Large Centralized Matching Markets [PDF]
Itai Ashlagi, Yash Kanoria, and Jacob Leshno (2013) Unblanaced Random Matching Markets: the Stark Effect of Competition, mimeo
Yeon-Koo Che, Jinwoo Kim, and Fuhito Kojima, Stable Matching in Large Economies (2015), mimeo
Topic 2: Random assignment
Abdulkadiroglu, A., and T. Sonmez (1998): “Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems,” Econometrica, 66, 689
Abdulkadiroglu, A., and T. Sonmez (2003) “Ordinal Effciency and Dominated Sets of Assignments,” Journal of Economic Theory, 112, 157--172.
*Bogomolnaia, A., and H. Moulin (2001), “A New Solution to the Random Assignment Problem,” Journal of Economic Theory, 100, 295{328.
E. Budish, Y-K. Che, F. Kojima, and Paul R. Milgrom (2012) “Designing Random Allocation Mechanisms: Theory and Applications” forthcoming, American Economic Review.
Che, Y-K and Fuhito Kojima (2010), ``Asymptotic Equivalence of Random Priority and Probabilistic Serial Mechanisms,” Econometrica.
Katta, A.-K. and J. Sethuraman, “A solution to the random assignment problem on the full preference domain” (2006), Journal of Economic Theory.
Kesten, O, “Why Do Popular Mechanisms Lack Efficiency in Random Environments?” mimeo
Fuhito Kojima and Mihai Manea, “Incentives in the probabilistic Serial Mechanism,” Journal of Economic Theory.
Fuhito Kojima, “Random Assignment of Multiple Indivisible Objects” (2007), forthcoming, Mathematical Social Sciences.
McLennan A., “Ordinal efficiency and the polyhedral seperating hyperplane theorem,” Journal of Economic Theory 105 (2002), 435-449.
Yilmaz, O., “House Allocation with Existing Tenants: A New Solution,” mimeo
Topic 3: Matching with Constraints
Roth and Sotomayor (1990), Chapters 2 and 5.
Roth, A.E., "The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory," Journal of Political Economy, 92, 1984, 991-1016.
· *Roth (1986), On the allocation of residents to rural hospitals: a general property of two-sided matching markets, Econometrica
· *Yuichiro Kamada and Fuhito Kojima, Efficient Matching under Distributional Constraints: Theory and Applications, 2015, American Economic Review
Peter Biro, Tamas Fleiner, Robert Irving, and David Manlove, "The College Admissions Problem with Lower and Common Quotas", (2010), Theoretical Computer Sience.
· John William Hatfield and Fuhito Kojima, “Substitutes and Stability for Matching with Contracts” (2010), Journal of Economic Theory, 145, 1704-1723.
Goto, Hashimoto, Iwasaki, Kawasaki, Ueda, Yasuda, and Yokoo, "Strategy-Proof Matching with Regional Minimum Quotas" (2014) AAMA 2014.
Fragiadakis, Iwasaki, Troyan, Ueda, and Yokoo, Strategy-Proof Matching with Minimum Quotas (2015), forthcoming, ACM Transactions on Economics and Computation
Daniel Fragiadakis and Peter Troyan, Market Design under Distributional Constraints: Diversity in School Choice and Other Applications (2015), mimeo
Yuichiro Kamada and Fuhito Kojima, "Stability Concepts in Matching under Distributional Constraints ", mimeo
Yuichiro Kamada and Fuhito Kojima, General Theory of Matching under Distributional Constraints (2015), mimeo
Fuhito Kojima, Akihisa Tamura, and Makoto Yokoo, Designing Matching Mechanisms under Constraints: An Approach from Discrete Convex Analysis, (2015), mimeo
Reading List for Final Papers:
Umut Dur and Utku M. Unver, Tuition Exchange, mimeo (R&R JPE)
SangMok Lee and Leeat Yariv, On the Efficiency of Stable Matchings in Large Markets [PDF]
Marek Pycia and Bumin Yenmez, Matching with Externalities, mimeo
Mohammad Akbarpour and Afshin Nikzad, Approximate Random Allocation Mechanisms, mimeo
Goto, Hashimoto, Iwasaki, Kawasaki, Ueda, Yasuda, and Yokoo, Strategy-Proof Matching with Regional Minimum Quotas, AAMAS-2014
Sampath Kannan, Jamie Morgenstern, Aaron Roth, and Steven Wu, Approximately Stable, School Optimal, and Student-Truthful Many-to-One Matching (via Differential Privacy), SODA 2015
Eduardo Azevedo and John William Hatfield, Complementarity and Multidimensional Heterogeneity in Large Matching Markets, mimeo
Thanh Nguyen and Rakesh Vohra, Near Feasible Stable Matchings with Complementarities, mimeo
Yinghua He, Antonio Miralles, and Jianye Yan, "Competitive Equilibrium from Equal Incomes for Two-Sided Matching" [PDF], mimeo
Tamas Fleiner and Zsuzsanna Janko, Choice Function Based Two-Sided Markets: Stability, Lattice Property, Path Independence and Algorithms, mimeo
Mohammda Akbarpour and Afshin Nikzad, Approximate Random Allocation Mechanisms, mimeo
Itai Ashlagi and Peng Shi, Improving Community Cohesion in School Choice via Correlated-Lottery Implementation, Operations Research, forthcoming.
Michael Ostrovsky and Renato Paes Leme, Gross Substitutes and Endowed Assignment Valuations, TE
Fuhito Kojima, Recent Developments in Matching Theory and its Practical Applications to appear in "Advances in Economics and Econometrics: 11th World Congress"