Matching Market Design | Microeconomic Analysis 1
マッチング・マーケットデザイン | ミクロ経済分析1
1st semester, Wednesdays 3rd (13:30-15:10), Seminar Room No.6 (演習室6)
Office Hours: by appointment
E-mail: yosuke.yasuda <at> gmail.com
Website: https://sites.google.com/site/yosukeyasuda2/home/lectures/osaka2023_matching
Last Update: July 11, 2022
Announcement | お知らせ
[July 11, 2022] --- This lecture is over. Reports are due on July 31.
[June 20, 2022] --- The lecture on July 4 is 30 minutes longer than the usual, 16:50-18:50.
[April 6, 2022] --- There will be no class on May 2. The next one, Lecture 4, will be on May 9.
[April 6, 2022] --- The link for Zoom regular meetings is posted in CLE. If you just want to attend the class without registration (i.e., you don't need a credit), please fill out this form. <= Important!!
[Feb 6, 2022] --- The first lecture will be on April 11 (Mon). Lectures will be given in English, but your questions and presentations can be made in Japanese.
Course Objective and Content | 講義概要・目的
We study economic research on matching with a primary focus on market design.
This course is mainly based on students' presentations of seminal papers that are covered in the main textbook, Haeringer (2017). Then, we read recent academic articles.
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 intermediate 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 market design,
2) a referee report on a paper (which is not directly covered in class), or
3) a survey on a specific issue of matching market design.
Textbooks | 講義テキスト
There is the main textbook for this course.
Main Textbook
Haeringer, 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.
Related Books
Roth and Sotomayor, 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.
Vulkan, Roth, and Neeman ed., Handbook of Market Design, 2013. Amazon TOC
This handbook includes many interesting real-life applications.
Course Schedule | 講義日程
(Lectures 1, 2, and 3 will be given by the instructor. All the rest consists of students' presentations.)
Lecture 1. Introduction to Matching Market Design April 11
<Survey>
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.
Lecture 2. A New Trade-off between Efficiency and Quantity April 18
References
BASIC TOPICS
Lecture 3. The Basic Matching Model April 25
Haeringer: Chapter 9
References
Alkan, A. (1988). Nonexistence of stable threesome matchings. Mathematical social sciences, 16(2), 207-209.
Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15.
Irving, R. W. (1985). An efficient algorithm for the “stable roommates” problem. Journal of Algorithms, 6(4), 577-595.
Roth, A. E. (1982). The economics of matching: Stability and incentives. Mathematics of operations research, 7(4), 617-628.
Roth, A. E., & Vate, J. H. V. (1990). Random paths to stability in two-sided matching. Econometrica: Journal of the Econometric Society, 1475-1480.
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. (2002), The Economist as Engineer: Game Theory, Experimentation, and Computation as Tools for Design Economics, Econometrica, 70: 1341-1378.
Roth, A. (2008), Deferred acceptance algorithms: history, theory, practice, and open questions, International Journal of Game Theory, 36: 537-569.
Roth, A. E., & Sotomayor, M. (1992). Two-sided matching. Handbook of game theory with economic applications, 1, 485-541.
The following lectures are based on students' presentations.
For each "TBA" slot, you can choose a paper from the references (or you could pick some other related paper if you wish). In any case, please send me an email and let me know which paper/slot you would like to present.
Lecture 4. The Medical Match May 9
Haeringer: Chapter 10
Presentations
Roth (1984) --- Yue ZICHONG
Roth & Peranson (1999) --- Yoichi OKADA
References
Kojima, F., Pathak, P. A., & Roth, A. E. (2013). Matching with couples: Stability and incentives in large markets. The Quarterly Journal of Economics, 128(4), 1585-1632.
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. 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.
<Survey>
Roth, A. (2003), The Origins, History, and Design of the Resident Match, Journal of the American Medical Association, 289 :909-912.
Lecture 5. Assignment Markets
Haeringer: Chapter 11
Presentations
Abdulkadiroğlu & Sönmez (1999) --- Reo KURATA May 16
Roth, Sönmez, & Ünver (2004) --- He WANG May 16 and 23
References
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.
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.
Shapley, L., & Scarf, H. (1974). On cores and indivisibility. Journal of mathematical economics, 1(1), 23-37.
Lecture 6. School Choice: Part 1
Haeringer: Chapter 13
Presentations
Abdulkadiroğlu & Sönmez (2003) --- Hidetoki NAKAYAMA May 23
Abdulkadiroğlu, Pathak, & Roth (2005, 09) --- Yu JUNSI May 30
References
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. (2009). Strategy-proofness versus efficiency in matching with indifferences: Redesigning the NYC high school match. American Economic Review, 99(5), 1954-78.
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.
Abdulkadiroğlu, A., & Sönmez, T. (2003). School choice: A mechanism design approach. American economic review, 93(3), 729-747.
Balinski, M., & Sönmez, T. (1999). A tale of two mechanisms: student placement. Journal of Economic theory, 84(1), 73-94.
Ergin, H. I. (2002). Efficient resource allocation on the basis of priorities. Econometrica, 70(6), 2489-2497.
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.
<Survey>
Pathak, P. A. (2011). The mechanism design approach to student assignment. Annu. Rev. Econ., 3(1), 513-536.
Lecture 7. Experimental Studies
Presentations
Chen & Sönmez (2006) --- Yuhao FU May 30
Calsamiglia, Haeringer, & Klijn (2010) --- Yunzhi LIU June 6
References
Calsamiglia, C., Haeringer, G., & Klijn, F. (2010). Constrained school choice: An experimental study. American Economic Review, 100(4), 1860-74.
Chen, Y., & Sönmez, T. (2002). Improving efficiency of on-campus housing: An experimental study. American economic review, 92(5), 1669-1686.
Chen, Y., & Sönmez, T. (2006). School choice: an experimental study. Journal of Economic theory, 127(1), 202-231.
Haeringer, G., & Klijn, F. (2009). Constrained school choice. Journal of Economic theory, 144(5), 1921-1947.
Kagel, J. H., & Roth, A. E. (2000). The dynamics of reorganization in matching markets: A laboratory experiment motivated by a natural experiment. The Quarterly Journal of Economics, 115(1), 201-235.
Kawagoe, T., Matsubae, T., & Takizawa, H. (2018). The skipping-down strategy and stability in school choice problems with affirmative action: Theory and experiment. Games and Economic Behavior, 109, 212-239.
Pais, J., & Pintér, Á. (2008). School choice and information: An experimental study on matching mechanisms. Games and Economic Behavior, 64(1), 303-328.
Lectures 8-9. Empirical Studies and Applications June 6 and 13
Presentations
Hakimov, Heller, Kübler, & Kurino (2021) --- Zichong YUE June 6
Rees-Jones (2018) --- Ruihan WANG June 13
Correa et al. (2021) --- Yunzhi LIU June 13
References
Abdulkadiroğlu, A., Angrist, J. D., Narita, Y., & Pathak, P. A. (2017). Research design meets market design: Using centralized assignment for impact evaluation. Econometrica, 85(5), 1373-1432.
Agarwal, N. (2015). An empirical model of the medical match. American Economic Review, 105(7), 1939-78.
Agarwal, N., & Somaini, P. (2018). Demand analysis using strategic reports: An application to a school choice mechanism. Econometrica, 86(2), 391-444.
Artemov, G., Che, Y. K., & He, Y. (2017). Strategic ‘mistakes’: Implications for market design research. NBER Working Paper.
Correa, J., Epstein, N., Epstein, R., Escobar, J., Rios, I., Aramayo, N., ... & Subiabre, F. (2021). School choice in Chile. Operations Research.
Fack, G., Grenet, J., & He, Y. (2019). Beyond truth-telling: Preference estimation with centralized school choice and college admissions. American Economic Review, 109(4), 1486-1529.
Galichon, A., Kominers, S. D., & Weber, S. (2019). Costly concessions: An empirical framework for matching with imperfectly transferable utility. Journal of Political Economy, 127(6), 2875-2925.
Hakimov, R., Heller, C., Kübler, D., & Kurino, M. (2021). How to avoid black markets for appointments with online booking systems. American Economic Review, 111(7), 2127-51.
Pathak, P. A., Sönmez, T., Unver, M. U., & Yenmez, M. B. (2020). Leaving no ethical value behind: triage protocol design for pandemic rationing (No. w26951). National Bureau of Economic Research.
Rees-Jones, A. (2018). Suboptimal behavior in strategy-proof mechanisms: Evidence from the residency match. Games and Economic Behavior, 108, 317-330.
Sönmez, T., & Switzer, T. B. (2013). Matching with (branch‐of‐choice) contracts at the United States Military Academy. Econometrica, 81(2), 451-488.
Uetake, K., & Watanabe, Y. (2020). Entry by merger: Estimates from a two-sided matching model with externalities. Available at SSRN 2188581.
Waldinger, D. (2021). Targeting in-kind transfers through market design: A revealed preference analysis of public housing allocation. American Economic Review, 111(8), 2660-96.
ADVANCED TOPICS
Lecture 10. School Choice: Part 2 June 20
Haeringer: Chapter 14
Presentations
Pathak & Sönmez (2008) --- Yuhao FU
Erdil & Ergin (2008) --- Ruihan WANG
References
Abdulkadiroğlu, A., Che, Y. K., & Yasuda, Y. (2011). Resolving conflicting preferences in school choice: The" Boston mechanism" reconsidered. American Economic Review, 101(1), 399-410.
Abdulkadiroğlu, A., Che, Y. K., & Yasuda, Y. (2015). Expanding" choice" in school choice. American Economic Journal: Microeconomics, 7(1), 1-42.
Erdil, A., & Ergin, H. (2008). What's the matter with tie-breaking? Improving efficiency in school choice. American Economic Review, 98(3), 669-89.
Pathak, P. A., & Sönmez, T. (2008). Leveling the playing field: Sincere and sophisticated players in the Boston mechanism. American Economic Review, 98(4), 1636-52.
Pathak, P. A., & Sönmez, T. (2013). School admissions reform in Chicago and England: Comparing mechanisms by their vulnerability to manipulation. American Economic Review, 103(1), 80-106.
Lecture 11. Chinese College Admission June 27
Presentations
Fang & Yasuda (2022a) --- Yuanju FANG June 27
References
Chen, Y., Jiang, M., & Kesten, O. (2020). An empirical evaluation of Chinese college admissions reforms through a natural experiment. Proceedings of the National Academy of Sciences, 117(50), 31696-31705.
Chen, Y., & Kesten, O. (2017). Chinese college admissions and school choice reforms: A theoretical analysis. Journal of Political Economy, 125(1), 99-139.
Fang, Y., & Yasuda, Y. (2022a). Improving Matching under Information Constraint: Chinese College Admission Reconsidered. mimeo
Fang, Y., & Yasuda, Y. (2022b). Two-sided Matching with Common Priority. mimeo
Pu, Y. (2020). College admission in three Chinese provinces: Province-specific versus pooling quotas. China Economic Review, 60, 101299.
Zhu, M. (2014). College admissions in China: A mechanism design perspective. China Economic Review, 30, 618-631.
Lecture 12. Matching with Wages and Contracts
Presentations
Adachi (2000) --- He WANG June 27
Hatfield & Milgrom (2005) --- Reo KURATA July 4
Bulow & Levin (2006) --- Junsi YU July 4
References
Adachi, H. (2000). On a characterization of stable matchings. Economics Letters, 68(1), 43-49.
Bulow, J., & Levin, J. (2006). Matching and price competition. American Economic Review, 96(3), 652-668.
Crawford, V. P., & Knoer, E. M. (1981). Job matching with heterogeneous firms and workers. Econometrica: Journal of the Econometric Society, 437-450.
Demange, G., & Gale, D. (1985). The strategy structure of two-sided matching markets. Econometrica: Journal of the Econometric Society, 873-888.
Hatfield, J. W., & Milgrom, P. R. (2005). Matching with contracts. American Economic Review, 95(4), 913-935.
Kelso Jr, A. S., & Crawford, V. P. (1982). Job matching, coalition formation, and gross substitutes. Econometrica: Journal of the Econometric Society, 1483-1504.
Kojima, F. (2007). Matching and price competition: comment. American Economic Review, 97(3), 1027-1031.
Sattinger, M. (1993). Assignment models of the distribution of earnings. Journal of economic literature, 31(2), 831-880.
Lecture 13. Affirmative Actions July 11
Presentations
Abdulkadiroğlu (2005) --- Hidetoki NAKAYAMA
Kojima (2012). --- Yuichi OKADA
References
Abdulkadiroğlu, A. (2005). College admissions with affirmative action. International Journal of Game Theory, 33(4), 535-549.
Dur, U., Pathak, P. A., & Sönmez, T. (2020). Explicit vs. statistical targeting in affirmative action: Theory and evidence from Chicago's exam schools. Journal of Economic Theory, 187, 104996.
Echenique, F., & Yenmez, M. B. (2015). How to control controlled school choice. American Economic Review, 105(8), 2679-94.
Ehlers, L., Hafalir, I. E., Yenmez, M. B., & Yildirim, M. A. (2014). School choice with controlled choice constraints: Hard bounds versus soft bounds. Journal of Economic theory, 153, 648-683.
Hafalir, I. E., Yenmez, M. B., & Yildirim, M. A. (2013). Effective affirmative action in school choice. Theoretical Economics, 8(2), 325-363.
Kojima, F. (2012). School choice: Impossibilities for affirmative action. Games and Economic Behavior, 75(2), 685-693.
Kominers, S. D., & Sönmez, T. (2016). Matching with slot‐specific priorities: Theory. Theoretical Economics, 11(2), 683-710.
Sönmez, T., & Yenmez, M. B. (2019). Affirmative action in India via vertical and horizontal reservations. Boston College.
Lecture 14. General Distributional Constraints
Presentations
References
Kamada, Y., & Kojima, F. (2015). Efficient matching under distributional constraints: Theory and applications. American Economic Review, 105(1), 67-99.
Kamada, Y., & Kojima, F. (2019). Fair matching under constraints: Theory and applications. Rev. Econ. Stud.
Goto, M., Iwasaki, A., Kawasaki, Y., Kurata, R., Yasuda, Y., & Yokoo, M. (2016). Strategyproof matching with regional minimum and maximum quotas. Artificial intelligence, 235, 40-57.
Nguyen, T., & Vohra, R. (2019). Stable matching with proportionality constraints. Operations Research, 67(6), 1503-1519.
Lecture X. Probabilistic Assignments
Haeringer: Chapter 12
References
Abdulkadiroğlu, A., & Sönmez, T. (1998). Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica, 66(3), 689-701.
Akbarpour, M., & Nikzad, A. (2020). Approximate random allocation mechanisms. The Review of Economic Studies, 87(6), 2473-2510.
Bogomolnaia, A., & Moulin, H. (2001). A new solution to the random assignment problem. Journal of Economic theory, 100(2), 295-328.
Che, Y. K., & Kojima, F. (2010). Asymptotic equivalence of probabilistic serial and random priority mechanisms. Econometrica, 78(5), 1625-1672.
Lecture Y. Other Advanced Topics
References
Adachi, H. (2003). A search model of two-sided matching under nontransferable utility. Journal of Economic Theory, 113(2), 182-198.
Aygün, O., & Turhan, B. (2020). Dynamic reserves in matching markets. Journal of Economic Theory, 188, 105069.
Azevedo, E. M., & Budish, E. (2019). Strategy-proofness in the large. The Review of Economic Studies, 86(1), 81-116.
Azevedo, E. M., & Leshno, J. D. (2016). A supply and demand framework for two-sided matching markets. Journal of Political Economy, 124(5), 1235-1268.
ECHENIQUE, F., & OVIEDO, J. (2006). A theory of stability in many-to-many matching markets. Theoretical Economics, 1, 233-273.
Fleiner, T. (2003). A fixed-point approach to stable matchings and some applications. Mathematics of Operations research, 28(1), 103-126.
Hatfield, J. W., & Kominers, S. D. (2017). Contract design and stability in many-to-many matching. Games and Economic Behavior, 101, 78-97.
Kojima, F., & Pathak, P. A. (2009). Incentives and stability in large two-sided matching markets. American Economic Review, 99(3), 608-27.
Kurino, M. (2014). House allocation with overlapping generations. American Economic Journal: Microeconomics, 6(1), 258-89.
Ostrovsky, M. (2008). Stability in supply chain networks. American Economic Review, 98(3), 897-923.
Pycia, M. (2012). Stability and preference alignment in matching and coalition formation. Econometrica, 80(1), 323-362.
Back to top.
Survey Articles | サーベイ論文
Abdulkadiroglu, A. and Sonmez, T. (2013), Matching Markets: Theory and Practice, in Advances in Economics and Econometrics; 10th World Congress, Edited by Daron Acemoglu, Manuel Arellano, Eddie Dekel.
Chade, H., Eeckhout, J. and Smith, L. (2016), Sorting Through Search and Matching Models in Economics, working paper (prepared for Journal of Economic Literature)
Chiappori, P. A., & Salanié, B. (2016). The econometrics of matching models. Journal of Economic Literature, 54(3), 832-61.
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
Knuth, D. (1976), Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms, English Reprint (1996). Amazon
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)
抄訳版が『経済セミナー』（2016年6・7月号に掲載されています）
Kojima, F. and Troyan, P. (2011), Matching and Market Design: An Introduction to Selected Topics, Japanese Economic Review, 62: 82–98.
Kurino, M. (2020). Credibility, efficiency, and stability: A theory of dynamic matching markets. The Japanese Economic Review, 71(1), 135-165.
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.
Pathak, P. A. (2011). The mechanism design approach to student assignment. Annu. Rev. Econ., 3(1), 513-536.
Roth, A. (2002), The Economist as Engineer: Game Theory, Experimentation, and Computation as Tools for Design Economics, Econometrica, 70: 1341-1378.
Roth, A. (2003), The Origins, History, and Design of the Resident Match, Journal of the American Medical Association, 289 :909-912.
Roth, A. (2008a), Deferred acceptance algorithms: history, theory, practice, and open questions, International Journal of Game Theory, 36: 537-569.
Roth, A. (2008b), What Have We Learned from Marked Design?, Economic Journal, 118: 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.
Sonmez, 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.
Sonmez, T. and Unver, U. (2013). MARKET DESIGN FOR KIDNEY EXCHANGE. in Handbook of Market Design, 93.
Topkis, D. (1998), Supermodularity and Complementarity. Amazon (Kindle)
Vives, X. (1999), Oligopoly Pricing: Old Ideas and New Tools. Amazon
Vohra, R. (2004), Advanced Mathematical Economics. Amazon (Kindle)
小島武仁・安田洋祐, マッチング・マーケットデザイン, 経済セミナー, (647), 135-145, 2009. 増補改訂版
坂井豊貴, マーケットデザイン: 最先端の実用的な経済学, ちくま新書, 2013. Amazon
マーケットデザインの日本語による包括的な入門書です。交換問題（講義では扱わない予定）と、その応用例である臓器移植マッチングについての記述が非常に詳しいです。
安田洋祐, マッチングの数理, 数学セミナー, 4月号, 2013. 草稿
安田洋祐, 学校選択問題のマッチング理論分析, 現代経済学の潮流2014（第4章, pp.95-122）, 東洋経済新報社, 2014.
安田洋祐（編著）, 学校選択制のデザイン：ゲーム理論アプローチ（編著）, NTT出版, 2010. Amazon
学校選択制のマッチング理論分析に関する本格的な研究書です。日米の現実の制度的な背景や、マッチング理論の基礎および新展開などについて詳しく論じています。
References | 参考文献
TBA