Math 432, Fall 2017


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


Office Phone: 215-573-9093

Office hours: (week of Dec. 4 only): T 11:00-11:50am in DRL 4E2B, R 10:00-10:50am in DRL 4E2B, and Friday from 9-9:45 am in the basement lobby area of ARCH.

Office hours: (week of Dec. 18 only): M 10:30-noon in DRL 4E2B.

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.

Midterm 2: Covers pages 1-57 (Sections 1 through 5) of Part II: Two-Person Zero-Sum Games. Topics include Strategic form of Games, Matrix Games: Saddle Points, Domination, Solving 2 by n and m by 2 games, Latin square games, Principle of Indifference, Nonsingular matrix games, Diagonal games and other special matrix games, Invariance, Simplex method (also known as the pivot method). Ficticious play. Extensive form of a game. Things you may need to prove: anything on page 2 of the handout above titled "Notes on Group Actions and Invariance". Midterm 2 is closed book; no notes, calculators, cell phones, etc. are allowed.

Midterm 2 Solutions




Midterm 3: Covers all of Part III: Two-person general sum games. Topics include General-Sum Strategic and Extensive form games, Safety levels, PSE's and SE's, Models of Monopoly and Dupoly (Cournot, Bertrand, Stackelberg), TU cooperative game solutions, Nash axioms and Nash solution of NTU games, All-in Player poker. You will not be asked to prove things on Midterm 3, although you may be asked to derive solutions using the methods in class and in the book, and you will have to show your work. Midterm 3 is closed book; no notes, calculators, cell phones, etc. are allowed.

Final Exam Tuesday, Dec. 19 from 9:00-11:00am in DRL A6. Alternate seating. The final exam is cummulative. It Covers all of Part I, all of Part II up to and including section 5.9, all of Part III, and all of Part IV except for sections 3.2 and 4.3. The notes on Group Actions and Invariance will not be part of the final exam. The only proofs you need to know involve mathematical induction. You will be provided with a copy of the table in the book on Nim multiplication used in solving Tartan games. You will also be provided with the Sprague-Grundy (SG) values for any individual games from Part I you are asked about, although you may be asked to prove the formulas for the SG values. The final exam does not include anything on fictitious play.

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 DRL A6. Students should sit in every other seat (alternate seating).


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


HW3 (due Wednesday, Nov. 29 by end of lecture)

1. Use induction to prove the claim in the book on pages III-17 and III-18 (as in Figure 3.1, as discussed in lecture), that by iteratively removing dominated strategies you converge to the SE for q1 and q2 of (a-c)/3.

2. Consider the Cournot monopoly model with price function
P(Q) = Q*Q/3-(15/2)Q+50   if   0<= Q <= 10,
and
P(Q)=25/3   if   Q>= 10,
where Q*Q stands for "Q squared", <= stands for "less than or equal to", and >= stands for "greater than or equal to". Assume the cost, c, of producing one item is c=9. The firm would not produce more than 10 items since they would then start losing money. Thus we may restrict the production q to the interval [0,10].
Find the monopoly production, and the optimal monopoly return.

3. Do part (b) of problem 5 from Section III 3.5, but where Player I's cost of producing x items is x+3, and II's cost of producing y is 2y+1.

4. Do problem III 4.5.4, with the function y<= 4-x*x replaced by y<= 7-x*x (but everything else the same).

5. Do problem III 4.5.5 (b), with the entry (1,0) in row1, column1 of the matrix replaced by (2,0) (but everything else the same).

6. (Challenge problem) Let A,B be m by n matrices. Prove or disprove the following statement:
(sigma + Val(A-B) )/2 is greater than or equal to Val (A), where as in the book,
sigma = max a[i,j]+b[i,j].