15-859 (21-801) Mathematical Games

General Information

This course will present a number of combinatorial games and puzzles, focusing on those for which there exist mathematical techniques for solving them. (See the list of topics below for more information.)

Class meetings are on Tuesday and Thursday from 1:30 to 2:50 in Wean 4615A. The instructors are Danny Sleator and Alan Frieze

There is a class mailing list that will be used sprodically. The address is sleator+games@cs.cmu.edu.

There is a blackboard site for this class, but it will be used only for recording of grades.

Grading

The grading for the class will be based on Homeowrks, a Midterm Exam, on a project, and on a final exam. Class participation is 15%, Homework is 30%, Midterm exam is 20% and the final/Project is 35%. Students have the option of doing a project, or taking the final exam, or both (only one will be counted toward your grade however). If you intend to do a project, you should submit a one-page project proposal describing the work you intend to do.

Important Dates

Midterm Exam: Due Thursday March 22nd in class
Project proposals due: Thursday March 24th
Final Exam: (We may not have a final)

Syllabus

Here are some topics that will probably be covered. Look for more details here later. Also see the web page for the previous incarnation of this course.

Jan 11, Jan 13, Jan 18, Jan 20
Read: Basic Combinatorial Games -- updated February 8 (ps)
Also read sections 1 through 5 of Ferguson Part I (below).
Topics: Combinatorial Games, Sums of Games, Nim, Geography, Tic Tac Toe and Extensions
Notes on take away games by Brian Thompson and Steven Kieffer
Jan 25, Jan 27: Welter's game, animating functions, etc. Chapter 13 from ONAG and 472-480 from Winning Ways
Feb 3, Theory of Combinatorial Games (Partizan games) notes
Feb 8, Shannon Switching Game (See Basic Notes above).
Feb 10, CG theory continued. Winning Ways Chapter 1 Winning Ways Chapter 2
Feb 15, Computer Analysis of Sprouts ps
Feb 17, Wythoff's Nim PDF
Feb 22, Green Hackenbush Notes of A. N. Walker
March 1-3, algorithms for permutation groups (Paper by Furst, et. al.)
March 15-17, Two person zero sum games
See Ferguson's chapter below, and Alan Frieze's zero-sum-games lecture notes
Alan Frieze's duality lecture notes
March 22, Bimatrix games, Nash Equilibria (see last two pages of zero-sum lecture notes above)
March 24, Midterm Exam discussion
March 29, Poker --- Andrew Gilpin (the talk was emailed to you)
March 31, April 5, Selfish Routing Roughgarden-Tardos paper Roughgarden Talk Frieze Slides
April 7, The Hex Theorem, 1st player wins Hex, Who Wins Misere Hex, Mudcrack Y, and the Mudcrack Y Theorem
April 12, Richman Games
April 14th
April 19th
April 21st Coin Weighing Problems: coins, coins2, coincompet.pdf, maacoins.pdf
------------------Not Covered----------------------------
More combinatorial game theory Winning Ways Chapter 3

Homeworks

Homework 1 Due January 20th in class.

Homework 2 Due February 4 in Wean 4128.

Homework 3 Due March 3 in class.

Midterm Exam

(pdf) (postscript)

The exam is due Tuesday March 22, 2005, in class Here are the instructions:

Do any four of the five problems. Please work alone. Please do not consult any material outside of that supplied in the class. Please feel free to contact the instructors for clarification.

Text Books

The following books have been put on reserve in the Engineering Library:

Winning Ways Volume 1 -- Games in General by Berlekamp, Conway, and Guy
Games of No Chance Edited by R. J. Nowakowski.
More Games of No Chance Edited by R. J. Nowakowski.
On Numbers and Games by John H. Conway
Mathematical Go, Chilling Gets the Last Point by Elwyn Berlekamp and David Wolfe

The following is the table of contents of Thomas Ferguson's on-line book on Game Theory. The entire text is available in PDF format in the links below.

Introduction
Part I: Impartial Combinatorial Games.
1. Take-Away Games.
2. The Game of Nim.
3. Graph Games.
4. Sums of Games.
5. Coin Turning Games.
6. Green Hackenbush.
Part II: Two-person Zero-Sum Games.
1. The Strategic Form of a Game.
2. Matrix Games. Domination.
3. The Principle of Indifference.
4. Solving Finite Games.
5. The Extensive Form of a Game.
6. Recursive and Stochastic Games.
Part III: Two-Person General-Sum Games.
1. Bimatrix Games. Nash Equilibrium.
2. The Noncooperative Theory. Safety Levels.
3. Models of Duopoly.
4. Cooperative Games.
Part IV: Games in Coalitional Form.
1. Many-Person TU Games.
2. Imputations and the Core.
3. The Shapley Value.
4. The Nucleolus.
Appendix.
1. Utility Theory.
2. Contraction Maps and Fixed Points.
3. Existence of Equilibria in Finite Games.