Econ 289: Topics in Game Theory
Instructor: Fuhito Kojima
fuhitokojima1979 “at” gmail.com (replace “at” with @)
(617) -699-1942
http://sites.google.com/site/fuhitokojimaeconomics/
Time and Location (attention: changed from the originally announced ones)
Time: Monday& Thursday, 4:15-6:05 PM
Location: room 130, the Education building.
Syllabus (this syllabus is evolving and will be modified as the class proceeds. See also the University website)
This is a topics course in game theory. A variety of topics will be covered, but an emphasis is on mechanism/market design, such as matching theory and auction theory.
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 will assign papers to read for each class, and sometimes ask students to present in front of the class.
Grading
Grading will be based on class participation (discussion, student presentations) and one final paper plus a midterm paper (added 12/29/2009).
* The deadline for the midterm is February 18th. I want you to write up either (1) a rough draft of the final or (2) a substantial literature review (updated 01/14/2010).
(1) I want you to encourage you to use the midterm assignment as opportunity to jump-start the final project.
(2) If you choose to do a literature review, please write not only summaries of papers, but also put in your thoughts/perspective (updated 01/14/2010).
* The deadline for the final paper is March 19th. You are welcome to use a paper that you are working on your own or for another class,
as long as it is on the topic of game theory and is appropriate in terms of relevance and quality.
This means that you can even use your work you submitted for my market design class last quarter as long as you make a substantial progress on the previous version.
This is not because I want to give you easy time, but to encourage you to write a paper that is very serious and potentially publishable.
So if you use a paper used for Econ 285, grading may be a bit more strict.
*There are two presentations. One is tentatively scheduled on February 8th or 11th. Each presentation lasts about 20 minutes (including questions and answers)
You can choose either to (1) present your own research for the midterm paper, or (2) choose a paper written by someone else and present it.
For the papers to present, feel free to choose any paper on the reading list below that is not attached the asterisk (*).
If you want to present something that is not on the list, write to me and we will figure out whether the paper is suitable for the class. (updated 01/14/2010).
The other presentation is a presentation on the final paper, tentatively scheduled either on March 4th or 8th or 11th.
Each presentation lasts about 20 minutes (including questions and answers)
Joint projects are welcome. Let me know.
Prerequisite
Game theory at the 1st year PhD level.
Also it is strongly recommended that you have taken Econ 285, because some 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
http://sites.google.com/site/economics285fall09/
Textbooks
Recommended textbooks are
Two-Sided Matching by Roth and Sotomayor (1990) from Cambridge University Press.
Putting Auction Theory to Work by Milgrom (2004) from Cambridge University Press.
I will also assign research papers.
Lecture Schedules and Topics: (the plan is tentative and may change depending on student interests and how the class proceeds.)
(* indicates required reading)
(1) Topics in Resource Allocation Mechanisms
January 4th (Mon): School Choice (and Other Resource Allocation Problems) Slides
*Abdulkadiroğlu, Atila, and Tayfun Sönmez (2003), "School Choice: A Mechanism Design Approach," American Economic Review, 93: 729-747.
Michel Balinski and Tayfun Sonmez “A Tale of Two Mechanisms: Student Placement” Journal of Economic Theory 84: 73-94, January 1999.
Roth, Alvin E. “Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions,” International Journal of Game Theory 36, 537-569.
January 7th (Th): Efficient Resource Allocation Slides
*Haluk Ergin (2002) “Efficient Resource Allocation on the Basis of Priorities,” Econometrica, 70, 2489–2498.
Yusuke Narita, Efficient Resource Allocation on the Basis of Priorities: A Comment, mimeo
*Kesten, Onur, “On Two Competing Mechanisms for Priority Based Allocation Problems,” Journal of Economic Theory 127, 2006; 155-171.
Taro Kumano, Efficient Resource Allocation under Acceptant Substitutable Priorities, mimeo
Lars Ehlers and Aytek Erdil, Efficient Assignment Respecting Priorities, forthcoming, Journal of Economic Theory.
Kesten, Onur, "School Choice with Consent," forthcoming, Quarterly Journal of Economics
January 11th (Mon): Application of Acyclicity in Resource Allocation Problems Slides
*Guillaume Haeringer and Flip Klijn Constrained school choice, Journal of Economic Theory, 144, 1921-1947 (2009)
*Fuhito Kojima "Robust Stability in Matching Markets" mimeo.
Kesten, Onur, On Two Kinds of Manipulation for School Choice Problems, mimeo
January 14th (Th): Incentive Compatible Market Design and an application to matching (Guest Lecture: Bumin Yenmez, Stanford GSB)
*Yenmez, Bumin Incentive Compatible Market Design with an Application to Matching with Wages
Tayfun Sonmez, “Strategy-Proofness and Essentially Single-Valued Cores,” Econometrica 67: 677-689, May 1999.
The assignment game I: The core LS Shapley, M Shubik - International Journal of Game Theory, 1971
"The Multiple-partners Assignment Game with Heterogeneous Sells and Multi-unit Demands: Competitive Equilibria," D. Jaume, J. Massó and A. Neme. mimeo.
January 18th (Mon): No Class (holiday)
January 21st (Th): Characterization of Allocation Mechanisms Slides
*L. Ehlers and B. Klaus (2009): "Allocation via Deferred Acceptance," CIREQ Cahier 17-2009: downloadable downloadable
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
(2) Tarski's Theorem and its applications to game theory and matching/market design
January 25th (Mon): Math review on Tarski's Fixed Point Theorem; Application to Supermodular Games and Matching Slides
Donald Topkis, Supermodularity and complementarity, Princeton University Press
*P Milgrom, J Roberts, Rationalizability, learning, and equilibrium in games with strategic complementarities - Econometrica
P Milgrom, C Shannon, Monotone comparative statics - Econometrica, 1994
Adachi, Hiroyuki, “On a characterization of stable matchings,” Economics Letters, 2000, 68, 43–49.
Echenique, Federico "A Characterization of Strategic Complementarities"
Games and Economic Behavior. Volume 46, Issue 2, Pages 325-347 (February 2004). [PDF]
Echenique, Federico, and Chris Chambers "Supermodularity and Preferences"
Journal of Economic Theory,. Volume 144, Issue 3, May 2009, Pages 1004-1014
Echenique, Federico and Jorge Oviedo, “Core Many-to-One Matchings by Fixed Point Methods,” Journal of Economic Theory, 2004, 115, 358– 376.
Echenique, Federico and Jorge Oviedo, “A theory of stability in many-to-many matching,” Theoretical Economics, 2006, 1, 233–273.
"A Solution to Matching with Preferences over Colleagues" (joint with M. Bumin Yenmez).
Games and Economic Behavior Volume 59, number 1, April 2007, pages 46-71.
"Finding All Equilibria in Games with Strategic Complements"
Journal of Economic Theory Volume 135, Issue 1, July 2007, Pages 514-532.
*Hatfield, John William and Paul R.Milgrom, “Matching with Contracts,” American Economic Review, 2005, 95, 913–935.
*Ostrovsky, Michael, “Stability in Supply Chain Networks,” American Economic Review, 2007, forthcoming.
Kandori, Kojima and Yasuda Understanding Stable Matchings: A Noncooperative Approach, mimeo.
(3) Mechanism design with interdependent values
January 28th (Th): Matching with Interdependent Values Slides
*Two-Sided Matching with Interdependent Values Archishman Chakraborty, Alessandro Citanna and Michael Ostrovsky, Journal of Economic Theory, forthcoming.
February 1st (Mon): Bayesian Implementation Slides
*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
February 4th (Th): Ex Post Implementation Lecture by Tadashi Hashimoto (Stanford GSB) Slides
*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
Chung and Ely "Ex Post Incentive Compatible Mechanism Design" mimeo,
http://sites.google.com/site/kimsauchung/expost.pdf
D Bergemann, S Morris(2005) Robust mechanism design, Econometrica
February 8th (Mon) and 11th (Th): Student Presentation
February 15th (Mon): No Class (holiday)
(4) Multi-unit auction
February 18th (Th): Introduction, Vickrey Auction and its problems Slides
*Ausubel, Lawrence and Paul Milgrom (2006): “The lovely but lonely Vickrey auction,” in Cramton et.al. (2006),
in “Combinatorial Auctions”, The MIT Press.
Ausubel, Lawrence and Paul Milgrom (2006): “Ascending Proxy Auctions,” in Cramton et.al. (2006), “Combinatorial Auctions”, The MIT Press.
*Milgrom, P., (2004) Putting Auction Theory to Work, Cambridge University Press, Chapter 8
*Lawrence Ausubel and Paul Milgrom (2002), Ascending Auctions with Package Bidding, Frontiers of Theoretical Economics, 1, 1, Article 1.
F Gul, E Stacchetti The English auction with differentiated commodities,Journal of Economic Theory, 2000
F Gul, E Stacchetti Walrasian equilibrium with gross substitutes Journal of Economic Theory, 1999
February 22nd (Mon): Guest Lecture by Paul Milgrom Slides
*John Kagel, Yuanchuan Lien, and Paul Milgrom (2010), “Ascending Prices and Package Bidding: A Theoretical and Experimental Analysis ,” forthcoming in AEJ-micro.
*David Porter, Stephen Rassenti, and Verson Smith (2003), "Combinatorial auction design ", PNAS
February 25th (Th): Combinatorial Auction Mechanisms
F Gul, E Stacchetti The English auction with differentiated commodities,Journal of Economic Theory, 2000
F Gul, E Stacchetti Walrasian equilibrium with gross substitutes Journal of Economic Theory, 1999
Bikhchandani, JM Ostroy The package assignment modelS - Journal of Economic theory, 2002
N Sun, Z Yang Equilibria and indivisibilities: gross substitutes and complements Econometrica
N Sun, Z YangA Double-Track Auction for Substitutes and Complements Econometrica
*Milgrom, P., (2004) Putting Auction Theory to Work, Cambridge University Press, Chapter 8
*Ascending auctions with package bidding LM Ausubel, P Milgrom - Frontiers of Theoretical Economics, 2002
Cramton, P., Y. Shoham. and R. Steinberg (eds.) (2006): “Combinatorial Auctions,”
Ausubel, Lawrence (1999): “A Generalized Vickrey Auction,” Econometric Society World Congress 2000 Contributed Papers, 1257.
Ausubel, Lawrence (2004): “An Efficient Ascending-Bid Auction for multiple Objects,” American Economic Review, 94, 1452-1475.
Ausubel, Lawrence (2006): “An Efficient Dynamic Auction for Heterogenous Commodities,” American Economic Review, 96, 602-629.
Ausubel, Lawrence, Peter Cramton and Paul Milgrom (2006): “The Clock-Proxy Auction: A Practical Combinatorial Auction Design,”
in Cramton et.al. (2006), “Combinatorial Auctions”, The MIT Press.
Paul Milgrom, Assignment Messages and Exchanges, AEJ-Micro 1:2, August 2009, 95-113.
*Day and Milgrom, "Core-Selecting Auctions", International Journal of Game Theory.
*Douglas Bernheim and Michael Whinston, Menu auctions, resource allocation, and economic influence The quarterly journal of economics, 1986
Douglas Bernheim and Michael Whinston, Common Agency, Econometrica, 1986
Grossman and Helpman (1994), Protection for sale The American Economic Review, 1994
Laussel and Le Breton (1999) Conflict and Cooperation The Structure of Equilibrium Payoffs in Common Agency, Journal of Economic Theory.
March 1st (Mon): Resource allocation with multi-unit demands Slides
*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.
John Pratt and Richard Zeckhauser, The Fair and Efficient Division of the Winsor Family Silver, Management Science 1990
March 4th (Th): When should we use money for allocating goods? Slides/ Presentation by Dan Fragiadakis
*Yeon-Koo Che and Ian Gale, Market versus Non-Market Assignment of Ownership
*Weitzman, M. (1977), “Is the Price System or Rationing More Effective in Getting a Commodity to Those Who Need it Most?” The Bel l Journal of Economics, 8, 517-524.
March 8th (Mon) and 11th (Th): Student Presentations
(Topics That We Will Probably not Cover but Seem Interesting)
Linear programming, network flow and market design
Assignment Messages and Exchanges, Paul Milgrom, AEJ-Micro 1:2, August 2009, 95-113.
A solution to the random assignment problem on the full preference domain, Akshay-Kumar Katta and Jay Sethuraman. Journal of Economic Theory, 131(1):231-250, 2006.
House Allocation with Fractional Endowments, Stergios Athanassoglou and Jay Sethuraman, mimeo.
Ozgur Yilmaz, Random Assignment under Weak Preferences Games and Economic Behavior, forthcoming.
Sponsored search auctions
Benjamin Edelman and Michael Ostrovsky (2007), "Strategic Bidder Behavior in Sponsored Search Auctions", Decision Support Systems.
Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz (2007),
Hal R. Varian (2007), "Position Auctions", IJIO.
Mehmet B. Yenmez (2009), "Pricing in Position Auctions and Online Advertising", working paper.
Renato Gomes and Kane Sweeney (2009), "Bayes-Nash Equilibria of the Generalized Second Price", working paper (not available).
Michael Ostrovsky and Michael Schwarz (2009), "Optimal Auction Design: A Field Experiment", working paper.
Hashimoto, T. Equilibrium Selection and Inefficiency in Internet Advertising Auctions. (SSRN)
Dynamic Mechanism Design
Athey and Segal, “An Efficient Dynamic Mechanism," mimeo.
Utku Unver (2009), "Dynamic Kidney Exchange", REStud, forthcoming.
Pavan, Segal and Toikka (2009), "Dynamic Mechanism Design: Incentive Compatibility, Profit Maximization and Information Disclosure", working paper.
Communication Complexity, Social Choice and Implelentation
“Nash Implementation with Little Communication,” Ilya Segal, Theoretical Economics, forthcoming
“The Communication Cost of Selfishness,” Ronald Fadel and Ilya Segal, Journal of Economic Theory 144, 2009, pp. 1895-920
“The Communication Requirements of Social Choice Rules and Supporting Budget Sets,” Ilya Segal, Journal of Economic Theory, 136, September 2007, pp. 341-378
Other papers of interest
Christopher Avery and Jonathan Levin Early Admissions at Selective Colleges American Economic Review, forthcoming.
Ron Siegel, "All-Pay Contests." Econometrica, January 2009.
Ron Siegel, "Asymmetric Contests with Conditional Investments." American Economic Review, forthcoming. Online Appendix.