Instructor: Fuhito Kojima fuhitokojima1979 “at” gmail.com (replace “at” with @) (617) 6991942 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!) 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 reallife 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 TwoSided 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: 46 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 812 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 2030 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) Twosided matching: basic theoryClass 2 (January 22nd): Twosided 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): Onesided 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, 13411378.
*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, 915.
*Alvin E. Roth andMarilda Sotomayor (1990) TwoSidedMatching: A Study in GameTheoretic Modeling and Analysis, Econometric Society Monograph Series, Cambridge University Press. Chapters 1,2,4,5
Tayfun Sonmez, “Manipulation via Capacities in TwoSided Matching Markets,” Journal of Economic Theory, 1997, 77, 197–204.
Tayfun Sonmez, “Can Prearranged Matches be Avoided in TwoSided 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 TwoSided 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, 748780
Class 4
*Bulow, J. and Levin, J. (2006), "Matching and Price Competition." American Economic Review, vol. 96 (3), pp. 652668.
B. Klaus and F. Klijn (2005): “Stable Matchings and Preferences of Couples,” Journal of Economic Theory, 121(1), 75106.
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. 10271031
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. 11531154
Class 5:
*Ma, J., “StrategyProofness and the Strict Core in a Market with Indivisibilities” International Journal of Game Theory, 1994(23), 7583.
Herve Moulin (1995), Cooperative Microeconomics: A GameTheoretic 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, 131137.
*Alvin E. Roth (1982) “Incentive compatibility in a market with indivisibiliTies” Economics Letters 9, 127132.
*Lloyd Shapley and Herbert Scarf (1974) “On cores and indivisibility,” Journal of Mathematical Economics 1, 2328.
LarsGunnar Svensson (1999) “Strategyproof Allocation of Indivisible Goods,” Social Choice and Welfare 16, 557567. *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, 233260.
Chen, Y. and Tayfun Sonmez (2002), “Improving Efficiency of OnCampus 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): 376380
*Alvin E. Roth, Tayfun Sonmez and Utku Unver (2007), “Efficient Kidney Exchange: Coincidence of Wants in Markets with CompatibilityBased Preferences,” American Economic Review, 97(3): 828851.
Class 8: School choice: basic theory
*Atila Abdulkadiroglu and Tayfun Sönmez (2003) “School Choice: A Mechanism Design Approach” American Economic Review, 93, 729747.
*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: 7394, 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 Tiebreaking? 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, 157172.
*Bogomolnaia, A., and H. Moulin (2001), “A New Solution to the Random Assignment Problem,” Journal of Economic Theory, 100, 295328.
Che, YeonK 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, “StrategyProofness 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), 435449.
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 ManytoOne Matchings by Fixed Point Methods,” Journal of Economic Theory, 2004, 115, 358– 376.
Echenique, Federico and Jorge Oviedo, “A theory of stability in manytomany 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 NonCooperative 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, YeonKoo Che, Fuhito Kojima and Paul Milgrom, “Implementing Random Assignment: A Generalization of Birkhoffvon Neumann Theorem,” mimeo Archishman Chakraborty, Alessandro Citanna and Michael Ostrovsky, “TwoSided 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
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
