STAT 155: Game Theory (Fall 2005)
Instructor Yuval Peres, 341 Evans Hall.
Class time Tuesday and Thursday, 2:00  3:30
(room 330, Evans Hall).
Lecture notes updated Fall 2005
All lectures ,
Lecture notes From Fall 2004
Lecture 1 ,
Lecture 2 ,
Lecture 3 ,
Lectures 4,5,6 ,
Lectures 7,8 ,
Lecture 910 ,
Lecture 1113 ,
Lecture 1415 ,
Lecture 1617 ,
Lecture 1819 ,
Lecture 2022 ,
Lecture 2325 ,
Lecture 2628 ,
Lecture 29 ,
Lecture 30 ,
Homework due Sep. 20 ,
Homework due Sep. 27 ,
Homework due Oct 6 ,
Homework due Oct 11 ,
Homework due Oct 18 ,
Practice midterm due Oct 18 ,
Homework due Nov 3 ,
Homework due Nov 10 ,
Homework due Nov 17 ,
Homework due Nov 24 ,
Homework due Dec 6 ,
Course description
Game theory is a fascinating subject, which sheds light on diverse
topics including economics, statistical decision theory, voting
and even evolutionary biology. We will first study
combinatorial games and zero sum games for which there is a satisfying
general theory, and continue with more general games where
the key notion is Nash equilibrium, and the problem of deciding
between Nash equilibria is a topic of active research. To gain a
feeling for the
strategies involved, we will try some of the games in class.
Additional topics: 1. The notion of Shapley value helps
identify the power of an agent when multiple coalitions are possible.
2. We will compare voting systems such as simple majority vote versus the
electoral college. 3. We'll consider hide and seek games related to
the assigment problem. 4. Well known games like hex or chess change
dramatically when instead of alternating moves,
a coin is tossed at each turn to decide who moves.
5. We will discuss Arrow's impossibility theorem for a "rational"
scheme of jointly deciding between more
than two options.
We will also explore some of the beautiful mathematical tools
that give game theory its power:
von Neumann's minimax theorem will be established
using supporting hyperplanes for convex sets; we'll prove
the existence of Nash equilibria via the Brouwer fixed point theorem,
following Nash's original argument.
Text
We will use the online
Game Theory Text
by Thomas S. Ferguson.
Another useful text is the book
"Game theory", 3rd ed. by Guillermo Owen, academic Press (1995).
The book "Game theory evolving" by H. Gintis,
has many lovely problems and insights.
For one special topic, we will refer to
D. Gale and L. S. Shapley (1962), College Admissions and the
Stability of Marriage, American Mathematics Monthly 69, 915.
An excellent resource, where you can find other lecture notes
and a glossary of game theory concepts,
and also play some games, is
gametheory.net
Prerequisite
Undergraduate courses in linear algebra and probability.
If you can solve linear equations and know what is the expectation of
a random variable, you're in.
Grading
Students taking the course for credit will be graded based on
 Weekly homework problems (15%);
 Midterm (35%);
 Final Exam (50%);

 In addition, up to 10 bonus points can be obtained for
making a 15 minute presentation of an advanced topic.
Each student will be graded based on his/her performance, rather than
on how it compares to the work of other students.
Hence collaboration in studying, and thinking about homeworks, is
encouraged and expected.