Econ 289 Spring 2014

Econ 289: Topics in Game Theory

Location: Econ 139

Office Hours: Monday and Wednesday 10:50-12

Instructor: Fuhito Kojima

fuhitokojima1979 “at” gmail.com (replace “at” with @)

http://sites.google.com/site/fuhitokojimaeconomics/

(This syllabus is evolving: Please check the latest version frequently. Last updated: 03/28/2014)

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 is a topics course in game theory. We discuss mechanism/market design, especially theory and application of matching theory.This class builds on material covered in Econ 285.

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.

About half of the classes are delivered in the lecture style. Then the latter half of the course is based on student presentations of recent research papers. Depending on availability of time (which depends on enrollment) and interest, I am planning to invite outside speakers for guest lectures (current plan: Dan Fragiadakis, Peter Biro, Bobby Pakzad-Hurson).

Grading

Grading will be based on class participation (discussion, student presentations) and a final paper (suggested length 10 pages).

Prerequisite

Game theory at the 1st year PhD level. Also it is strongly recommended that you have taken Econ 285, because many of the topics are based on the material covered there.

If not, please familiarize yourself with the topic, by taking a look at slides at, for example,

http://www.stanford.edu/~niederle/marketdesign2012.htm

Textbooks

The recommended textbook is

Two-Sided Matching by Roth and Sotomayor (1990) from Cambridge University Press.

I will also assign research papers.

Slides

Class 1 (04/01)

Class 2 (04/03)

Class 3 (04/08) + Class 5 (04/15)

Class 4 (04/10); Guest Lecture by Dan Fragiadakis

Class 6 (04/17)

Class 7 (04/22)

Class 8 (04/24); Guest Lecture by Peter Biro

Class 9 (04/29)

Class 10 (05/01): Guest Lecture by Itai Ashlagi

Class 11 (05/06)

Class 12 (05/08): Guest Lectures by Afshin Nikzad and Bobby Pakzad-Hurson

Class 13 (05/13)

Lecture Topics (the plan is tentative and may evolve depending on student interests and how the class proceeds). Papers with * are the main readings for the class.

Class 1: Introduction/ Design of Labor Market Clearinghouses

    • *Roth and Sotomayor (1990), Chapters 2-4.

    • Gale, David and Lloyd Shapley (1962), “College Admissions and the Stability of Marriage” American Mathematical Monthly, 69, 9-15.

    • *Kojima, F. and Pathak, P. A. (2008), “Incentives and Stability in Large Two-Sided Matching Markets,” American Economic Review 99, pp 608-627.

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

    • Immorlica, N. and Mahdian, M. (2005), “Marriage, Honesty, and Stability,” SODA 2005, pp. 53–62.

Class 2: “Rural Hospital Theorem” and Related Topics

Classes 3 and 4: School Choice and Efficient Priority-Based Allocations

    • Abdulkadiroğlu, Atila, and Tayfun Sönmez (2003), "School Choice: A Mechanism Design Approach," American Economic Review, 93: 729-747.

    • *Haluk Ergin (2002) “Efficient Resource Allocation on the Basis of Priorities,” Econometrica, 70, 2489–2498.

  • *Guillaume Haeringer and Flip Klijn Constrained school choice, Journal of Economic Theory, 144, 1921-1947 (2009)

  • *Fuhito Kojima "Robust Stability in Matching Markets" forthcoming, Theoretical Economics.

  • Kesten, Onur, On Two Kinds of Manipulation for School Choice Problems, forthcoming, Economic Theory

  • Fuhito Kojima, Efficient Resource Allocation under Multi-unit Demand (2011), mimeo

  • *Kesten, Onur, “On Two Competing Mechanisms for Priority Based Allocation Problems,” Journal of Economic Theory 127, 2006; 155-171.

  • Lars Ehlers and Aytek Erdil, Efficient Assignment Respecting Priorities, forthcoming, Journal of Economic Theory.

Class 5: Design of Random Assignment Mechanisms (1)

    • Abdulkadiroglu, A., and T. Sonmez (2003) “Ordinal Efficiency and Dominated Sets of Assignments,” Journal of Economic Theory, 112, 157—172.

  • Abdulkadiroglu, A., and T. Sonmez (1998): “Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems,” Econometrica, 66, 689-698.

  • *Bogomolnaia, A., and H. Moulin (2001), “A New Solution to the Random Assignment Problem,” Journal of Economic Theory, 100, 295-328.

  • *Che, Yeon-Koo and Fuhito Kojima, “Asymptotic Equivalence of Random Priority and Probabilistic Serial Mechanisms,” forthcoming, Econometrica.

  • Hylland and Zeckhauser (1979), “The efficient allocation of Individuals to Positions”, Journal of Political Economy.

  • 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?,” forthcoming, journal of economic theory.

  • *Fuhito Kojima and Mihai Manea, “Incentives in the Probabilistic Serial Mechanism,” forthcoming, 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

  • Manea, Mihai, “Asymptotic Ordinal Inefficiency of Random Serial Dictatorship,” forthcoming, Theoretical Economics.

Class 6: Design of Random Assignment Mechanisms (2):

    • Hylland and Zeckhauser (1979), “The efficient allocation of Individuals to Positions”, Journal of Political Economy.

    • *Eric Budish, Yeon-Koo Che, Fuito Kojima, and Paul Milgrom (2011), “Designing Random Allocation Mechanisms: Theory and Applications”, forthcoming, AER.

    • *Daisuke Hirata and Tadashi Hashimoto, " Characterizations of the Probabilistic Serial Mechanism

Class 7: Mechanism design with interdependent values (1)

*Two-Sided Matching with Interdependent Values Archishman Chakraborty, Alessandro Citanna and Michael Ostrovsky, Journal of Economic Theory, forthcoming.

*P Jehiel, B Moldovanu Efficient design with interdependent valuations Econometrica

*Efficient Auctions*jstor.org [PDF]

Find it@Stanford P Dasgupta, E Maskin - Quarterly Journal of Economics, 2000 - MIT Press

"An Efficient Multi-Unit Ascending Auction." Motty Perry and Philip J. Reny; The Review of Economic Studies, 2005, 72(2), pp. 567.

http://dx.doi.org/10.1111/j.1467-937X.2005.00343.x

Class 8: Mechanism design with interdependent values (2)

*Jehiel, P., M. Meyer-ter-Vehn, B. Moldovanu and W. R. Zame, (2006): “The Limits of ex post Implementation,” Econometrica, 74(3), 585-610.

Generic Impossibility of Partial Ex Post Implementation with General Utility Functions Tadashi Hashimoto

*Yeon-Koo Che, Jinwoo Kim, and Fuhito Kojima, "Efficient Assignment under Interdependent Values", mimeo.

Class 9: Guest Lecture: Tadashi Hashimoto (Stanford GSB)

Tadashi Hashimoto, The Generalized Random Priority Mechanism with Budgets , mimeo

Class 10: Resource allocation with multi-unit demands

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

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 11: School Competition,


The following lectures are not given this year:

Class **: Characterizations of Assignment Mechanisms

  • L. Ehlers and B. Klaus (2009): "Allocation via Deferred Acceptance," mimeo

  • *Fuhito Kojima and Mihai Manea: "Axioms for Deferred Acceptance," forthcoming, Econometrica.

  • *Papai, Szilvia, “Strategy-proof Assignments by Hierarchical Exchange,” Econometrica 68, 1403-1433

  • Fuhito Kojima and Utku Unver, "The Boston School Choice Mechanism," mimeo.

  • Lars-Gunnar Svensson (1999) “Strategyproof Allocation of Indivisible Goods,” Social Choice and Welfare 16, 557-567.

  • Utku Unver and Marek Pycia, A Theory of House Allocation and Exchange Mechanisms , mimeo

Class **: Monotone Methods and Matching


Additional Guest Lectures: TBA

Classes 12-: Student Presentations

Students can present one of the papers in the above reading list, 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 are presenting papers not on this list, please email me so that we can make sure that the paper is related enough to the class topics and/or interesting enough to the audience). Alternatively, we are also welcome to present your own work: remember, you will be asked to write a final paper that is your own research, so it may help to present the paper in front of the class during the quarter.

Atila Abdulkadiroğlu, Parag Pathak, Alvin Roth and Tayfun Sonmez, “Changing the Boston School Choice Mechanism,” mimeo

Niederle, Muriel, and Alvin E. Roth, “Making Markets Thick: Designing Rules for Offers and Acceptances”, mimeo

Pathak, P. “Lotteries in Student Assignment,” TE

Marek Pycia and Utku Unver, “A Theory of House Allocation and Exchange Mechanisms,” mimeo

Utku Unver, “Dynamic Kidney Exchange,” REStud

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

Valuing Prearranged Paired Kidney Exchanges: A Stochastic Game Approach (Murat Kurt, Mark Roberts, Andrew Schaefer, and Utku Unver) Boston College Working Papers in Economics, No: 785; revision requested from Operations Research

A Theory of School-Choice Lotteries (Onur Kesten and Utku Unver) Boston College Working Papers in Economics, No: 737

Unraveling Results from Comparable Demand and Supply: An Experimental Investigation (Muriel Niederle, Alvin E. Roth, and Utku Unver)

Strategy-proof Stochastic Assignment, Aytek Erdil

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), SangMok Lee

“The difference indifference makes in strategy-proof allocation of objects,” forthcoming, Journal of Economic Theory. (Paula Jaramillo and Vikram Manjunath)

Manjunath, Vikram, “A market approach to fractional matching,” 2011.

Dur and Unver, Tuition Exchange

Dur, Kominers, Pathak, and Sonmez,

Priorities vs. Precedence in School Choice:Theory and Evidence from Boston

Gabrielle Caroll, When are Local Incentive Constraints Sufficient? / Online appendix (Econometrica, forthcoming)

Carroll, On Mechanisms Eliciting Ordinal Preferences

Carroll, A General Equivalence Theorem for Allocation of Indivisible Objects

Carooll, Efficient Random Assignment with Constrained Rankings

Aaron Bodoh-Creed, http://www.economics.cornell.edu/ab882/LargeMatching.pdf

Yeon-Koo Che and Youngwoo Koh, Decentralized College Admissions, mimeo