STAT 155: Game Theory (Spring 2007)
Instructor: Asaf Nachmias.
Email: a s a f n a c h @ m a t h
Office hours: Tue 3:30-4PM, Wed 2-3PM, Thu 3:30-4PM, 341 Evans.
Class time: Tuesday and Thursday, 2:00 - 3:30 (room 330, Evans Hall).
Announcements
- Here is the class picture from Tuesday afternoon (thanks Wanchen).
- On Thursday, May 10th, there will be additional office hours at 14-16.
- Final examination will cover all the material we talked about in class (not including your presentations, except for the ones we discussed later in class.
So Ramsey theory is not included, but Shapley value is). In particular the chapters we've covered are:
- Combinatorial games.
- Zero-Sum games.
- General sum games.
- Additional topics: Random turn selection games, Auction-turn games (Richman) and Shapley Value.
- Please note that a correction to Homework 12 was posted: in question #1, the graph G is connected (thanks Andy).
- Homework 12 has a formulation of Ramsey's Theorem that is relevant for bonus question 3 of Homework 11.
- See topics for presentations. Email me or come to office hours to choose a topic and schedule a time. Do that this week, before spring break so everyone will have time to speak!
- In tomorrow's class, Tuesday March 6th, we will have a review of the material for the upcoming midterm, solve the practice midterm and some other problems.
- Office hours for tomorrow, Wednesday February 21, are going to be held at 4-5 (instead of the usual 2-3) at 341 Evans.
- For the curious, here is the original paper: Non-Cooperative Games , John Nash, 1951.
- The midterm will be given on March 8th, 14-15:30. More details will follow.
- The electronic edition of Graph Theory by Reinhard Diestel is a great reference for all you ever wanted to know about graph theory.
- Homework 3 will count as bonus to your quiz score, up to half of the quiz weight.
- An in-class Quiz will be given on Tuesday, January 30th in the last half hour of class, 3-3:30. Any written material is allowed. What will be necessary is scrap paper and a working pen . The quiz's questions will be only about material we covered in the first two weeks of class. The way to study for the quiz is to make sure you understand all we did in class and all the homework for the first two weeks.
Do not stress!
- January 23rd: A correction was uploaded to homework assignment number 1, Question 2.
Homework
- Homework 1 , due January 25th.
- Homework 2 , due February 1st.
- Homework 3 , due February 8th.
- Homework 4 , due February 15th.
- Homework 5 , due February 22nd.
- Homework 6 , due March 1st. Practice midterm is a part of Homework 6.
- Homework 7 , due March 15th.
- Homework 8 , due March 22nd.
- Homework 9 , due April 12th.
- Homework 10 , due April 19th.
- Homework 11 , due May 1st.
- Bonus Homework 12 , due May 3rd.
Possible topics for presentations
- Moore's Nim_k (Taken)
- Coalitions and the Shapley Value (Taken)
- Keeping the weatherman honest (Taken)
- Secret Sharing (Taken)
- Cake cutting (Taken)
- Condorcet's paradox and Arrow's impossibility Theorem (Taken)
- Stable matchings (Taken)
- Additional topics in Game Theory can be obtained in gametheory.net
.
- Additional topics in Graph Theory.
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. 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 texts:
An excellent additional resource, where you can find other lecture notes and a glossary of game theory concepts, and
also play some games, is gametheory.net
More information about random turn selection games can be found here .
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%);
- Quiz (10%);
- Midterm (30%);
- Final Exam (45%);
- 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.
