Econ 289: Topics in Game Theory
Class Time: Tuesdays and Thursdays, 1:15-3:05
Location: Tuesdays at 160-B36 (Wallenberg Hall, Main Quad),
Thursdays at Econ 106
Office Hours: by appointment
Instructor: Fuhito Kojima
fuhitokojima1979 “at” gmail.com (replace “at” with @)
http://sites.google.com/site/fuhitokojimaeconomics/
(This syllabus is evolving: Please check the latest version frequently. Last updated: 03/31/2015)
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 is a topics course in game theory. We discuss mechanism/market design, especially theory and application of matching theory.This class builds on material covered in Econ 285.
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 first few weeks (tentative plan: 3 weeks) are delivered in the lecture style. Then the rest of the course is based on student presentations of recent research papers. Depending on availability of time (which depends on enrollment) and interest, I may invite outside speakers for guest lectures.
Grading
Grading will be based on class participation (discussion, student presentations) and a final paper (suggested length is 10 pages; it can be either your own research idea or you can write a critical literature review).
Prerequisite
Game theory at the 1st year PhD level. Also it is strongly recommended that you have taken Econ 285, because many of the topics are based on the material covered there.
If not, please familiarize yourself with the topic, by taking a look at slides at, for example,
http://www.stanford.edu/~niederle/marketdesign2012.htm
Textbooks
The recommended textbook is
Two-Sided Matching by Roth and Sotomayor (1990) from Cambridge University Press.
I will also assign research papers.
Slides
Lecture Topics (the plan is tentative and may evolve depending on student interests and how the class proceeds). Papers with * are the main readings for the class.
Class 1: Introduction/ Design of Labor Market Clearinghouses
*Roth and Sotomayor (1990), Chapters 2-4.
Gale, David and Lloyd Shapley (1962), “College Admissions and the Stability of Marriage” American Mathematical Monthly, 69, 9-15.
*Kojima, F. and Pathak, P. A. (2008), “Incentives and Stability in Large Two-Sided Matching Markets,” American Economic Review 99, pp 608-627.
*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
Kojima, F., Parag A. Pathak, and Alvin E. Roth (2013) "Matching with Couples: Stability and Incentives", Quarterly Journal of Economics.
Immorlica, N. and Mahdian, M. (2005), “Marriage, Honesty, and Stability,” SODA 2005, pp. 53–62.
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
Itai Ashlagi, Mark Braverman, and Avinatan Hassidim, Stability in Large Matching Markets with Complementarities, forthcoming, Operations Research.
Yeon-Koo Che, Jinwoo Kim, and Fuhito Kojima, Stable Matching in Large Economies (2015), mimeo
Class 2: Matching with Distributional 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
Class 3: Design of Random Assignment Mechanisms (1)
Abdulkadiroglu, A., and T. Sonmez (2003) “Ordinal Efficiency and Dominated Sets of Assignments,” Journal of Economic Theory, 112, 157—172.
Abdulkadiroglu, A., and T. Sonmez (1998): “Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems,” Econometrica, 66, 689-698.
*Bogomolnaia, A., and H. Moulin (2001), “A New Solution to the Random Assignment Problem,” Journal of Economic Theory, 100, 295-328.
*Che, Yeon-Koo and Fuhito Kojima, “Asymptotic Equivalence of Random Priority and Probabilistic Serial Mechanisms,” forthcoming, Econometrica.
Hylland and Zeckhauser (1979), “The efficient allocation of Individuals to Positions”, Journal of Political Economy.
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?,” forthcoming, journal of economic theory.
*Fuhito Kojima and Mihai Manea, “Incentives in the Probabilistic Serial Mechanism,” forthcoming, 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
Manea, Mihai, “Asymptotic Ordinal Inefficiency of Random Serial Dictatorship,” forthcoming, Theoretical Economics.
Class 4: Design of Random Assignment Mechanisms (2):
Hylland and Zeckhauser (1979), “The efficient allocation of Individuals to Positions”, Journal of Political Economy.
*Eric Budish, Yeon-Koo Che, Fuito Kojima, and Paul Milgrom (2013), “Designing Random Allocation Mechanisms: Theory and Applications”, American Economic Review
Tadashi Hashimoto, Daisuke Hirata, Onur Kesten, Morimitsu Kurino, and M. Utku Unver, Two Axiomatic Approaches to the Probabilistic Serial Mechanism. Theoretical Economics
Mohammad Akbarpour and Afshin Nikzad, Approximate Random Allocation Mechanisms, mimeo
Class 5: Resource allocation with multi-unit demands
*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 6: Mechanism design with interdependent values
*Two-Sided Matching with Interdependent Values Archishman Chakraborty, Alessandro Citanna and Michael Ostrovsky, Journal of Economic Theory.
*P Jehiel, B Moldovanu Efficient design with interdependent valuations Econometrica
*Efficient Auctions*jstor.org [PDF]
Find it@Stanford P Dasgupta, E Maskin - Quarterly Journal of Economics, 2000 - MIT Press
"An Efficient Multi-Unit Ascending Auction." Motty Perry and Philip J. Reny; The Review of Economic Studies, 2005, 72(2), pp. 567.
http://dx.doi.org/10.1111/j.1467-937X.2005.00343.x
*Jehiel, P., M. Meyer-ter-Vehn, B. Moldovanu and W. R. Zame, (2006): “The Limits of ex post Implementation,” Econometrica, 74(3), 585-610.
Generic Impossibility of Partial Ex Post Implementation with General Utility Functions Tadashi Hashimoto
*Yeon-Koo Che, Jinwoo Kim, and Fuhito Kojima, "Efficient Assignment under Interdependent Values", forthcoming, Journal of Economic Theory.
Classes 7-: Student Presentations
Students can present one of the papers in the above reading list, 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 (if you are presenting papers not on this list, please email me so that we can make sure that the paper is related enough to the class topics and/or interesting enough to the audience).
Atila Abdulkadiroglu, Josh Angrist, and Parag Pathak, The Elite Illusion: Achievement Effects at Boston and New York Exam Schools | Supplementary Material, Econometrica
Nikhil Agarwal, An Empirical Model of the Medical Match | Online Appendix American Economic Review, forthcoming
Onur Kesten and Utku M. Unver, A Theory of School-Choice Lotteries , TE
Mehmet Ekmekci and Bumin Yenmez, Integrating Schools for Centralized Admissions, mimeo
Yeon-Koo Che and Youngwoo Koh, Decentralized College Admissions, mimeo (R&R JPE)
Eric Budish and Judd Kessler, Changing the Course Allocation Mechanism at Wharton, mimeo
Eric Budish, Peter Cramton, and John Shim, The High-Frequency Trading Arms Race: Frequent Batch Auctions as a Market Design Response
Paul Milgrom and Ilya Segal, Deferred Acceptance Auctions and Radio Spectrum Reallocation
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
Mohammad Akbarpour and Afshin Nikzad, Approximate Random Allocation Mechanisms, 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
Haluk Ergin, Tayfun Sonmez, and Utku M. Unver, “Lung Exchange,” [ PDF ], mimeo
Umut Dur and Utku M. Unver, Tuition Exchange, mimeo (R&R JPE)
SangMok Lee and Leeat Yariv, On the Efficiency of Stable Matchings in Large Markets [PDF]
Federico Echenique and Bumin Yenmez, How to control controlled school choice, American Economic Review, forthcoming. [PDF] [appendix] [slides]
Federico Echenique and Juan Sebastian Pereyra, Strategic Complementarities and Unraveling in Matching Markets, TE
Chris Chambers and Bumin Yenmez, Choice and Matching, mimeo
Marek Pycia and Bumin Yenmez, Matching with Externalities, mimeo
Bumin Yenmez, College Admissions, mimeo
Mohammad Akbarpour and Afshin Nikzad, Approximate Random Allocation Mechanisms, mimeo
Goto, Hashimoto, Iwasaki, Kawasaki, Ueda, Yasuda, and Yokoo, Strategy-Proof Matching with Regional Minimum Quotas, AAMAS-2014
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
Aytek Erdil, Strategy-proof Stochastic Assignment, JET
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
Konrad Menzel, Large Matching Markets as Two-Sided Demand Systems, mimeo (R&R Econometrica)
Nikhil Agarwal and Paulo Somaini, Demand Analysis using Strategic Reports: An application to a school choice mechanism | Appendix, mimeo