Econ 289: Topics in Game TheoryInstructor: Fuhito Kojima fuhitokojima1979 “at” gmail.com (replace “at” with @) (617) 6991942 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 jumpstart 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
TwoSided 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: 729747. Michel Balinski and Tayfun Sonmez “A Tale of Two Mechanisms: Student Placement” Journal of Economic Theory 84: 7394, January 1999.
Roth, Alvin E. “Deferred Acceptance Algorithms:
History, Theory, Practice, and Open Questions,” International Journal of Game
Theory 36, 537569.
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; 155171.
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, 19211947 (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, “StrategyProofness and Essentially SingleValued Cores,” Econometrica 67: 677689, May 1999.
The assignment game I: The core LS Shapley, M Shubik  International Journal of Game Theory, 1971
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 172009:
downloadable
downloadable
Fuhito Kojima and Mihai Manea: "Axioms for Deferred Acceptance," forthcoming, Econometrica.
Papai, Szilvia, “Strategyproof Assignments by Hierarchical Exchange,” Econometrica 68, 14031433LarsGunnar Svensson (1999)
“Strategyproof Allocation of Indivisible Goods,” Social Choice and Welfare 16,
557567.
(2) Tarski's Theorem and its applications to game theory and matching/market designJanuary 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
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 325347 (February 2004).
[PDF]
Echenique, Federico, and Chris Chambers "Supermodularity and Preferences"
Journal of Economic Theory,.
Volume 144, Issue 3, May 2009, Pages 10041014 Echenique, Federico and Jorge Oviedo, “Core
ManytoOne Matchings by Fixed Point Methods,” Journal of Economic Theory,
2004, 115, 358– 376.
Echenique, Federico and Jorge Oviedo, “A theory
of stability in manytomany 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 4671.
"Finding All Equilibria in Games with Strategic Complements"
Journal of Economic Theory
Volume 135, Issue 1, July 2007, Pages 514532.
*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
February 4th (Th): Ex Post Implementation Lecture by Tadashi Hashimoto (Stanford GSB) Slides *Jehiel, P., M. MeyerterVehn, B. Moldovanu and W. R. Zame, (2006): “The Limits of ex post Implementation,” Econometrica, 74(3), 585610. *Generic Impossibility of Partial Ex Post Implementation with General Utility Functions Tadashi Hashimoto
D Bergemann, S Morris(2005)
February 8th (Mon) and 11th (Th): Student Presentation
February 15th (Mon): No Class (holiday)
(4) Multiunit 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 Walrasian equilibrium with gross substitutes Journal of Economic Theory, 1999
February 22nd (Mon): Guest Lecture by Paul Milgrom Slides
February 25th (Th): Combinatorial Auction MechanismsF 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
*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 AscendingBid Auction for multiple Objects,” American Economic Review, 94, 14521475.
Ausubel, Lawrence (2006): “An Efficient Dynamic Auction for Heterogenous Commodities,” American Economic Review, 96, 602629.
Ausubel, Lawrence, Peter Cramton and Paul Milgrom (2006): “The ClockProxy Auction: A Practical Combinatorial Auction Design,” in Cramton et.al. (2006), “Combinatorial Auctions”, The MIT Press.
Paul Milgrom, Assignment Messages and Exchanges, AEJMicro 1:2, August 2009, 95113.
*Day and Milgrom, "CoreSelecting 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, 1994Laussel 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 multiunit demands Slides John William Hatfield, Strategyproof, efficient, and nonbossy quota allocations, Social Choice and Welfare, 2009.
Mihai Manea, Serial dictatorship and Pareto optimality, Games and Economic Behavior, 2007.
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
*Weitzman, M. (1977), “Is the Price System or Rationing More Eﬀective in Getting a Commodity to Those Who Need it Most?” The Bel l Journal of Economics, 8, 517524.
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, AEJMicro 1:2, August 2009, 95113.
A solution to the random assignment problem on
the full preference domain, AkshayKumar Katta and Jay Sethuraman.
Journal of Economic Theory, 131(1):231250, 2006.
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),
"Internet
Advertising and the Generalized Second Price Auction: Selling Billions of
Dollars Worth of Keywords", AER.
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), "BayesNash 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. 1895920
“The
Communication Requirements of Social Choice Rules and Supporting Budget
Sets,” Ilya Segal, Journal of Economic Theory, 136,
September 2007, pp. 341378Other papers of interestChristopher Avery and Jonathan Levin Early
Admissions at Selective Colleges American Economic Review, forthcoming.
Ron Siegel, " AllPay Contests." Econometrica, January 2009.
Ron Siegel, " Asymmetric Contests with Conditional Investments." American Economic Review, forthcoming.
Online Appendix. 

Updating...
Ċ Fuhito Kojima, Feb 10, 2010, 9:17 PM
Ċ Fuhito Kojima, Feb 15, 2010, 11:25 PM
Ċ Fuhito Kojima, Feb 26, 2010, 5:54 PM
Ċ Fuhito Kojima, Feb 15, 2010, 10:59 PM
Ċ Fuhito Kojima, Jan 25, 2010, 1:40 PM
Ċ Fuhito Kojima, Feb 26, 2010, 5:55 PM
Ċ Fuhito Kojima, Feb 26, 2010, 5:55 PM
Ċ Fuhito Kojima, Feb 26, 2010, 5:56 PM
Ċ Fuhito Kojima, Feb 27, 2010, 11:00 PM
Ċ Fuhito Kojima, Feb 26, 2010, 5:57 PM
Ċ Fuhito Kojima, Feb 26, 2010, 5:55 PM
Ċ Fuhito Kojima, Feb 26, 2010, 5:54 PM
Ċ Fuhito Kojima, Mar 3, 2010, 11:03 AM
Ċ Fuhito Kojima, Feb 26, 2010, 5:53 PM
Ċ Fuhito Kojima, Feb 15, 2010, 11:00 PM
Ċ Fuhito Kojima, Feb 9, 2010, 11:25 AM
Ċ Fuhito Kojima, Jan 26, 2010, 8:30 AM
