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 ,

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, 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 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