ECON 182: Honors Market Design
Class Time: Tuesdays and Thursdays, 11:00-12:50
Location: Econ 218
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. 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 or more class presentations 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 30th) 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) The class presentation is about 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 on your own in a short amount of time, 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) The suggested maximum length of the final paper is about 10 pages (tentative plan: due on June 4th Thursday). You can write an original research paper or a critical literature review. As is the case for (2), think of a literature review as a default option, but I welcome an original research paper if you choose to do so. If you choose to do so, write to me in advance so that I can suggest if your topic is in a good direction.
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.
Problem Sets
Class Slides
Class 1 (03/31) + Class 2 (04/02) + Class 3(04/07)
Class 4 (04/09) + Class 5 (04/14) + Class 6 (04/16)
Class 7 (04/21) + Class 8 (04/23)
Class 9 (04/28) + Class 10 (04/30)
Class 11 (05/05)
Class 12 (5/07)
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: One-sided matching: basic theory
Class 5: Application: Kidney exchange and university housing
Class 6: Kidney exchange continued: recent developmentsｓ
Class 7: School choice: basic theory
Class 8: School choice: recent developments
Class 9: Random assignment; Using Lottery for Fair Allocations
Class 10: Random assignment; Applications
Class 11: Combinatorial Assignment Problem
Class 12: Matching with Constraints
In addition, depending on availability and interest, I might invite 2 or 3 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
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
Class 4-6:
*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.
*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
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 7-8: School choice:
*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.
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 9-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 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 11: Combinatorial Assignment Problem
*Eric Budish, The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes
*Eric Budish and Estelle Cantillon, The Multi-Unit Assignment Problem: Theory and Evidence from Course Allocation at Harvard
Eric Budish, Yeon-Koo Che, Fuhito Kojima, and Paul Milgrom, Implementing Random Assignments: A Generalization of the Birkhoff-von Neumann Theorem (2009),
Kojima, F, Random Assignment of Multiple Indivisible Objects (2007), forthcoming, Mathematical Social Sciences.
Fuhito Kojima, Efficient Resource Allocation under Multi-unit Demand (2013), Games and Economic Behavior
John William Hatfield, Strategy-proof, efficient, and nonbossy quota allocations, Social Choice and Welfare, 2009.
Mihai Manea, Serial dictatorship and Pareto optimality, Games and Economic Behavior, 2007.
Aanund Hylland and Richard Zeckhauser, The efficient allocation of individuals to positions, JPE 1979.
Class 12: 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
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.
NOTE: I include links to some of the papers, but check the author's website for the latest version (in economics, often the authors keep the latest draft on their personal websites, and frequently update the paper before publication)
Haluk Ergin, Tayfun Sonmez, and Utku M. Unver, “Lung Exchange,” [ PDF ], mimeo
Umut Dur and Utku M. Unver, Two-Sided Matching via Balanced Exchange: Tuition and Worker Exchanges, 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
Bumin Yenmez, College Admissions, mimeo
John William Hatfield, Scott Duke Kominers, Alexandru Nichifor, Michael Ostrovsky, and Alexander Westkamp, Chain Stability in Trading Networks, April 2015, Revise and resubmit, Econometrica.
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
Gabriel Carroll, On Mechanisms Eliciting Ordinal Preferences
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
Ivan Balbuzanov, Short Trading Cycles: Kidney Exchange with Strict Ordinal Preferences, mimeo
Onur Kesten and Utku M. Unver, A Theory of School-Choice Lotteries , TE
Eric Budish and Judd Kessler, Changing the Course Allocation Mechanism at Wharton, mimeo
Itai Ashlagi and Peng Shi, Optimal Allocation Without Money: an Engineering Approach, Management Science, forthcoming
Eric Budish and Eduardo Azevedo, Strategy-Proofness in the Large, mimeo
Itai Ashlagi and Peng Shi, Improving Community Cohesion in School Choice via Correlated-Lottery Implementation, Operations Research, forthcoming.
John William Hatfield, Scott Duke Kominers, Alexandru Nichifor, Michael Ostrovsky, and Alexander Westkamp, Substitutability in Trading Networks
Michael Ostrovsky and Renato Paes Leme, Gross Substitutes and Endowed Assignment Valuations, TE
Itai Ashlagi and Afshin Nikzad, What matters in tie-breaking rules? How competition guides design.
Itai Ashlagi, Afshin Nikzad, Assaf Romm, Assigning more students to their top choices: A tiebreaking rule comparison (extended abstract in EC 15).
Fuhito Kojima, Recent Developments in Matching Theory and its Practical Applications, mimeo
Fuhito Kojima, Akihisa Tamura, and Makoto Yokoo, Designing Matching Mechanisms under Constraints: An Approach from Discrete Convex Analysis, mimeo
Yeon-Koo Che and Olivier Tercieux, Efficiency and Stability in Large Matching Markets, mimeo
Yeon-Koo Che and Olivier Tercieux, An Analysis of Top Trading Cycles in Two-Sided Matching Markets, mimeo
Yeon-Koo Che and Olivier Tercieux Payoff Equivalence of Efficient Mechanisms in Large Matching Markets, mimeo