**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:**

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 |