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 9-10 ,
Lecture 11-13 ,
Lecture 14-15 ,
Lecture 16-17 ,
Lecture 18-19 ,
Lecture 20-22 ,
Lecture 23-25 ,
Lecture 26-28 ,
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 ,
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.
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, 9-15.
An excellent resource, where you can find other lecture notes
and a glossary of game theory concepts,
and also play some games, is
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.
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.