Matching Theory (2024 1st)
Matching Theory | Microeconomic Analysis 2
マッチング理論 | ミクロ経済分析2
1st semester, Mondays 2nd (10:30-12:00), Room 演6(文法経講義棟)
Office Hours: Mondays 12:40-13:20 or by appointment.
E-mail: yosuke.yasuda <at> gmail.com
Website: https://sites.google.com/site/yosukeyasuda2/home/lectures/osaka2024_matching
Last Update: May 1, 2024
Announcement | お知らせ
[May 1, 2024] --- The Slides for lectures 1 and 2 have been updated, and the slides for lectures 3 and 4 were just uploaded.
[Apr 23, 2024] --- The audio file of the second lecture given on Monday, April 22, has been uploaded to CLE.
[Apr 16, 2024] --- The audio file of the first lecture given on Monday, April 15, has been uploaded to CLE.
[April 14, 2024] --- The slide for the first lecture was just uploaded here. Audio will also be recorded and uploaded to CLE. International students who are unable to enter Japan due to visa issues are encouraged to use these materials to catch up with the class.
[March 2, 2024] --- The first lecture will be on April 15 (Mon). Lectures will be in English, but your questions and presentations can be in Japanese.
Course Objective and Content | 講義概要・目的
We study the theory of two-sided matching.
First, lectures based on the textbook are given.
Then, we read recent academic papers on this subject.
Learning Goals | 学習目標
To acquire analytical skills on the economics of matching from theoretical perspectives.
To understand how theoretical ideas on matching are applied to real-life issues on market design such as medical match, school choice, and college admission.
Requirement / Prerequisite | 履修条件・受講条件
Game theory at the advanced undergraduate level.
Grading Policy | 成績評価
Based on your presentation and final report.
Auditing students SHOULD also make presentations but need NOT submit the final report.
You can give a talk in either English or Japanese, but you should prepare SLIDES typed in ENGLISH. (so that everyone can understand the contents)
Your presentation should be about 20 to 30 minutes long. After each talk, we will invite questions and comments from other participants.
You can write the final report in either Japanese or English. The suggested length is 2 - 5 pages. Your report should be either
1) an original research paper/idea on matching theory,
2) a referee report on a paper (which is not directly covered in class), or
3) a survey on a specific issue of matching theory.
Textbooks | 講義テキスト
The main textbook for this course is here.
Main Textbook
Roth and Sotomayor [RS], Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis, 1990. Amazon (Kindle)
This is the “bible” of the matching theory; it covers most of the important theoretical research on matching up to the 1980s.
The relevant parts will be posted in CLE, so you need NOT purchase this book.
Related Books
Haeringer [MD], Market Design: Auctions and Matching, 2017. Amazon
Vulkan, Roth, and Neeman ed. [HB], Handbook of Market Design, 2013. Amazon TOC
This handbook includes many interesting real-life applications.
Roth, Who Gets What -- And Why: The New Economics of Matchmaking and Market Design, 2015. Amazon
This is a great introductory book that guides you to matching market design.
Course Schedule | 講義日程
The instructor will give lectures 1 through 7. All the rest consist of students' presentations.
Lecture 1. One-to-One Matching Model April 15
Slide for Lec 1.
[RS] Ch1: Introduction; Ch2: Stable Matchings
[MD] Ch9: The Basic Matching Model (slides)
References
**Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15.
*Blair, C. (1984). Every finite distributive lattice is a set of stable matchings. Journal of Combinatorial Theory, Series A, 37(3), 353-356.
Alkan, A. (1988). Nonexistence of stable threesome matchings. Mathematical Social Sciences, 16(2), 207-209.
Gärdenfors, P. (1975). Match making: assignments based on bilateral preferences. Behavioral Science, 20(3), 166-173.
Sotomayor, M. (1996). A non-constructive elementary proof of the existence of stable marriages. Games and Economic Behavior, 13(1), 135-137.
<Survey>
**Roth, A. (2002), The Economist as Engineer: Game Theory, Experimentation, and Computation as Tools for Design Economics, Econometrica, 70: 1341-1378.
**Roth, A. E., & Wilson, R. B. (2019). How market design emerged from game theory: A mutual interview. Journal of Economic Perspectives, 33(3), 118-43.
*Economic Sciences Prize Committee of the Royal Swedish Academy of Sciences (2012), Stable Allocations and The Practice of Market Design, Scientific Background on the Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel 2012. Link
*Roth, A. E. (2008). What have we learned from market design? The Economic Journal, 118(527), 285-310.
Niederle, M., Roth, A. and Sonmez, T. (2008), Matching, in The New Palgrave Dictionary of Economics, edited by Steven N. Durlauf and Lawrence E. Blume.
Roth, A. E. (2007). Repugnance as a Constraint on Markets. Journal of Economic Perspectives, 21(3), 37-58.
Roth, A. (2008), Deferred acceptance algorithms: history, theory, practice, and open questions, International Journal of Game Theory, 36: 537-569.
Roth, A. E. (2018). Marketplaces, markets, and market design. American Economic Review, 108(7), 1609-58.
Keywords
two-sided matching, cooperative game theory, non-cooperative game theory, stable matching, Gale-Shapley's deferred acceptance (DA) algorithm, M-optimal stable matching.
Lecture 2. Incentive Issues April 22
Slide for Lec 2.
[RS] Ch3: The Structure of the Set of Stable Matchings, Ch4: Strategic Questions
[MD] Ch9: The Basic Matching Model
References
**Dubins, L. and Freedman, D. (1981), Machiavelli and the Gale-Shapley algorithm, American Mathematics Monthly, 88: 485–494.
**Roth, A. E. (1982). The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4), 617-628.
*Demange, G., Gale, D. and Sotomayor, M. (1987), A further note on the stable matching problem, Discrete Applied Mathematics, 16: 217–222.
*Roth, A. and Rothblum, U. (1999), Truncation Strategies in Matching Markets - in Search of Advice for Participants, Econometrica, 67: 21-43.
Demange, G., & Gale, D. (1985). The strategy structure of two-sided matching markets. Econometrica, 873-888.
Sotomayor, M. (2007), Connecting the cooperative and competitive structures of the multiple-partners assignment game, Journal of Economic Theory, 134: 155–174.
Keywords
manipulation, dominant strategy, strategy-proofness, blocking lemma, impossibility theorem, strategic equilibrium.
Lecture 3. Structure of Stable Matchings No Lecture (or On-Demand)
Slide for Lec 3.
[RS] Ch3: The Structure of the Set of Stable Matchings, Ch4: Strategic Questions
[MD] Ch9: The Basic Matching Model
References
*Gale, D and Sotomayor, M. (1985), Ms Machiavelli and the stable matching problem, American Mathematical Monthly, 92: 261-8.
*Roth, A. E. and Vate, J. H. V. (1990). Random paths to stability in two-sided matching. Econometrica, 1475-1480.
Demange, G., Gale, D. and Sotomayor, M. (1987), A further note on the stable matching problem, Discrete Applied Mathematics, 16: 217–222.
Eeckhout, J. (2000). On the uniqueness of stable marriage matchings. Economics Letters, 69(1), 1-8.
Blum, Y., Roth, A. E., and Rothblum, U. G. (1997). Vacancy chains and equilibration in senior-level labor markets. Journal of Economic Theory, 76(2), 362-411.
Roth, A. E., Rothblum, U. G., and Vande Vate, J. H. (1993). Stable matchings, optimal assignments, and linear programming. Mathematics of Operations Research, 18(4), 803-828.
Rothblum, U. G. (1992). Characterization of stable matchings as extreme points of a polytope. Mathematical Programming, 54, 57-67.
Keywords
lattice, decomposition lemma, comparative statics, extending (preferences), adding (agents), path of blocking pairs.
Lecture 4. One-to-Many Matching Model May 13
Slide for Lec 4.
[RS] Ch5: The College Admissions Model and the Labor Market for Medical Interns
[MD]: Ch10: The Medical Match (slides)
References
**Roth, A. E. (1984). The evolution of the labor market for medical interns and residents: a case study in game theory. Journal of Political Economy, 92(6), 991-1016.
*Roth, A. E., & Peranson, E. (1999). The redesign of the matching market for American physicians: Some engineering aspects of economic design. American economic review, 89(4), 748-780.
Kojima, F., Pathak, P. A., & Roth, A. E. (2013). Matching with couples: Stability and incentives in large markets. Quarterly Journal of Economics, 128(4), 1585-1632.
Mongell, S., & Roth, A. E. (1991). Sorority rush as a two-sided matching mechanism. American Economic Review, 441-464.
Niederle, M., & Roth, A. E. (2003). Unraveling reduces mobility in a labor market: Gastroenterology with and without a centralized match. Journal of Political Economy, 111(6), 1342-1352.
Roth, A. (1985), The college admissions problem is not equivalent to the marriage problem, Journal of Economic Theory, 36: 277-288.
<Survey>
Roth, A. (2003), The Origins, History, and Design of the Resident Match, Journal of the American Medical Association, 289 :909-912.
Keywords
responsive preferences, pairwise stable matching, group stable matching, related marriage market, weak Pareto optimality, rural hospital theorem.
Lecture 5. Matching with Money May 20
Slide for Lec 5.
[RS] Ch6: Discrete models with money, and more complex preferences
References
**Kelso Jr, A. S., & Crawford, V. P. (1982). Job matching, coalition formation, and gross substitutes. Econometrica, 1483-1504.
*Crawford, V. P., & Knoer, E. M. (1981). Job matching with heterogeneous firms and workers. Econometrica, 437-450.
Blair, C. (1988), The Lattice Structure of the Set of Stable Matchings with Multiple Partners, Mathematics of Operations Research, 13: 619-628.
Bulow, J., & Levin, J. (2006). Matching and price competition. American Economic Review, 96(3), 652-668.
Kojima, F. (2007). Matching and price competition: comment. American Economic Review, 97(3), 1027-1031.
Mongell, S. J., & Roth, A. E. (1986). A note on job matching with budget constraints. Economics Letters, 21(2), 135-138.
Sasaki, H., & Toda, M. (1996). Two-sided matching problems with externalities. Journal of Economic Theory, 70(1), 93-108.
Sotomayor, M. (2004), Implementation in the many-to-many matching market, Games and Economic Behavior, 46: Pages 199–212.
Keywords
substitutability, gross substitutes, salary-adjustment process, continuous market, budget constraints.
Lecture 6. Monotone Method May 27
References
**Adachi, H. (2000). On a characterization of stable matchings. Economics Letters, 68(1), 43-49.
*Chapter 2 of Vives, X. (1999), Oligopoly Pricing: Old Ideas and New Tools. Amazon
Chapter 7 of Vohra, R. (2004), Advanced Mathematical Economics. Amazon (Kindle)
Echenique, F. (2005), A Short And Constructive Proof of Tarski's Fixed-Point Theorem, International Journal of Game Theory, 33: 215-218.
Echenique, F. and Oviedo, J. (2004), Core many-to-one matchings by fixed point methods, Journal of Economic Theory, 115: 358–376.
Fleiner, T (2003), A fixed-point approach to stable matchings and some applications, Mathematics of Operations Research, 28: 103–126.
Kandori, M., Kojima, F., and Yasuda, Y. (2008), Understanding Stable Matchings: A Non-Cooperative Approach, mimeo.
Roth, A. E., & Sotomayor, M. (1988). Interior points in the core of two-sided matching markets. Journal of Economic Theory, 45(1), 85-101.
Tarski, A. (1955), A lattice theoretical fixpoint theorem and its applications, Pacific Journal of Mathematics, 5: 285-309.
Topkis, D. (1998), Supermodularity and Complementarity. Amazon (Kindle)
安田洋祐, マッチングの数理, 数学セミナー, 4月号, 2013. 草稿
Keywords
partial orde, supremum and infimum, complete lattice, fixed point, Tarski's fixed point theorem, pre-matching.
Lecture 7. Matching with Contracts June 3
Presentation
References
**Hatfield, J. and Milgrom, P. (2005), Matching with Contracts, American Economic Review, 95: 913-935.
*Aygun, O. and Sonmez, T. (2013), Matching with Contracts: Comment, American Economic Review, 103: 2050-2051.
*Ostrovsky, M. (2007), Stability in Supply-Chain Networks, American Economic Review, 98: 897-923.
*Sonmez, T. and Switzer, T. (2014), Matching with (Branch-of-Choice) Contracts at the United States Military Academy, Econometrica, 81: 451-488.
Echenique, F. (2012), Contracts vs. Salaries in Matching, American Economic Review, 102: 594-601.
Hatfield, J. W., and Kojima, F. (2008). Matching with contracts: Comment. The American Economic Review, 98(3), 1189-1194.
Hatfield, J. W., and Kojima, F. (2009). Group incentive compatibility for matching with contracts. Games and Economic Behavior, 67(2), 745-749.
Hatfield, J. W., and Kojima, F. (2010). Substitutes and stability for matching with contracts. Journal of Economic Theory, 145(5), 1704-1723.
Kominers, S. D. (2012). On the correspondence of contracts to salaries in (many-to-many) matching. Games and Economic Behavior, 75(2), 984-989.
Westkamp, A. (2010), Market structure and matching with contracts, Journal of Economic Theory Volume, 145: 1724–1738.
=== Below Lectures will be based on the Students' Presentations ====
Lecture 8. Assignment Problem
Lecture 9. Probabilistic Assignments
[MD] Ch11: The Assignment Problems (slides)
[MD] Ch12: Probabilistic Assignments (slides)
Sönmez, T. and Unver, U. (2011), Matching, Allocation, and Exchange of Discrete Resources, in Handbook of Social Economics, Vol. 1A, edited by J. Benhabib, A. Bisin, and M. Jackson.
References
**Shapley, L., & Scarf, H. (1974). On cores and indivisibility. Journal of mathematical economics, 1(1), 23-37.
*Abdulkadiroğlu, A., & Sönmez, T. (1999). House allocation with existing tenants. Journal of Economic Theory, 88(2), 233-260.
*Roth, A. E., Sönmez, T., & Ünver, M. U. (2004). Kidney exchange. The Quarterly Journal of Economics, 119(2), 457-488.
Combe, J., Tercieux, O., & Terrier, C. (2022). The design of teacher assignment: Theory and evidence. The Review of Economic Studies, 89(6), 3154-3222.
Ergin, H. I. (2002). Efficient resource allocation on the basis of priorities. Econometrica, 70(6), 2489-2497.
Ma, J. (1994), Strategy-Proofness and the Strict Core in a Market with Indivisibilities, International Journal of Game Theory, 23: 75-83.
Roth, A. and Postlewaite, A. (1977), Weak Versus Strong Domination in a Market with Indivisible Goods, Journal of Mathematical Economics, 4: 131-137.
Roth, A. E., Sönmez, T., & Ünver, M. U. (2005). Pairwise kidney exchange. Journal of Economic Theory, 125(2), 151-188.
Roth, A. E., Sönmez, T., & Ünver, M. U. (2007). Efficient kidney exchange: Coincidence of wants in markets with compatibility-based preferences. American Economic Review, 97(3), 828-851.
小島武仁・安田洋祐, マッチング・マーケットデザイン, 経済セミナー, (647), 135-145, 2009. 増補改訂版
坂井豊貴, マーケットデザイン: 最先端の実用的な経済学, ちくま新書, 2013. Amazon
Lecture 10. Kidney Exchange
Lecture 11. School Choice: Basic Model
Lecture 12. School Choice: Extensions
[MD] Ch13: School Choice (slides)
[MD] Ch14: School Choice: Further Developments (slides)
Presentation
Paper 1: Abdulkadiroğlu and Sönmez (2003) --- QIU Jiaying
Paper 2: Chen and Kesten (2017) --- SUN Weiting
References
**Abdulkadiroğlu, A., & Sönmez, T. (2003). School choice: A mechanism design approach. American economic review, 93(3), 729-747.
*Abdulkadiroğlu, A., Che, Y.-K. and Yasuda, Y. (2011), Resolving Conflicting Preferences in School Choice: the "Boston Mechanism" Reconsidered, American Economic Review, 101: 399-410.
*Abdulkadiroğlu, A., Pathak, P. A., & Roth, A. E. (2009). Strategy-proofness versus efficiency in matching with indifferences: Redesigning the NYC high school match. American Economic Review, 99(5), 1954-78.
*Chen, Y., & Kesten, O. (2017). Chinese college admissions and school choice reforms: A theoretical analysis. Journal of Political Economy, 125(1), 99-139.
Balinski, M., & Sönmez, T. (1999). A tale of two mechanisms: student placement. Journal of Economic Theory, 84(1), 73-94.
Abdulkadiroğlu, A., Pathak, P. A., & Roth, A. E. (2005). The new york city high school match. American Economic Review, 95(2), 364-367.
Abdulkadiroğlu, A., Pathak, P. A., Roth, A. E., & Sönmez, T. (2005). The Boston public school match. American Economic Review, 95(2), 368-371.
Abdulkadiroglu, A., Che, Y.-K. and Yasuda, Y. (2015), Expanding "Choice" in School Choice, American Economic Journal: Microeconomics, 7: 1-42.
Ergin, H., & Sönmez, T. (2006). Games of school choice under the Boston mechanism. Journal of Public Economics, 90(1-2), 215-237.
Kesten, O. (2010). School choice with consent. The Quarterly Journal of Economics, 125(3), 1297-1348.
Calsamiglia, C., Haeringer, G., and Klijn, F. (2010). Constrained school choice: An experimental study. The American Economic Review, 1860-1874.
Erdil, A. and Ergin, H. (2008), What's the Matter with Tie-Breaking? Improving Efficiency in School Choice, American Economic Review, 98: 669-689.
Haeringer, G., and Klijn, F. (2009). Constrained school choice. Journal of Economic Theory, 144(5), 1921-1947.
Pathak, P. and Sönmez, T. (2008), Leveling the Playing Field: Sincere and Sophisticated Players in the Boston Mechanism, American Economic Review, 98: 1636-1652.
Pathak, P. and Sönmez, T. (2013), School Admissions Reform in Chicago and England: Comparing Mechanisms by their Vulnerability to Manipulation, American Economic Review, 103: 80-106.
安田洋祐, 学校選択問題のマッチング理論分析, 現代経済学の潮流2014(第4章, pp.95-122), 東洋経済新報社, 2014.
安田洋祐(編著), 学校選択制のデザイン:ゲーム理論アプローチ(編著), NTT出版, 2010. Amazon
<Survey>
Pathak, P. A. (2011). The mechanism design approach to student assignment. Annu. Rev. Econ., 3(1), 513-536.
Lecture 13. Course Bidding
Lecture 14. Recent Developments
References
Abdulkadiroğlu, A. (2005). College admissions with affirmative action. International Journal of Game Theory, 33(4), 535-549.
<Survey>
Kojima, F. (2015), Recent Developments in Matching Theory and its Practical Applications, working paper (prepared for Advances in Economics and Econometrics; 11th world congress of Econometric Society)
Kojima, F. and Troyan, P. (2011), Matching and Market Design: An Introduction to Selected Topics, Japanese Economic Review, 62: 82–98.
Lecture 15. Review
Back to the top.
Lecture. Introduction
[RS] Ch1: Introduction
[MD] Ch9: The Basic Matching Model (slides)
References
*Roth, A. E., & Sotomayor, M. (1992). Two-sided matching. Handbook of Game Theory with Economic Applications, Vol.1, 485-541.
Roth (2015), Who Gets What -- And Why: The New Economics of Matchmaking and Market Design.
<Survey>
**Roth, A. (2002), The Economist as Engineer: Game Theory, Experimentation, and Computation as Tools for Design Economics, Econometrica, 70: 1341-1378.
*Economic Sciences Prize Committee of the Royal Swedish Academy of Sciences (2012), Stable Allocations and The Practice of Market Design, Scientific Background on the Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel 2012. Link
Roth, A. E. (2007). Repugnance as a Constraint on Markets. Journal of Economic Perspectives, 21(3), 37-58.
Roth, A. E. (2008). What have we learned from market design?. The Economic Journal, 118(527), 285-310.
Roth, A. E. (2018). Marketplaces, markets, and market design. American Economic Review, 108(7), 1609-58.
Roth, A. E., & Wilson, R. B. (2019). How market design emerged from game theory: A mutual interview. Journal of Economic Perspectives, 33(3), 118-43.
Keywords
matching, market design, Nobel prize, auctions, game theory, Pareto efficiency, blocking pair, stable matching, Gale-Shapley mechanism, chat-gpt.
Lecture. Mathematical Structure of Stable Matchings
[RS] Ch3: The structure of the set of stable matching
References
*Blair, C. (1984). Every finite distributive lattice is a set of stable matchings. Journal of Combinatorial Theory, Series A, 37(3), 353-356.
*Demange, G., Gale, D. and Sotomayor, M. (1987), A further note on the stable matching problem, Discrete Applied Mathematics, 16: 217–222.
Eeckhout, J. (2000). On the uniqueness of stable marriage matchings. Economics Letters, 69(1), 1-8.
Gale, D and Sotomayor, M. (1985), Some remarks on the stable matching problem, Discrete Applied Mathematics, 11: 223-32.
Knuth, D. (1976), Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms, English Reprint (1996). Amazon
Keywords
deferred acceptance algorithm, propose, engage, reject, men/women optimal stable matching, lattice, decomposition lemma.
Lecture. Assignment Game
[RS] Ch8: The assignment game
References
**Shapley, L. and Shubik, M. (1971), The assignment game I: the core, International Journal of Game Theory, 1:111–130.
*Demange, G., Gale, D., & Sotomayor, M. (1986). Multi-item auctions. Journal of Political Economy, 94(4), 863-872.
Becker, G. S. (1991). A treatise on the family: Enlarged edition. Harvard University Press.
[RS] Ch9: A generalization of the assignment model
Hylland, A. and Zeckhauser, R. (1977), The efficient allocation of individuals to positions, Journal of Political Economy, 87: 293-314.
Sotomayor, M. (1992). The multiple partners game. Equilibrium and Dynamics: Essays in Honour of David Gale, 322-354.
<Survey>
Sattinger, M. (1993). Assignment models of the distribution of earnings. Journal of Economic Literature, 31(2), 831-880.
Keywords
...
Lecture. Ad Auctions
[MD] Ch5: Keyword Auctions (slides)
Presentation
References
*Edelman, B., Ostrovsky, M., & Schwarz, M. (2007). Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords. American Economic Review, 97(1), 242-259.
*Varian, H. R. (2007). Position auctions. international Journal of industrial Organization, 25(6), 1163-1178.
[RS] Ch7: A simple model of one seller and many buyers
[MD] Ch2: Simple Auctions (slides)
Athey, S., & Ellison, G. (2011). Position auctions with consumer search. The Quarterly Journal of Economics, 126(3), 1213-1270.
Chen, Y., & He, C. (2011). Paid placement: Advertising and search on the internet. The Economic Journal, 121(556), F309-F328.
Varian, H. R., & Harris, C. (2014). The VCG auction in theory and practice. American Economic Review, 104(5), 442-45.
<Survey>
Goldfarb, A., & Tucker, C. (2019). Digital economics. Journal of Economic Literature, 57(1), 3-43.