Econ 182 (Spring 2013)
ECON 182: Honors Market Design
Location: Econ 218
Office Hours: Wednesday 10-12
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
Grading criterion is subject to change, depending on the enrollment and student interest. My tentative plan is to assign a few problem sets (30 percent), one midterm assignment (20 percent), one class presentation (20 percent) and one final paper (30 percent).
(1) The problem sets are assigned 3 times throughout the course (tentative plan: April 4th, 18th, and May 16th) 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 midterm assignment is a short paper (tentative plan: due May 9th in class; suggested length: 4-6 pages). It can be a rough idea for the final paper, or a review of one or more paper(s) by other researcher(s).
(3) Class presentation is either a student’s own research or discussion of a research paper of someone else.
(4) Suggested length of the final paper is between 10 to 15 pages but it can vary within a reasonable limit (tentative plan: due on June 6th Thursday). You can write an original research paper or a critical literature review.
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.
Class Slides
Class 1 (Tue 04/02) + Class 2 (Thu 04/04)
Class 3 (Tue 04/09)
Class 4 (Thu 04/11) + Class 5 (Tue 4/16)
Class 6 (Thu 04/18)
Class 7 (Tue 4/23) + Class 8 (Thu 4/25)
Class 9 (Tue 4/30) + Class 10 (Thu 5/02), supplementary material
Class 11 (Tue 05/07)
Class 12 (Thu 05/09)
Class 13 (Tue 05/14)
Class 19 (Tue 06/04)
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 will have 2 or 3 guest speakers. 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-18: 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.
Atila Abdulkadiroğlu, Parag Pathak, Alvin Roth and Tayfun Sonmez, “Changing the Boston School Choice Mechanism,” mimeo
Archishman Chakraborty, Alessandro Citanna and Michael Ostrovsky, “Two-Sided Matching with Interdependent Values,” mimeo.
Niederle, Muriel, and Alvin E. Roth, “Making Markets Thick: Designing Rules for Offers and Acceptances”, 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
Utku Unver, “Dynamic Kidney Exchange,” mimeo
Bumin Yenmez and Michael Schwarz, “Median Stable Matching,” mimeo
Tayfun Sonmez and Tobias Switzer, Matching with (Branch-of-Choice) Contracts at the United States Military Academy, Econometrica
Parag Pathak and Tayfun Sonmez, School Admissions Reform in Chicago and England: Comparing Mechanisms by Their Vulnerability to Manipulability, AER
Tayfun Sonmez, Bidding for Army Career Specialties: Improving the ROTC Branching Mechanism, mimeo
Scott Kominers and Tayfun Sonmez, Designing for Diversity in Matching
Aygun and Sonmez x 2
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
A Theory of School-Choice Lotteries (with Onur Kesten) Boston College Working Papers in Economics, No: 737
Unraveling Results from Comparable Demand and Supply: An Experimental Investigation (with Alvin E. Roth and Muriel Niederle)
Strategy-proof Stochastic Assignment
The Revealed Preference Theory of Stable and Extremal Stable Matchings [PDF], joint with Federico Echenique, Matthew Shum, and M. Bumin Yenmez, Econometrica, forthcoming.
Incentive Compatibility of Large Centralized Matching Markets [PDF] (Supplemental Materials)
“The difference indifference makes in strategy-proof allocation of objects,” forthcoming, Journal of Economic Theory. (With Paula Jaramillo)
“A market approach to fractional matching,” 2011.
Dur and Unver, Tuition Exchange
Cho (Rochester)
Hashimoto, Tadashi.
When are Local Incentive Constraints Sufficient? / Online appendix (Econometrica, forthcoming)
On Mechanisms Eliciting Ordinal Preferencese
A General Equivalence Theorem for Allocation of Indivisible Objects