Econ 182 Fall 2015

ECON 182: Honors Market Design

Class Time: Mondays and Wednesdays, 9:30-11:20

Location: Econ 218

Office Hours: by appointment

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.

Basic Textbooks(s)

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

I have just finished a survey paper, Recent Developments in Matching Theory and its Practical Applications to appear in "Advances in Economics and Econometrics: 11th World Congress", and this will be highly relevant to this class as well. Comments are greatly appreciated!

Here is a general audience book on market design,

http://www.amazon.com/Who-Gets-What-Compensation-Financial/dp/1586489771

The book is not tightly linked to the material of this course, but it gives a very nice perspective on the topic of market design in general, and I highly recommend it.

Grading

The grade will depend on 3 problem sets (30 percent), one or more class presentations and participation in discussion (30 percent) and one final paper (40 percent).

(1) The problem sets are assigned 3 times throughout the course (tentative plan: September 23rd, October 7th, and 21st) and due in one week in the beginning of 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 class presentation is about either a student’s own research or discussion of a research paper of someone else. Usually it is very hard to write an original paper on your own in a short amount of time, so you can think of a literature review as a default; don't think of your "original research" to be superior at this point, because understanding a paper by someone else is a very important step for writing a creative paper!

(3) The suggested length of the final paper is about 5-8 pages (tentative plan: due on December 4th Friday, 4pm). You can write an original research paper or a critical literature review. As is the case for (2), think of a literature review as a default option, but I welcome an original research paper if you choose to do so. If you choose to do so, write to me in advance so that I can suggest if your topic is in a good direction.

Prerequisite

Basic knowledge in microeconomics and game theory is useful, but it's 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.

Problem Sets

Class Slides

Classes 1, 2, 3 (September 21, 23, 28)

Classes 4, 5, (September 30, October 5)

Class 6: Guest Lecture by Al Roth (October 7)

Class 7, 8 (October 12, 14)

Class 9: Guest Lecture by Itai Ashlagi (October 19)

Class 10, 11 (October 21, 26)

Class 12 (October 28)

Class 13: Guest Lecture by Al Roth (November 2)

Class 14 (November 4)

Class 15: Guest Lecture by Muriel Niederle (November 9)

Class 16 (November 11)

Class 17-20: Student Presentations

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: One-sided matching: basic theory

Class 5: Application: Kidney exchange and university housing

Class 6: Kidney exchange continued: recent developmentsｓ

Class 7: School choice: basic theory

Class 8: School choice: recent developments

Class 9: Random assignment; Using Lottery for Fair Allocations

Class 10: Random assignment; Applications

Class 11: Combinatorial Assignment Problem

Class 12: Matching with Constraints

In addition, depending on availability and interest, I might invite 2 or 3 guest speakers.

After lectures by me, I will ask you to do presentations--- I will ask you to schedule the presentations during the quarter (4th week or so).

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

I. Ashlagi, M. Braverman, and A. Hassidim (2014) “Stability in Matching Markets with Complementarities,” Operations Research

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.

Fuhito Kojima, “Finding All Stable Matchings with Couples,” mimeo

F. Kojima, P.A. Pathak, and Alvin E. Roth (2013), “Matching with Couples: Stability and Incentives,” Quarterly Journal of Economics

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, mimeo

Yeon-Koo Che, Jinwoo Kim, and Fuhito Kojima, Stable Matching in Large Economies (2015), mimeo

Class 4-6:

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

*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

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 7-8: School choice:

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

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 9-10: 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 11: Combinatorial Assignment Problem

*Eric Budish, The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes

*Eric Budish and Estelle Cantillon, The Multi-Unit Assignment Problem: Theory and Evidence from Course Allocation at Harvard

Eric Budish, Yeon-Koo Che, Fuhito Kojima, and Paul Milgrom, Implementing Random Assignments: A Generalization of the Birkhoff-von Neumann Theorem (2009),

Kojima, F, Random Assignment of Multiple Indivisible Objects (2007), forthcoming, Mathematical Social Sciences.

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.

Class 12: Matching with 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), mimeo

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

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. If you choose to present a paper that is not listed in this website, please write to me in advance so that I can tell you whether the paper is suitable for presentation in this class.

Haluk Ergin, Tayfun Sonmez, and Utku M. Unver, “Lung Exchange,” mimeo

Umut Dur and Utku M. Unver, Two-Sided Matching via Balanced Exchange: Tuition and Worker Exchanges, mimeo (R&R JPE)

SangMok Lee and Leeat Yariv, On the Efficiency of Stable Matchings in Large Markets

Marek Pycia and Bumin Yenmez, Matching with Externalities, mimeo

Bumin Yenmez, College Admissions, mimeo

John William Hatfield, Scott Duke Kominers, Alexandru Nichifor, Michael Ostrovsky, and Alexander Westkamp, Chain Stability in Trading Networks, April 2015, Revise and resubmit, Econometrica.

Sampath Kannan, Jamie Morgenstern, Aaron Roth, and Steven Wu, Approximately Stable, School Optimal, and Student-Truthful Many-to-One Matching (via Differential Privacy), SODA 2015

Eduardo Azevedo and John William Hatfield, Complementarity and Multidimensional Heterogeneity in Large Matching Markets, mimeo

Thanh Nguyen and Rakesh Vohra, Near Feasible Stable Matchings with Complementarities, mimeo

Gabriel Carroll, On Mechanisms Eliciting Ordinal Preferences

Yinghua He, Antonio Miralles, Marek Pycia, and Jianye Yan, "A Pseudo-Market Approach to Allocation with Priorities" mimeo

Tamas Fleiner and Zsuzsanna Janko, Choice Function Based Two-Sided Markets: Stability, Lattice Property, Path Independence and Algorithms, mimeo

Ivan Balbuzanov, Short Trading Cycles: Kidney Exchange with Strict Ordinal Preferences, mimeo

Onur Kesten and Utku M. Unver, A Theory of School-Choice Lotteries , TE

Eric Budish and Judd Kessler, Changing the Course Allocation Mechanism at Wharton, mimeo

Itai Ashlagi and Peng Shi, Optimal Allocation Without Money: an Engineering Approach, Management Science, forthcoming

Eric Budish and Eduardo Azevedo, Strategy-Proofness in the Large, mimeo

Itai Ashlagi and Peng Shi, Improving Community Cohesion in School Choice via Correlated-Lottery Implementation, Operations Research, forthcoming.

John William Hatfield, Scott Duke Kominers, Alexandru Nichifor, Michael Ostrovsky, and Alexander Westkamp, Substitutability in Trading Networks

Michael Ostrovsky and Renato Paes Leme, Gross Substitutes and Endowed Assignment Valuations, TE

Itai Ashlagi and Afshin Nikzad, What matters in tie-breaking rules? How competition guides design.

Itai Ashlagi, Afshin Nikzad, Assaf Romm, Assigning more students to their top choices: A tiebreaking rule comparison (extended abstract in EC 15).

Fuhito Kojima, Recent Developments in Matching Theory and its Practical Applications, mimeo

Fuhito Kojima, Akihisa Tamura, and Makoto Yokoo, Designing Matching Mechanisms under Constraints: An Approach from Discrete Convex Analysis, mimeo

Yeon-Koo Che and Olivier Tercieux, Efficiency and Stability in Large Matching Markets, mimeo

Yeon-Koo Che and Olivier Tercieux, An Analysis of Top Trading Cycles in Two-Sided Matching Markets, mimeo

Yeon-Koo Che and Olivier Tercieux Payoff Equivalence of Efficient Mechanisms in Large Matching Markets, mimeo

Large Matching Markets as Two-Sided Demand Systems, Econometrica 83(3) (2015), 897-941

Yan Chen and Onur Kesten, College and High School Admissions Reforms in China: A Theoretical Analysis, Journal of Political Economy