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:

• Game Theory by Thomas S. Ferguson.
• Game Theory, Alive by Anna R. Karlin and Yuval Peres.

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.