Mini Lectures on Matching and Market Design
Instructor: Fuhito Kojima
Department of Economics, Stanford University
fuhitokojima1979 “at” gmail.com (replace “at” with @)
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 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.
Slides from the lectures
References
Class 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 andMarilda Sotomayor (1990) Two-SidedMatching: 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.
Class 2
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
lass 10: Random assignment
Classes 3 and 4
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 Efficiency 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.
Che, Yeon-K and Fuhito Kojima, ``Asymptotic Equivalence of Random Priority and Probabilistic Serial Mechanisms,” mimeo
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, “Strategy-Proofness of the Probabilistic Serial Mechanism in Large Random Assignment Problems,” mimeo
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
Web Resources
For more topics in matching and market design, see my course website at Stanford
Econ 182: Honors Market Design
I cover closely related topics in more detail. Another class,
ECON 289: Topics in Game Theory,
is a more advanced topics class. I recommend that you take a look at 182 and then 289.
Al Roth's website (lots of material related to this course; links to researchers; bibliography in matching and market design)
http://kuznets.fas.harvard.edu/~aroth/alroth.html
Market Design Blog (by Al Roth and Peter Coles: there are a lot of topics, especially things that are not covered in this course.)
http://marketdesigner.blogspot.com/