Class Time: Fridays, 1:00pm-2:45pm
Location: zoom live
Office Hours: by appointment
Instructor: Fuhito Kojima
fuhitokojima1979 “at” gmail.com
http://sites.google.com/site/fuhitokojimaeconomics/
(This syllabus is evolving: Please check the latest version frequently. Last updated: September 6th, 2020)
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 to one another, and (3) organ transplantation, 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, Boston and other U.S. cities 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, and the John Bates Clark medal (a.k.a. "baby Nobel") awarded to Parag Pathak in 2018.
This is a topics course. We discuss mechanism/market design, with the main (though not necessarily exclusive) focus on theory and application of matching theory. This class builds on basic knowledge in matching theory, but I will try to give quick review in the first few lectures. If you have never learned matching theory before, I recommend that you take a look at lecture slides in https://sites.google.com/site/fuhitokojimaeconomics/econ-182-spring-2019. If you read Japanese, here is a book manuscript in Japanese at https://www.dropbox.com/s/nv6damxtb53u850/matching-theory-texbook-manuscript.pdf?dl=0 that you might find useful.
The main part of this course is composed of student presentations. Depending on availability of time slots and interest, I may also invite a few guest lecturers.
Grading
Tentative plan: Class presentation(s), class participation, and a term paper, but subject to change depending on enrollment.
Prerequisite
I assume basic knowledge about matching theory, although I will give a few lectures to review basic material. If you are unfamiliar with the topic but would like to take the course, you are very welcome to do so, but please make sure to familiarize yourself with basic material I mentioned.
Textbooks
There is no textbook.
For reviewing basic material in matching theory, take a look at lecture slides at
https://sites.google.com/site/fuhitokojimaeconomics/econ-182-spring-2019.
Additional information can be obtained from Haeringer, G. (2018) Market Design: Auctions and Matching, MIT Press
or
A book manuscript (in Japanese) at https://www.dropbox.com/s/nv6damxtb53u850/matching-theory-texbook-manuscript.pdf?dl=0
Other materials are to be announced.
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, forthcoming, Journal of Political Economy
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 (R&R Econometrica)
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), forthcoming, Theoretical Economics
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
Classes 5-: Student Presentations
I have assigned papers to each date of class after the first few lectures by me. There are TBA slots. Each student should sign up for TBA dates (subject to change depending on enrollment). I will send a google docs link to class by the end of the firsts week so that everyone enrolled can sign up for slots.
Below are reading lists from previous years. In the past I taught from subsets from these topics. I keep them here iin case you are interested, although I will not cover them this year.
Resource allocation with multi-unit demands
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.
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.
Tadashi Hashimoto, Generic Impossibility of Partial Ex Post Implementation with General Utility Functions
*Yeon-Koo Che, Jinwoo Kim, and Fuhito Kojima, "Efficient Assignment under Interdependent Values", forthcoming, Journal of Economic Theory.
School Choice and Efficient Priority-Based Allocations
Abdulkadiroğlu, Atila, and Tayfun Sönmez (2003), "School Choice: A Mechanism Design Approach," American Economic Review, 93: 729-747.
*Haluk Ergin (2002) “Efficient Resource Allocation on the Basis of Priorities,” Econometrica, 70, 2489–2498.
*Guillaume Haeringer and Flip Klijn Constrained school choice, Journal of Economic Theory, 144, 1921-1947 (2009)
*Fuhito Kojima "Robust Stability in Matching Markets" forthcoming, Theoretical Economics.
Kesten, Onur, On Two Kinds of Manipulation for School Choice Problems, forthcoming, Economic Theory
Fuhito Kojima, Efficient Resource Allocation under Multi-unit Demand (2011), mimeo
*Kesten, Onur, “On Two Competing Mechanisms for Priority Based Allocation Problems,” Journal of Economic Theory 127, 2006; 155-171.
Lars Ehlers and Aytek Erdil, Efficient Assignment Respecting Priorities, forthcoming, Journal of Economic Theory.
Characterizations of Assignment Mechanisms
L. Ehlers and B. Klaus (2009): "Allocation via Deferred Acceptance," mimeo
*Fuhito Kojima and Mihai Manea: "Axioms for Deferred Acceptance," forthcoming, Econometrica.
*Papai, Szilvia, “Strategy-proof Assignments by Hierarchical Exchange,” Econometrica 68, 1403-1433
Fuhito Kojima and Utku Unver, "The Boston School Choice Mechanism," mimeo.
Lars-Gunnar Svensson (1999) “Strategyproof Allocation of Indivisible Goods,” Social Choice and Welfare 16, 557-567.
Utku Unver and Marek Pycia, A Theory of House Allocation and Exchange Mechanisms , mimeo
Monotone Methods and Matching
Donald Topkis, Supermodularity and complementarity, Princeton University Press
P Milgrom, J Roberts, Rationalizability, learning, and equilibrium in games with strategic complementarities - Econometrica
P Milgrom, C Shannon, Monotone comparative statics - Econometrica, 1994
*Adachi, Hiroyuki, “On a characterization of stable matchings,” Economics Letters, 2000, 68, 43–49.
Echenique, Federico "A Characterization of Strategic Complementarities"
Games and Economic Behavior. Volume 46, Issue 2, Pages 325-347 (February 2004). [PDF]
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 Paul R.Milgrom, “Matching with Contracts,” American Economic Review, 2005, 95, 913–935.
*Ostrovsky, Michael, “Stability in Supply Chain Networks,” American Economic Review, 2007, forthcoming.
Michihiro Kandori, Fuhito Kojima, and Yosuke Yasuda, Understanding Stable Matchings: A Noncooperative Approach, mimeo.