Econ 182 Spring 2014
ECON 182: Honors Market Design
Location: Econ 218
Office Hours: MW 10:50-12 or 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. I am planning to invite two or three guest speakers from economics and computer science to talk about their own researches so that you can see how researchers conduct their studies.
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
The grade will depend on 3 problem sets (30 percent), one class presentation and discussion (30 percent) and one final paper (40 percent).
(1) The problem sets are assigned 3 times throughout the course (tentative plan: April 2nd, 16th, and May 12th) and due in one week in class (no late submission is accepted). Most questions are basic ones to consolidate your understanding of basic concepts. You need to write proofs for some questions.
(2) Class presentation is either a student’s own research or discussion of a research paper of someone else. Usually it is very hard to write a new paper, so you can think of a literature review as a default; understanding a paper by someone else is a very important step for writing a creative paper.
(3) Suggested maximum length of the final paper is about 10 pages (tentative plan: due on June 4th Wednesday). You can write an original research paper or a critical literature review. As for (2), think of a literature review as a default option, but I welcome original research paper if you choose to do so.
Prerequisite
Basic knowledge in microeconomics and game theory is useful but 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.
Problem Sets
Class Slides
Class 1 (03/31) + Class 2 (04/02)
Class 3 (04/07)
Class 4 (04/09) + Class 6 (04/16) + Class 7 (04/21)
Class 5 (04/14) Guest Lecture by Paul Milgrom
Class 8 (04/23) Guest Lecture by Al Roth
Class 9 (04/28) + Class 10 (04/30)
Class 11 (05/05) + Class 12 (05/07)
Class 13 (05/12)
Matching under constraint (5/19)
Lecture Topics: The schedule is tentative and evolving.
Class 1: Introduction: preliminary discussion of how matching theory is applied to real world problems.
Class 2: Two-sided matching: basic theory
Class 3: Design of labor markets: National Resident Matching Program (NRMP)
Class 4: Design of labor markets: recent developments (market size, couples, etc.)
Class 5: One-sided matching: basic theory
Class 6: Application: Kidney exchange and university housing
Class 7: Kidney exchange continued: recent developmentsｓ
Class 8: School choice: basic theory
Class 9: School choice: recent developments
Class 10: Random assignment; Using Lottery for Fair Allocations
Class 11: Random assignment; Applications
Class 12: Matching with contracts: Basic Theory
Class 13: Matching with contracts: Applications
Class 14: Mechanism Design Theory
Class 15: Mechanism Design Theory (2)
Class 16: Student Presentations
Class 17: Student Presentations
Class 18: Student Presentations
In addition, I am planning to invite 2 or 3 guest speakers (current plan: Al Roth, Paul Milgrom (04/14) and Mohammad Akbarpour) . The exact dates of the classes are subject to change as we schedule the guest speakers.
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 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.
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
I. Ashlagi, M. Braverman, and A. Hassidim (2011) “Stability in Matching Markets with Complementarities,” working paper
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.
Fuhito Kojima, “Finding All Stable Matchings with Couples,” mimeo
F. Kojima, P.A. Pathak, and Alvin E. Roth (2010), “Matching with Couples: Stability and Incentives,” working paper
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 In-
troduction. Princeton University Press, Chapter 3
Alvin E. Roth and Andrew Postlewaite (1977) “Weak versus strong domina-
tion in a market with indivisible goods,” Journal of Mathematical Economics
4, 131-137.
*Alvin E. Roth (1982) “Incentive compatibility in a market with indivisibili-
Ties” 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.
Class 6:
*Atila Abdulkadiroglu and Tayfun Sönmez (1999) “House Allocation with Ex-
isting 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 Ex-
change 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 Mecha-
nism Design Approach” American Economic Review, 93, 729-747.
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.
Class 9: School choice: recent developments
Abdulkadiroglu, Che and Yasuda (2008) “Expanding ‘Choice’ in School Choice,” mimeo.
*Atila Abdulkadiroglu, 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
Fuhito Kojima and Mihai Manea (2010), Axioms for Deferred Acceptance, Econometrica.
Parag Pathak and Tayfun Sonmez, “Leveling the Playing Field: Sincere and Strategic Players in the Boston Mechanism,” forthcoming in American Economic Review.
Class 10&11: 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
Class 12&13: Matching with Consracts
*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.
Hatfield, John William and Fuhito Kojima, “Substitutes and Stability in Matching with Contracts,” 2007. Journal of Economic Theory.
Hatfield, John William and Fuhito Kojima, “Matching with Contracts: Comments,” 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, ``Bridging the gap between cooperative and noncooperative games: simple economics of matching,’’ 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.
*Tayfun Sonmez and Tobias Switzer “Matching with (Branch-of-Choice) Contracts at the United States Military Academy”, forthcoming, Econometrica.
Class 14&15: Mechanism Design
*P Jehiel, B Moldovanu, Efficient design with interdependent valuations, Econometrica
Archishman Chakraborty, Alessandro Citanna and Michael Ostrovsky, Two-Sided Matching with Interdependent Values Journal of Economic Theory, forthcoming.
M. Perry and P. Reny, "An Efficient Multi-Unit Ascending Auction." Motty Perry and Philip J. Reny; The Review of Economic Studies, 2005, 72(2), pp. 567.
*Jehiel, P., M. Meyer-ter-Vehn, B. Moldovanu and W. R. Zame, (2006): “The Limits of ex post Implementation,” Econometrica, 74(3), 585-610.
Tadashi Hashimoto (2011) “Generic Impossibility of Partial Ex Post Implementation with General Utility Functions”
Class 16-19: 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, 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.
A Theory of School-Choice Lotteries (with Onur Kesten) Boston College Working Papers in Economics, No: 737
Dur and Unver, Tuition Exchange
Gabriel Carroll, When are Local Incentive Constraints Sufficient? / Online appendix (Econometrica, forthcoming)
Gabriel Carroll, On Mechanisms Eliciting Ordinal Preferences
Gabriel Carroll, A General Equivalence Theorem for Allocation of Indivisible Objects
Gabriel Carroll, Efficient Random Assignment with Constrained Rankings
Mennle and Seuken;
Bumin Yenmez and Michael Schwarz, “Median Stable Matching,” mimeo
Valuing Prearranged Paired Kidney Exchanges: A Stochastic Game Approach (with Murat Kurt, Mark Roberts, and Andrew Schaefer) Boston College Working Papers in Economics, No: 785; revision requested from Operations Research
Tadashi Hashimoto; Two Axiomatic Approaches to the Probabilistic Serial Mechanism (with Daisuke Hirata, Onur Kesten, Morimitsu Kurino, and Utku Ünver). Theoretical Economics, 9 (2014), 253--277.
The Generalized Random Priority Mechanism with Budgets
http://www.kellogg.northwestern.edu/research/math/seminars/201314/Rann%20SmorodinskyBagLunchOct10.pdf
Strategy-proof mechanisms for two-sided matching with minimum and maximum quotas
…, D Fragiadakis, A Iwasaki, P Troyan, M Yokoo - Proceedings of the 11th …, 2012 - dl.acm.org
Abstract We consider the problem of allocating objects to agents when the objects have
minimum quotas. There exist many real-world settings where minimum quotas are relevant.
For example, in a hospital-resident matching problem, unconstrained matching may ...
Cited by 5 Related articles All 5 versions Cite Save More
[PDF] from osaka-u.ac.jp
[PDF] Strategyproof matching with minimum quotas
http://pycia.bol.ucla.edu/pycia-unver-DRM.pdf
Yeon-Koo Che and Youngwoo Koh, Decentralized College Admissions, mimeo