Matching Theory (2023 1st)

Matching Theory | Microeconomic Analysis 2 

マッチング理論 | ミクロ経済分析2

• 1st semester, Wednesdays 2nd (10:30-12:00) → 1st (8:50-10:20), Seminar Room 6 (文法経講義棟3階 演習室6)  

• Office Hours: Mondays 12:45-13:30 or by appointment. 

• E-mail: yosuke.yasuda <at> gmail.com 

• Website: https://sites.google.com/site/yosukeyasuda2/home/lectures/osaka2023_matching 

Last Update: July 19, 2023 

Announcement | お知らせ  

• [July 19, 2003] --- We will have a final lecture on July 24. There will be not lecture on July 31. 

• [May 20, 2003] --- There will be NO lecture on May 31.

• [April 20, 2003] --- The time slot for this course will move from the 2nd to the 1st (8:50-10:20) on Wednesdays, starting from April 25. The lecture room remains the same, i.e., seminar room 6.

• [April 18, 2003] --- Lecture slides (for Lec 2-6) were slightly updated. The new file is available here. 

• [April 7, 2023] --- The first lecture will be on April 12 (Wed). 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. 

  1. First, lectures based on the textbook are given.

  2. 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 | 講義テキスト

• There is the main textbook for this course. 

• 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  

    • The author's website on the market design lecture based on the textbook is here. 

      • Note: Slide materials on each chapter can also be downloaded from the above link :) 

    • The relevant parts will be posted in CLE, so you need NOT purchase this book.

  • 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 4 (and 13?). All the rest consists of students' presentations. 

• Lecture slides for Lec1

• Lecture slides for Lec 2-6 (and more) 

• Slides for Haeringer (2017) [MD]: Ch2, Ch5, Ch9, Ch10, Ch11, Ch12, Ch13, Ch14. 

Lecture 1. Introduction  April 12 

• [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 2. One-to-One Matching Model  April 19

• [RS] 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.

  • *Roth, A. E., & Vate, J. H. V. (1990). Random paths to stability in two-sided matching. Econometrica, 1475-1480.

  • Alkan, A. (1988). Nonexistence of stable threesome matchings. Mathematical Social Sciences, 16(2), 207-209.

  • Sotomayor, M. (1996). A non-constructive elementary proof of the existence of stable marriages. Games and Economic Behavior, 13(1), 135-137. 

  • <Survey>

  • 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. (2008), Deferred acceptance algorithms: history, theory, practice, and open questions, International Journal of Game Theory, 36: 537-569. 

• Keywords

  • matching problem, room-mate problem, mapping, individual rationality, block, stable matching, deferred acceptance algorithm, taxi problem, cooperative game theory. 

Lecture 3. Mathematical Structure of Stable Matchings  April 26

• [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 4. Incentive Issues  May 10, 17, 24 

• [RS] Ch4: Strategic questions 

  • Presenter 1 --- LAI Haohei 

  • Presenter 2 --- OKADA Yuichi

• References

  • **Roth, A. E. (1982). The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4), 617-628.

  • *Dubins, L. and Freedman, D. (1981), Machiavelli and the Gale-Shapley algorithm, American Mathematics Monthly, 88: 485–494. 

  • *Roth, A. and Rothblum, U. (1999), Truncation Strategies in Matching Markets - in Search of Advice for Participants, Econometrica, 67: 21-43.

  • Alcalde, J. (1996), Implementation of Stable Solutions to Marriage Problems, Journal of Economic Theory, 69: 240–254. 

  • Alcalde, J. and Barbera, S. (1994), Top dominance and the possibility of strategy-proof stable solutions to matching problems, Economic Theory, 4: 417-435.

  • Demange, G., & Gale, D. (1985). The strategy structure of two-sided matching markets. Econometrica, 873-888.

  • Gale, D and Sotomayor, M. (1985), Ms Machiavelli and the stable matching problem, American Mathematical Monthly, 92: 261-8. 

  • Sotomayor, M. (2007), Connecting the cooperative and competitive structures of the multiple-partners assignment game, Journal of Economic Theory, 134: 155–174. 

• Keywords

  •  incentive, manipulation, noncooperative game, dominant strategy, strategy-proof, group strategy-proof, blocking lemma. 

Lecture 5. One-to-Many Matching Model  June 7, 14  

• [RS] Ch5: The college admissions model and the labor market for medical interns 

  • Presenter 1 --- QIU Jiaying

  • Presenter 2 --- SUN Weiting 

• [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 stability, weak dominance, core, corresponding marriage market 

Lecture 6. Matching with Money  June 21, 28 

• [RS] Ch6: Discrete models with money, and more complex preferences 

  • Presenter 1 --- YU Junsi 

  • Presenter 2 --- FU Qifan 

• 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

  •  ... 

Lecture 7. Public School Choice  July 5, 12 

• [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  Matching with Contracts  July 12, 19  

• Presentation 

  • Paper 1: Hatfield and Milgrom (2005) ---  LAI Haohei 

  • Paper 2: Ostrovsky, M. (2007) --- OKADA Yuichi

• 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.

==========

Lecture  Assignment Model  

• [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  Application 2: House Allocation Problem  

• [MD] Ch11: The Assignment Problems (slides) 

• [MD] Ch12: Probabilistic Assignments (slides) 

• Presentation

  • Paper 1: Abdulkadiroğlu and Sönmez (1999) --- 

  • Paper 2: 

  • Paper 3: 

• 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  Application 3: Ad Auctions  

• [MD] Ch5: Keyword Auctions (slides) 

• Presentation

  • Paper 1: Varian (2007) --- 

  • Paper 2: 

• 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. 

Lecture  Monotone Method  

• 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.  草稿

Lecture  Distributional Constraints  

• 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. 

Back to the top.