Problem set 1 ps1.tex Solutions
Problem set 2 ps2.tex
COURE NOTES
Description:
Game theory is the theory of decision problems with multiple decision makers, often
with conflicting objectives. The theory seeks to describe the actions of decision
makers in various settings, and, in some cases, to aid in the design of incentives
to steer the collective actions towards specified objectives. The course focuses
on fundamental theory, with applications to a broad range of problems arising
in networks, such as resource allocation, incentives for investment, and pricing.
Grading scheme:
Homework (40%), two ninety minute midterms (20% each), project (20%).
Prerequisites:
Familiarity with dynamic systems (at the level of ECE 515), background in probability theory (at the level of ECE 313, and preferably ECE 534), familiarity with the basics of linear and
nonlinear programming (at the level of ECE 490).
Credit: 4 graduate hours
Assigned Reading:
There will be no required text, but there will be selected readings from
books, journal papers, and other information availalble online.
 T. Basar and G. J. Olsder, Dynamic Noncooperative Game Theory, Second Edition, SIAM
Classics in Applied Mathematics, 1999.
 N. CesaBianchi and G. Lugosi, Prediction, Learning, and Games, Cambridge University Press, 2006.
eBook for uiuc students: Click Course Reserves, indicate instructor and course
 D. Easley and J. Kleinberg,
Networks, Crowds, and Markets, Cambridge University Press, 2010.
 D. Fudenberg and J. Tirole, Game Theory, MIT Press, 1991.
 R. Gibbons, Game Theory for Applied Enconomists, Princeton University Press, 1992.
 V. Krishna, Auction
Theory, Associated Press, 2002.
 R.B. Myerson, Game theoryanalysis of conflict, Harvard University Press, Cambridge, MA,
1991.
 Prof. Ozdaglar's notes available online from MIT OpenCourseware

M.J. Osborne and A. Rubinstein, A course in game theory, MIT Press, Cambridge, MA, 1994.

Menache and A. Ozdaglar, Network Games: Theory, Models, and Dynamics,
Morgan and Claypool Publishers, 2010.
 T. Roughgarden,
"An Algorithmic Game Theory Primer" :Revised
Version of Survey in the IFP Conference of Theoretical Computer
Science, Sept. 2008.
 Shamma and Arslan, "Unified convergence proof of
continuous time fictitious play," IEEE Trans. Automatic Control , vol. 49, no. 7, pp. 11371142.

Y. Shoham and K LeytonBrown. Multiagent Systems: Algorithmic, GameTheoretic, and Logical Foundations. Cambridge University Press, 2008.
 List of games in game theory, Wikipedia
Meeting times:
9:3010:50 a.m. TuTh in 3015 ECE Building
Instructor:
Professor
Bruce Hajek
Teaching assistant:
Muhammed Sayin
Office hours:
BH: Wednesdays, 12pm, 105 CSL, MS: Mondays, 56pm, 101 CSL
Question and answer site:
Piazza
Tentative summary of topics:

I. Static games of complete information
 Dominant strategies, iterated elimination of dominated strategies, mixed strategies, Nash equilibrium, saddlepoint theory,
 Conditions for existence, and conditions for uniqueness, of Nash equilibrium
 Correlated equilibria
 Fictitious play and convergence results
 Evolutionarily stable strategies (ESS) and evolutionarily stable states of replicator dynamics
 Trembling hand equilibrium
 Blackwell's approachability theorem and learning
 II. Dynamic games of complete information
 Extensive form games with imperfect information: normal form, subgame perfect equilibrium, sequential equilibria
 Multistage games with observed actions: one step deviation principle
 Repeated games: trigger strategies, feasibility theorems (aka folk theorems)
 III. Static games of incomplete information
 IV. Mechanism design and the theory of auctions
 Vikrey second price auction and its generalization (VCG mechanism)
 Revenue optimal auctions (direct revelation principle, revenue equivalence, virtual valuations (Myerson theory)
 Equilbrium bidding strategies and revenue ordering for second price
and ascending auctions with correlated private information (Milgrom and Weber theory)
 V. Coalitions in cooperative games
 Core, exchange economies with transferrable payments, Shapley value
About the project:
For the project you are to choose a topic related to the course content and understand and critically evaluate
two or three major papers in that area. Then demonstrate knowledge of the papers by working an example
based on a paper or possibly extending the theory of a paper. You will need to write a project report of five
to ten pages in length, and prepare a fifteen minute presentation.
Additional policy:
Collaboration on the homework is permitted, however each student must write and submit independent solutions. Homework is due within the first 5 minutes of the class period on the due date. No late homework will be accepted (unless an extension is granted in advance by the instructor).
You may bring two sheets of notes to the first exam and three sheets of notes to the second exam. You may use both sides of the sheets, with font size 10 or larger printing
(or similar handwriting size). The examinations are closed book otherwise. Calculators, laptop computers, tables of integrals, etc. are not permitted.