News

Look here for announcements, e.g., classroom location!

Abstract

Classical and combinatorial game theory are quite different subjects, but both are fascinating, fun, and sometimes an occasion for deep mathematics. In classical game theory (cf. A Beautiful Mind), the players---usually two of them---move simultaneously and receive payoffs according to some prescribed matrix. Applications to economics, politics, and warfare abound; the central concepts are optimal strategies and equilibria. Random strategies are of great importance, even when the conditions are strictly deterministic.

Combinatorial game theory attempts to understand actual games in which two players make alternate moves, and positions are deterministic and transparent---as in chess, checkers, and go. In the basic theory, combinatorial games are won by the last player to make a legal move, but results often extend to scoring-type games like go. The theory will take us all the way from the mundane problem of beating your roommate at Dots and Boxes, to the bizarre world of surreal numbers.

Prerequisites: The mathematical sophistication of a beginning math graduate student or advanced undergraduate math math major, or the same for theory and algorithms in computer science. A basic acquaintance with probability, as encountered in MATH 20 or COSC 70, will be assumed; check with the instructor if you're not sure about whether your background is sufficient for this course. There will be daily (small) assignments, and in-class exams including a final. You will see some proofs in class and occasionally be asked to prove something not too complex. You will not be required to write computer programs, but doing so will sometimes provide an alternative way to do an assignment.

Here is a rough weekly syllabus:

1. Classical versus combinatorial: purpose, outcome range, move order, mathematical tools

2. Simultaneous games, payoff matrices, dominant strategies

3. Alternating move, impartial games; Grundy numbers

4. Normal-form games, Rock-Paper-Scissors, prisoners' dilemma

5. Partizan games, game values, infinitesimals

6. Mixed strategies, fixed-point theory, Nash equilibria

7. Abstract games and surreal numbers

8. Static vs. dynamic games; repeated games

9. Voting, auctions, mechanism design

Classes

Room: TBA
Lectures: 9L slot: Monday, Wednesday and Friday 8:50 - 9:55.
X-hour: Thursdays 9:05 - 9:55. Will be used only when so announced in class.

Staff

Instructor:

Prof. Pete Winkler -- Kemeny Hall 231
Office Hours: Tue 10-11, Wed 2-3, Thu 11-12. email: peter.winkler at dartmouth.edu

TA:

TBD
email:

Textbooks

Steven Tadelis, Game Theory: An Introduction, Princeton U. Press 2013.

Michael Albert, Richard Nowakowski, and David Wolfe, Lessons in Play, A K Peters, 2007.

Grading

Your grade will be based on homework, class participation (attendance is expected!), midterms, and a final exam.

Exams

There will be in-class exams on Monday, April 17 and Monday, May 8. Let your instructor know in advance if you antipate a conflict. The final exam will be held on the assigned day and time for "9L" slot classes.

Homework

Homework will be assigned at each class period, due on paper at the beginning of the next class. If you can't make it to class (e.g., on account of COVID quarantine), let the instructor know, and you will be able to email a PDF of your homework to the instructor and the TA. Late homeworks will be checked off but not graded.

Assignments

Due Wednesday March 29: Read the Introduction to each textbook.

Honor Code

Students are encouraged to work together to do homework problems. What is important is a student's eventual understanding of homework problems, and not how that is achieved. The honor principle applies to homework in the following way. What a student turns in as a written homework solution is to be his or her own understanding of how to do the problem. Students must state what sources they have consulted, with whom they have collaborated, and from whom they have received help. Students are discouraged from using solutions to problems that may be posted on the web, and as just stated, must reference them if they use them. The solutions you submit must be written by you alone. Any copying (electronic or otherwise) of another person's solutions, in whole or in part, is a violation of the Honor Code.

If you have any questions as to whether some action would be acceptable under the Academic Honor Code, please speak to me, and I will be glad to help clarify things. It is always easier to ask beforehand than to have trouble later!

Notification to Student re Recording

(1) Consent to recording of course meetings and office hours that are open to multiple students. By enrolling in this course, a) I affirm my understanding that the instructor may record meetings of this course and any associated meetings open to multiple students and the instructor, including but not limited to scheduled and ad hoc office hours and other consultations, within any digital platform, including those used to offer remote instruction for this course. b) I further affirm that the instructor owns the copyright to their instructional materials, of which these recordings constitute a part, and my distribution of any of these recordings in whole or in part to any person or entity other than other members of the class without prior written consent of the instructor may be subject to discipline by Dartmouth up to and including separation from Dartmouth. (2) Requirement of consent to one-on-one recordings: By enrolling in this course, I hereby affirm that I will not make a recording in any medium of any one-on-one meeting with the instructor or another member of the class or group of members of the class without obtaining the prior written consent of all those participating, and I understand that if I violate this prohibition, I will be subject to discipline by Dartmouth up to and including separation from Dartmouth, as well as any other civil or criminal penalties under applicable law. I understand that an exception to this consent applies to accommodations approved by SAS for a student's disability, and that one or more students in a class may record class lectures, discussions, lab sessions, and review sessions and take pictures of essential information, and/or be provided class notes for personal study use only.

If you have questions, please contact the Office of the Dean of the Faculty of Arts and Sciences.

Disabilities

I encourage any students with disabilities, including "invisible" disabilities such as chronic diseases and learning disabilities, to discuss appropriate accommodations that might help you with this class, either after class or during office hours. Dartmouth College has an active program to help students with disabilities, and I am happy to do whatever I can to help out, as appropriate.

The Student Disabilities Center is located at 318 Wilson Hall, ext. 6-9900, http://www.dartmouth.edu/~accessibility, if you have any questions. Any student with a documented disability requiring academic adjustments or accommodations is requested to speak with me by the end of the second week of the term. All discussions will remain confidential, although the Academic Skills Center may be consulted to verify the documentation of the disability and advise on an appropriate response to the need. It is important, however, that you talk to me soon, so that I can make whatever arrangements might be needed in a timely fashion.