Math 432, Fall 2017


Dr. Jim Haglund, jhaglund@math.upenn.edu
Course webpage: http://www.math.upenn.edu/~jhaglund/432/

Office hours: T 11:00-11:50am, R 10:00-10:50am in DRL 4E2B
Also, I have an office hour on Fridays from 9-9:45 am in the basement lobby area of ARCH.

Office Phone: 215-573-9093

Lecture: MWF 10-10:50am in DRL A4

Grader: Adam Clearwater, adamdav@math.upenn.edu
Office hours: M 3:30-4:30pm, R 11am-noon in DRL 3C13
Office Phone: 215-898-2949


Course: Game Theory is a relatively new and exciting field of mathematics which has applications to economics and many other areas. This course covers standard topics in game theory such as combinatorial games, two person (zero-sum and general-sum) games, noncooperative games, and Nash's equilibrium theorem. We will focus on the mathematics involved.

Text: The text for this course is " Game Theory" by Thomas S. Ferguson, available free online at his UCLA webpage. Some auxillary sources which may be helpful to consult, on reserve in the Math/Physics Library in DRL 3N1, are "Winning Ways for your Mathematical Plays" by Berlekamp, Conway, and Guy, and "A Course in Game Theory" by M. J. Osborne and A. Rubenstein.

Notes on Group Actions and Invariance


Exams and Grades: There will be three midterm exams and a final exam. Midterm exam 1 counts for 15% of your grade, while Midterm 2 and Midterm 3 each count for 20% of your grade. The final exam counts for 35% of your grade, while hw and quizzes together count for 10%. Midterm 1 will be on Wednesday, September 27, Midterm 2 on Wednesday, November 1, and Midterm 3 on Wednesday, Nov. 29. All three midterms are during our normal lecture time, from 10-10:50am in our normal lecture room - DRL A4. The final exam will be on Tuesday, Dec. 19 from 9:00-11:00am in ??.

Midterm 1: Covers all of Part I: Impartial Combinatorial Games. Games you may be asked to find winning moves for include Nim, Lasker's Nim, Moore's Nim_k, Misere Nim, Subtraction Games, Directed Graph Games, Kayles, Turtles, Twins, Mock Turtles, Ruler, Turning Corners, Tartan Games, Green Hackenbush, sums of games. SG functions for Kayles and Turning Corners will be provided, if they appear in a question. You should know the SG functions for Lasker's Nim and Mock Turtles. You may be asked to prove a given pattern for an SG function holds using induction. You may also be asked to explain parts of any of the proofs of theorems discussed in class, such as why in the sum of games G1 + G2, the SG-value of a position (x,y) equals the Nim sum of the SG-value of x in G1 and the SG-value of y in G2, the proof of the Colon Principle from Green Hackenbush, or proving something by induction. Midterm 1 is closed book; no notes, calculators, cell phones, etc. are allowed.

Important Dates


Sept. 4, Monday - Labor Day, No Class
Sept. 27, Wednesday - Midterm 1 - 10:00-10:50am in DRL A4
Oct. 6, Friday - No Class due to Fall Break
Oct. 9, Monday - Drop Period Ends
Nov. 1, Wednesday - Midterm 2 - 10:00-10:50am in DRL A4
Nov. 10, Friday - last day to withdraw from class
Nov. 23-26 Thanksgiving Break - No Class Nov. 24th
Nov. 29, Wednesday - Midterm 3 - 10:00-10:50am in DRL A4
Dec. 11, Monday - Last day of classes
Dec. 19, Tuesday - final exam from 9:00-11:00am in ???


Homework Assignments:



No late HW accepted except for Dean's excuse.

HW1 (due Friday, September 15, by end of lecture)

1. Consider the following game, as described in class. A warden tells seven prisoners that tomorrow they will be placed in a circle, and each given a randomly chosen black or white colored hat. Each prioner will be able to see the color of all the other prisoners' hats, but not their own hat. Each prisoner must then either guess the color of his/her hat (either black or white), or pass. If any prisoner guesses wrong, or if all prisoners pass, then the prisoners lose and are all returned to jail. Otherwise they win and are all set free. The prisoners will be required to all guess/pass simultaneously, and will not be able to communicate in any way after seeing the hats.
Number the prisoners 1,2,...,7 as you go around the circle. Let S be the following strategy: Each player complutes the Nim sum of all the numbers of the prisoners with black hats that he/she can see; if this is zero, he/she guesses black. If it equals his/her own number, he/she guesses white. Otherwise, he/she passes.
(a) Let V be the Nim sum of all the numbers of the prisoners who have black hats. Show that if V=0, using strategy S all prisoners guess wrong, while if V is not zero, all pass except one who guesses right.
(b) Show that the probability that V=0 is 1/8. Conclude that the probability that the prisoners win is 7/8.
(c) Can you think of a reason why a 7/8 probability of winning is the best possible?

2. For the Nim pile (13, 9, 2, 12), what moves are winning moves (i.e. go to a P position)? What if we are playing Moore's Nim with k=2?

3. Let G be the directed graph obtained by starting with the directed graph on page I-16 of the book (Figure 3.2), and reversing the direction of the four arrows which touch the vertex labelled a. Draw G and label all the vertices of G with their Sprague-Grundy values.

4. Prove Moore's Theorem (described on page I-13 in the book), which gives a description of the P-positions in Moore's Nim _k. That is, give a logical argument which shows that the P-positions are given by the rule described in Moore's Theorem.

5. Prove by induction that
1^3+2^3+ ...+ (n-1)^3 = n^2*(n-1)^2/4. For example,
1+8+27 = 16*9/4 = 36.

HW2 (due Friday, Oct. 13, by end of lecture)

1. Prove that if a matrix game A has a saddle point with value S, then S is unique (i.e., a matrix cannot have saddle points with two different values).

2. Solve the following games using the graphical method.

(a)

 5  0  3  -1
 1  2  -1  4


(b)

 3  0
 0  3
 2  1.5
 1  2


3. Solve the following games by any method.

(a)

 4  2
 1  3


(b)

 2  0  1  -1
 3  2  0  4
 2  1  1  2
 2  3  0  -1


(c)

 4  1  5
 3  2  1
 1  4  1


(d)

 1  2  3  4
 2  4  1  3
 3  1  4  2
 4  3  2  1


(e)

 0  1  -2
 -1  0  3
 2  -3  0