STAT 155: Game Theory
Fall 2013
Instructor: Antar Bandyopadhyay
(Email: antar (at) isid (dot) ac (dot) in
Office: Room # 387 Evans Hall).
Class Time:
Monday, Wednesday and Friday 13:00 - 14:00 hours in Class Room 60 Evans.
Instructor's Office Hours: Monday 10:00 - 12:00 hours in 387 Evans Hall.
Section Times:
Monday 16:00 - 17:00 hours and 17:00 - 18:00 hours in Class Room 334 Evans Hall.
GSI: Sujayam Saha
(E-mail: sujayam (at) stat (dot) berkeley (dot) edu Office : 345 Evans Hall).
GSI's Office Hours: Tuesday 13:00 - 15:00 hours and Friday 14:00 - 16:00 hours in 446 Evans Hall.
Course Duration: August 29 - December 6, 2013 (14 Weeks).
Note: Academic and Administrative Holidays: September 2, 2013 (Monday), November 11, 2013 (Monday)
and November 29, 2013 (Friday).
Midterm Examination: October 23, 2013 (Wednesday) Time: 13:00 - 14:00 hours in class.
Final Examination:
December 18, 2013 (Wednesday) Time: 19:00 - 22:00 hours.
Review before final: December 09, 2013 (Monday) Time: 16:00 - 18:00 hours in 213 Wheeler Hall.
Review will be done by Sujayam Saha, GSI.
Course Outline:
- Introduction and examples.
- Combinatorial games, impartial and partisan games, examples.
- Take-Away Games, examples of various take-away/subtraction games.
- The Game of Nim, Bouton's Theorem and proof. Various variants of Nim.
- Sums of Combinatorial Games, equivalence, Sprague-Grundy Function,
Sprague-Grundy Theorem and applications.
- Two-Person Zero-Sum Games, definitions and examples. Pure and mixed strategies.
von Neumann's Minimax Theorem.
- Matrix Games, Saddle Points, Nash Equilibrium. Solutions of 2 x 2 games.
- Simplifying and solving two-person zero-sum games, technique of domination, use of symmetry.
- Solution for 2 x 2 games. Solutions for 2 x n and m x 2 games.
- The Equilibrium Theorem and proof. Solution for games with non-singular payoff matrix.
- Solution for games with diagonal and triangular payoff matrix.
- Solving general m x n games. Pivot Method. Relation with linear programing.
- Two-Person General-Sum Games, examples. Nash equilibria.
- General-Sum Games with more than two players, examples.
- Pure and mixed Nash equilibria. Nash's Theorem for finite many players game.
- Application of Nash's Theorem: Game theoretic interpretation of the chromatic number of a finire graph.
- Voting and Ranking Mechanisms, Arrow's Impossibility Theorem, applications.
Lecture Schedule:
Note that this schedule may change as the semester progress. Right now it is only up to Midterm).
Main Text:
Other Resources:
- http://www.gametheory.net is an excellent resource,
where you can find other lecture notes and a
glossary of Game Theoretic concepts, and also can play some games!
Prerequisites: Theory of Probability (at the level of STAT 134), some basic real
analysis/calculus (at the level MATH 16A,B or MATH 104) and
linear algebra (at the level of MATH 54 or MATH 110).
Grading Policy:
- Homeworks: 20% of the total credit.
- Midterm Exam: 30% of the total credit.
- Final Exam: 50% of the total credit.
Homework Policies:
- There will be a total of 12 sets of weekly homework assignments, 6 prior and
6 after the midterm. Each carrying a total of 20 points. 10 best assignment scores
will be taken for the final grading.
- The assignments will be given in class on every Monday starting from September 9, 2013,
and it will be due on the Monday of the following week. Each assignment
set will be based on course materials covered in the (three) lectures in the previous week.
- Please submit your assignment to the GSI in your Section.
- Late submission of an assignment will NOT be accepted. If you
can not submit an assignment on time, don't worry about it, and try to do
well in the others. It will not count in your final grade since you
have two extra assignments anyway.
- Graded assignments will be returned by the GSI in the Section on
Monday following the due date.
- Click here
for downloading the assignments.
- Click here
for downloading the solutions of the assignments.
- Note there will be no assignment in the week of the midterm, that is, no assignment will
be given on Monday, October 21, 2013.
Midterm and Final Exam Policies:
- For both Midterm and Final Examinations you may bring a list of formulas, theorems with you and
your homework solutions, but no books, printed or photo copied materials
and/or hand-written, typed, of photo copied class notes will be allowed.
- No make up Final or Midterm will be given and no student may take the Midterm or Final earlier
than scheduled.
- Here is a practice midterm and its
solution.
- Here is a solution to the Midterm.
- Here is a set of practice problems for the final.
Regrading Policy:
- Regrading of homeworks or exams will only be undertaken in cases where you believe there has been a
genuine error or misunderstanding. Please note that our primary aim in grading is consistency,
so that all students are treated the same; for this reason, we will not adjust the score of one student
on an issue of partial credit unless the score allocated clearly deviates from the grading policy
we adopted for that problem.
- If you wish to request a regrading of a homework or exam, you must return it to the instructor or the
GSI with a written note on a separate piece of paper explaining the problem.
- The entire assignment may be regraded, so be sure to check the solutions to confirm that your overall
score will go up after regrading.
- All such requests must be received within one week from the date on which the homework or exam was made
available for return.
Last modified December 14, 2013.