Econ 474: Matching and Market Design
Instructor: Fuhito Kojima
fuhitokojima1979 “at” gmail.com (replace “at” with @)
(617) -699-1942
http://sites.google.com/site/fuhitokojimaeconomics/
Slides from the lectures
I am grateful to Al Roth and Utku Unver for generously allowing me to consult with their slides when I was preparing for the lectures, and to Yusuke Narita for comments.
Slides 01 (for January 15th and 22nd; last updated January 25th, 2009), with supplementary material (January 22nd, 2009)
Slides 02 (for January 29th; January 25, 2009)
Slides 03 (for February 5th; updated February 3rd), with supplementary material (updated February 3rd)
Slides 04 (for February 12th; updated February 8th)
Slides 05 (for February 19th; updated February 16th)
Slides 06 (for February 26th; updated February 23th)
Slides 07 (for March 5th; updated February 28th)
Slides 08 (for March 26th; upadated March 19th)
Web Resources
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/
Paul Milgrom's website (a lot of things on auction, which is a very successful application of game theory and market design. This course does not cover it except for a few, so take a look if you are interested!)
Syllabus (this syllabus is evolving and will be modified as the class proceeds. See also the University website)
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.
Grading
Grading is based on one midterm assignment (30 percent), one class presentation (20 percent) and one final paper (50 percent).
(1) The midterm assignment is a short paper (suggested length: 4-6 pages). It can be a rough idea for the final paper. It can be either an original research (extension of existing theories, or proposal for market design in some markets, for example) or a review of one or more paper(s) by other researcher(s). The paper should be typed (handwriting is not accepted). A joint paper by up to two students are allowed, but in that case the length should be 8-12 pages. The deadline is March 26th in class (if you cannot make it, send me a file by email by the end of the 25th).
(2) Class presentation (length: 25 minutes including questions and answers). The content is either their own research or discussion of a research paper of someone else. Presentations will be on April 2nd, 9th, 16th and 23rd. A joint presentation by up to two students are allowed, but in that case, the length should be 50 minutes.
(3) Suggested length of the final paper is between 15 to 20 pages but it can vary within a reasonable limit. I prefer an original research paper, but a critical literature review (discussion of papers written by others) is also welcome. The paper should be typed (handwriting is not accepted). A joint paper by up to two students are allowed, but in that case the suggested length is 20-30 pages. The deadline is May 1st.
Prerequisite
Basic knowledge in microeconomics is required. Knowledge of game theory is useful but not required. No mathematical background is required beyond basic algebra, but it is important to have basic skills in logical thinking and following mathematical proofs.
Lecture Topics: (the plan is tentative and may change depending on student interests and how the class proceeds)
Class 1 (January 15th): (1) Introduction: preliminary discussion of how matching theory is applied to real world problems.
(2) Two-sided matching: basic theory
Class 2 (January 22nd): Two-sided matching: basic theory (continued)
Class 3 (January 29th): Design of labor markets: National Resident Matching Program (NRMP)
Class 4 (Combined to January 29th): Design of labor markets: recent developments (market size, antitrust, couples)
Class 5 (February 5th): One-sided matching: basic theory
Class 6 (February 12th): Application: Kidney exchange and university housing
Class 7 (Combined to February 12th): Kidney exchange continued: recent developments
Class 8 (February 19th): School choice: basic theory
Class 9 (February 26th): School choice: recent developments
Class 10 (March 5th): Random assignment
Class 11 (March 26th): Matching with complex preferences: theoretical advances of matching theory
Class 12 (Combined to March 26th): Review, Conclusion, and some open questions
Class 13 (April 2nd, April 9th, April 16th, April 23rd): Student presentation
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.
Class 2
*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 3
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
Class 4
*Bulow, J. and Levin, J. (2006), "Matching and Price Competition." American Economic
Review, vol. 96 (3), pp. 652-668.
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, forthcoming.
Kojima, F. (2007), “Matching and Price Competition: Comment”, American Economic
Review, vol. 97 (3), pp. 1027-1031
Fuhito Kojima, “Finding All Stable Matchings with Couples,” mimeo
Niederle, M. (forthcoming), “Competitive Wages in a Match with Ordered Contracts”,
American Economic Review .
*Niederle, M., and Roth, A. E. (2003a), "Relationship Between Wages and Presence of a
Match in Medical Fellowships." JAMA, Journal of the American Medical Association,
vol. 290 (9), pp. 1153-1154
Class 5:
*Ma, J., “Strategy-Proofness and the Strict Core in a Market with Indivisibilities” International Journal of Game Theory, 1994(23), 75-83.
Herve Moulin (1995), Cooperative Microeconomics: A Game-Theoretic Introduction. Princeton University Press, Chapter 3
Alvin E. Roth and Andrew Postlewaite (1977) “Weak versus strong domination in a market with indivisible goods,” Journal of Mathematical Economics
4, 131-137.
*Alvin E. Roth (1982) “Incentive compatibility in a market with indivisibiliTies” Economics Letters 9, 127-132.
*Lloyd Shapley and Herbert Scarf (1974) “On cores and indivisibility,” Journal of Mathematical Economics 1, 23-28.
Lars-Gunnar Svensson (1999) “Strategyproof Allocation of Indivisible Goods,” Social Choice and Welfare 16, 557-567.
*Tayfun Sonmez and Utku Unver, Matching, Allocation, and Exchange of Discrete Resources, Jess Benhabib, Alberto Bisin, and Matthew Jackson (eds.) Handbook of Social Economics, Elsevier, forthcoming (special thanks to M. Utku Unver, who sent me the latest version of the draft)
Class 6:
*Atila Abdulkadiroglu and Tayfun Sönmez (1999) “House Allocation with Existing Tenants” Journal of Economic Theory, 88, 233-260.
Chen, Y. and Tayfun Sonmez (2002), “Improving Efficiency of On-Campus Housing: An Experimental Study,” American Economic Review.
*Alvin E. Roth, Tayfun Sönmez and M. Utku Ünver (2003) “Kidney Ex-
Change” Quarterly Journal of Economics,
Tayfun Sonmez and Utku Unver, “Kidney Exchange with Good Samaritan Donors: A Characterization,” mimeo
Class 7: Kidney exchange continued: recent developments
Hatfield, J. W. (2005), “Pairwise Kidney Exchange: Comment,” Journal of Economic Theory.
*Alvin E. Roth, Tayfun Sönmez, and M. Utku Ünver (2005) “Pairwise Kidney Exchange,” Journal of Economic Theory.
Alvin E. Roth, Tayfun Sönmez, and M. Utku Ünver (2005) . A Kidney Exchange Clearinghouse in New England. American Economic Review Papers
and Proceedings, 95(2): 376-380
*Alvin E. Roth, Tayfun Sonmez and Utku Unver (2007), “Efficient Kidney Exchange: Coincidence of Wants in Markets with Compatibility-Based Preferences,” American Economic Review, 97(3): 828-851.
Class 8: School choice: basic theory
*Atila Abdulkadiroglu and Tayfun Sönmez (2003) “School Choice: A Mechanism Design Approach” American Economic Review, 93, 729-747.
*Atila Abdulkadiroglu, Parag Pathak, and Alvin Roth (2005), “The New York City High School Match,” American Economic Review Papers and Proceedings, 95, 364–367.
*Atila Abdulkadiroglu, Parag Pathak, Alvin Roth and Tayfun Sonmez (2005), “The Boston Public School Match,” American Economic Review Papers and Proceedings, 95, 368–372.
Michel Balinski and Tayfun Sönmez (1999) “A Tale of Two Mechanisms: Student Placement” Journal of Economic Theory 84: 73-94, January 1999.
Ergin, H. and Tayfun Sonmez (2006) “Games of School Choice under the Boston Mechanism,” Journal of Public Economics.
*Fuhito Kojima and Mihai Manea, “Competitive Claims and Resource Allocation by Deferred Acceptance” (2007), mimeo
*Haluk Ergin (2002) “Efficient Resource Allocation on the Basis of Priorities,” Econometrica, 70, 2489–2498.
Class 9: School choice: recent developments
Abdulkadiroglu, Che and Yasuda (2008) “Expanding ‘Choice’ in School Choice,” mimeo.
*Atila Abdulkadiroğlu, Parag Pathak and Alvin E. Roth “Strategyproofness versus Efficiency in Matching with Indifferences: Redesigning the NYC High School Match,” mimeo.
*Erdil, Aytek and Haluk Ergin (2007), “What's the Matter with Tie-breaking? Improving Efficiency in School Choice,” American Economic Review, forthcoming.
*Onur Kesten, “An Alternative Mechanism Design Approach to School Choice in the United States.” mimeo
Parag Pathak and Tayfun Sonmez, “Leveling the Playing Field: Sincere and Strategic Players in the Boston Mechanism,” forthcoming in American Economic Review.
Class 10: 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 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
Class 11:
*Adachi, Hiroyuki, “On a characterization of stable matchings,” Economics Letters, 2000, 68, 43–49.
Echenique, Federico and Jorge Oviedo, “Core Many-to-One Matchings by Fixed Point Methods,” Journal of Economic Theory, 2004, 115, 358– 376.
Echenique, Federico and Jorge Oviedo, “A theory of stability in many-to-many matching,” Theoretical Economics, 2006, 1, 233–273.
Hatfield, John William and Fuhito Kojima, “Group Incentive Compatibility for Matching with Contracts,” 2007. Games and Economic Behavior, forthcoming.
Hatfield, John William and Fuhito Kojima, “Matching with Contracts: Comment,” 2007. American Economic Review, forthcoming.
*Hatfield, John William and Paul R.Milgrom, “Matching with Contracts,” American Economic Review, 2005, 95, 913–935.
Kandori, M., Fuhito Kojima and Yosuke Yasuda, ``Understanding Stable Matchings: a Non-Cooperative Approach,’’ mimeo.
Kelso, A. and Vincent Crawford (1982), “Job matching, coalition
formation, and gross substitutes,” Econometrica, 1982, 50, 1483–1504.
*Ostrovsky, Michael, “Stability in Supply Chain Networks,” American Economic
Review, 2007, forthcoming.
Class 12: There is no assigned paper.
Class 13: Student Presentations
Students are encouraged to present their own work in progress, however preliminary. Alternatively, students can present one of the papers in the above reading list without an asterisk (*), or other papers. The following list suggests possible papers to be presented (some have links. If not, type in in Google and you're likely to find the latest draft), but you are more than welcome to present papers not on the list as long as it is related to the topic of this course.
Atila Abdulkadiroğlu, Parag Pathak, Alvin Roth and Tayfun Sonmez, “Changing the Boston School Choice Mechanism,” mimeo
Atila Abdulkadiroglu and Simon Loertscher (2007), "Dynamic House Allocation", mimeo.
Eric Budish, Yeon-Koo Che, Fuhito Kojima and Paul Milgrom, “Implementing Random Assignment: A Generalization of Birkhoff-von Neumann Theorem,” mimeo
Archishman Chakraborty, Alessandro Citanna and Michael Ostrovsky, “Two-Sided Matching with Interdependent Values,” mimeo.
Lars Ehlers and Jordi Masso, ``Matching Markets under (In)complete Information'', mimeo
Clayton Featherstone, Muriel Niederle, Ex Ante Efficiency in School Choice Mechanisms: An Experimental Investigation
Paul Milgrom, “Assignment Messages and Exchanges,” mimeo.
Antonio Miralles, "Cardinal Bayesian allocation mechanisms without transfers," mimeo
Antonio Miralles, "School choice: the case for the Boston Mechanism," mimeo
Niederle, Muriel, and Alvin E. Roth, “Making Markets Thick: Designing Rules for Offers and Acceptances”, mimeo
Niederle, Muriel and Leeat Yariv, “Matching Through Decentralized Markets”, mimeo
"Incentives in Decentralized Random Matching Markets"
Pais, Joana; forthcoming in Games and Economic Behavior 2008
"School Choice and Information: An Experimenta Study on Matching Mechanisms"
Pais, Joana and Ágnes Pintér; forthcoming in Games and Economic Behavior 2008
Pathak, P., and Tayfun Sonmez, “Comparing Mechanisms by their Vulnerability to Manipulation,” mimeo
Pathak, P. “Lotteries in Student Assignment,” mimeo
Marek Pycia and Utku Unver, “A Theory of House Allocation and Exchange Mechanisms,” mimeo
Michael Schwarz and Bumin Yenmez, “Median Stable Matching,” mimeo
Utku Unver, “Dynamic Exchange Mechanisms and An Application to Paired Kidney Donation, Review of Economic Studies, forthcoming subject to revision.
Ozgur Yilmaz, Kidney Exchange: An Egalitarian Mechanism