Statistics 155. Game Theory.

TTh 12:30p-2:00p in Stanley 106.

GENERAL INFORMATION. (## = berkeley dot edu)
Please include "STAT155" and your SID in the subject line of all emails.
Instructor: Nike Sun (nikesun at ##).
Office hours Thu 2:15p-4:15p in Evans 443.
GSI: Soumendu Mukherjee (soumendu at ##).
Office hours Mon 3:00p-4:30p and Fri 2:30p-4:00p in Evans 444.
Discussion sections Wed 11:00a-12:00n and 12:00n-1:00p in Evans 340.

Some materials, including homework assignments, will be posted to bcourses. If you cannot access the site, email the instructor with your @berkeley.edu address.

PREREQUISITES. To take this course you should have some background in single-variable calculus, matrix algebra, and probability theory (ideally Statistics 134).

REFERENCES.
(KP) Game Theory, Alive by A. Karlin and Y. Peres, available online.
(F) Game Theory by T. S. Ferguson, available online.

HOMEWORK. Please be considerate of the grader: write solutions neatly, and staple.
At the top of the first page, write clearly the following information: your name, student ID number, Berkeley email address, the course name (STAT155), and the names of any other students with whom you discussed the assignment. Please also indicate if you are currently waitlisted.
Collaboration policy. You should first attempt to solve homework problems on your own. If you are having trouble, you may discuss with others. You are expected to write down your solutions alone.

TESTS. All tests will be closed book and closed notes. No calculators or other devices.
Midterm 1: Thursday September 28, in lecture time slot.
Midterm 2: Thursday November 9, in lecture time slot.
Final: Thursday December 14, 3:00-6:00, Hearst Mining 390.

GRADING. Your final grade will consist of
20% homework + 20% midterm 1 + 20% midterm 2 + 40% final.
No late homework will be accepted. Lowest two homework scores will be dropped.
No rescheduling (early/late/repeat) for any exams. Missing the final will automatically result in an F grade. All students will be graded under the same scheme, regardless of late enrollment.

SCHEDULE. KP = Karlin & Peres, F = Ferguson (see above for links).

• Lecture 1 (08/24) impartial combinatorial games: subtraction. KP 1.1.
• Lecture 2 (08/29) impartial combinatorial games: Chomp and Nim. KP 1.1.
  Homework 1 posted, due 09/06.
• Lecture 3 (08/31) impartial/partisan combinatorial games: Nim/Rims; recursive majority. KP 1.2.
• Lecture 4 (09/05) introduction to zero-sum games; statement of minimax theorem. KP 2.1-2.3.
• Lecture 5 (09/07) zero-sum games; (pure/mixed) Nash equilibria; equalizing payoffs; separating hyperplane theorem. KP 2.4.1, 2.6.
• Lecture 6 (09/12) proof of von Neumann's minimax theorem via separating hyperplanes. KP 2.6. Homework 2 posted, due 09/20.
• Lecture 7 (09/14) principle of indifference (also called principle of equalizing payoffs or complementary slackness). KP 2.4.2, Proposition 2.5.3.
• Lecture 8 (09/19) domination and indifference; plus one game. KP 2.4.3.
• Lecture 9 (09/21) review of zero-sum games. KP Exercise 2.3.
• Lecture 10 (09/26) review of combinatorial games; Sprague--Grundy theorem. F I.3, I.4.
• Midterm 1 (09/28) covering KP Chapters and 2.
• Lecture 11 (10/03) two-player general-sum games. KP 4.1-4.2.
  Homework 3 posted, due 10/11.
• Lecture 12 (10/05) multi-player general-sum games. KP 4.3.
• Lecture 13 (10/10) congestion games, potential games. KP 4.4.
  Homework 4 posted, due 10/19.
• Lecture 14 (10/12) consensus game (asynchronous updates versus parallel updates), graph coloring game. KP 4.4.
• Lecture 15 (10/17) competitive pricing game; evolutionarily stable equilibria (ESS). KP 4.5, 7.1.
• Lecture 16 (10/19) ESS and ESMS (evolutionary stability against mixed strategies) in k-player games. KP 7.1.
• Lecture 17 (10/24) ESS in k-player games (polluting factories example); introduction to correlated strategies. KP 7.1-7.2.
• Lecture 18 (10/26) correlated strategies and correlated equilibrium (CE). KP 7.2.
  Homework 5 posted, due 11/02.
• Lecture 19 (10/31) traffic congestion games (with infinitesimal drivers), Braess paradox, price of anarchy (POA). KP 8.1.
• Lecture 20 (11/02) traffic games with linear latencies (POA equals 1), traffic games with affine latencies (POA is at most 4/3); Braess paradox and POA. KP 8.1.
• Lecture 21 (11/07) (lecture given by Soumendu) POA under more general latencies. KP 8.1.
  Homework 6 posted, due 11/16.
• Lecture 22 (11/14) cooperative games: transferable utility (TU) vs nontransferable utility (NTU); solution of 2-player TU cooperative games via threat strategies. F III.4.1-III.4.2.
• Lecture 23 (11/16) n-player TU cooperative games, as specified by characteristic functions: Gilles core; Shapley value and Shapley random arrival formula. KP 12.1-12.3.
• Lecture 24 (11/21) introduction to auctions: allocation, payment, utility, Bayes--Nash equilibrium (BNE). Examples: first-price and second-price auctions. KP 14.1-14.3.
  Homework 7 posted, due 11/29.
• Lecture 25 (11/28) auctions: general approach to finding symmetric BNE; revenue equivalence theorem. KP 14.4.
• Lecture 26 (11/30) review 1.
  Homework 8 (last homework) posted, due 12/06.
• Lecture 27 (12/05) review 2 (last lecture).
• The final exam is on Thursday December 14, 3:00-6:00, Hearst Mining Building Room 390 (registrar).