News

FINAL EXAM If you are on campus and wish to visit your final exam, come by my office (Kemeny 231) at 2 on June 20 or make an email appointment.

Review Session: By popular request, there will be an optional review session at X-hour, in our regular classroom, 9:05-9:55 Thursday morning 5/4. (And an office hour 11-12 in Kemeny 231.) Monday May 8 is our second of two hour exams in class.

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:

Jamie Schmidt
email: James.A.Schmidt.GR at dartmouth.edu

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: Find, if it's possible, a 2x2 matrix for a classical game in which Alice and Bob would each prefer to go first, if the game were not simultaneous. If it's not possible, why not?

Due Friday March 31: You are offered the chance to collect $x tax-free if the toss of a fair coin comes up "heads"; if it comes up tails you get nothing. Or, instead, you can have $y tax-free outright. Consider the following six cases: x = 10, x = 100, x = 1,000, x = 10,000, x = 100,000, x = 1,000,000. In each case, what value of y would make it the toughest possible decision for you?

Due Monday April 3: Your utility for owning $x is log x. (The base of the logarithm doesn't matter; for this problem I recommend the natural logarithm.) You have $a and are permitted to make one bet on the flip of a coin that comes up "heads" with probability p which is known to you and greater than 1/2. If you bet $b and win, you win $b; otherwise you lose the amount bet. What fraction of $a should you bet, to maximize your expected utility?

Due Wednesday April 5: Read Chapter 0 of Lessons in Play, and do Problem 1 at the end of the chapter.

Due Friday April 7: Provide two positions for DOMINEERING that belong to each of the four outcome classes for combinatorial games.

Due Monday April 10: Determine (with proof!) the N and P positions for SUBTRACTION, where the set of subtractibles is {3,4,5}.

Due Wednesday April 12: In WEIGHTED ODDS AND EVENS, Alice and Bob simultaneously put out one or two fingers. If they put out different numbers of fingers, Alice wins from Bob a number of dollars equal to the total number of fingers put out (namely, in this case, 3). If they put out the same number of fingers, Alice pays Bob $2 or $4 according to the total number of fingers played. (1) Find an equilibrium pair of randomized strategies. (2) What is the expected outcome if these strategies are employed?

Due Friday April 14: Before last basketball season, WNBA star Vera Similitude's lifetime free-throw percentage was below 80%. After the season, it was above 80%. Must there have been a moment in the season when it was exactly 80%? Justify your answer!

Due Wednesday April 19: Let "x" be the value of some particular immpartial game. Then, as we saw in class, x + x = 0, since, by symmetrizing, the sum of two copies of this game is in the class P whose value is 0. Since addition of games is commutative (and associative), the set of all possible values of impartial games should be an abelian group in which x + x = 0 for all elements x. Find an example of such a group, preferably one of countably infinite size.

Due Friday April 21: Suppose you are playing a sum of two games, one of which is just a single NIM stack of size 5. In the other game a move can produce a position of value *k for any k in a certain finite set K of nonnegative integers. What sets K result in this sum of games being in the outcome class P?

Due Monday April 24: Replace each of the first five letters of your official Dartmouth email address by its position in the alphabet (a number between 1 and 26), and consider the resulting 5-stack NIM position. Find all winning moves (if any) from that position, and email your results to Jamie (address above). Jamie's computer program will check your answer against the address you sent it from.

Due Wednesday April 26: Compute the value of 1xn CRAM for n = 7, 8, 9, 10. Or: Find the P-positions for the game of PANCAKES, in which there are two stacks of pancakes and you may eat from the larger stack any multiple of the number of pancakes in the smaller stack. Finishing a stack is illegal (owing to the soggy pancake at the bottom).

Due Friday April 28: State and prove the n-dimensional Sperner's Lemma, by induction on n. The 2-dimensional Sperner's Lemma states that if a triangle with vertices colored 1,2,3 is "triangulated" into smaller triangles, and vertices are colored 1, 2 or 3 with the stipulation that outside vertices (that is, vertices on an edge of the big triangle) can only get a color of one of the big edge's endpoints, then an odd number of cells (small triangles) get all the colors. (NOTE: tomorrow, Thursday April 27, office hour will be 1-2 instead of 11-12.)

Due Monday May 1: Find an equilibrium for Alice and Bob playing Rock, Paper, Scissors with the following amendment: If Alice crushes Bob's scissors with her rock, or Bob cuts Alice's paper with her scissors, it's treated as a double win for one (and a double loss for the other). Thus, the matrix for the game, with rows R,P,S for Alice and columns R.P.S for Bob, is ((0,0), (-1,1), (2,-2); (1,-1), (0,0), (-2,2); (-1,1), (1,-1), (0,0)). Also: read in Tadelis about proving that Nash equilibria exist.

Due Wednesday May 3: The convex closure cc(U) of a subset set U of Euclidean d-space is the intersection of all convex sets containing U. Show that cc(U) can also be described as the set of all points c_1 p_1 + c_2 p_2 + . . . + c_n p_n where n is any positive integer, each p_i is any point (i.e., d-tuple) of U, and the c_i's are arbitrary nonnegative reals that sum to 1.

Due Friday May 5: A $10 bill is auctioned to 10 people in the following way: Each person chooses a non-negative integer number of dollars to submit as a sealed bid. The $10 bill goes to a uniformly random person who was among the highest bidders, in return for the amount bid. Find and count all pure Nash equilibria for this game. (You may assume everyone's utility for money is linear in the range $0 to $10.)

Due Wednesday May 10: Alice and Bob comprise the only bidders in an all-pay auction in which the prize, $4, goes to the highest bidder. If the bids are equal the prize is split, with each party getting $2. No matter what happens, both players must pay their bids. Bids are whole numbers of dollars from $0 to $3, inclusive. Find a (pure or mixed) Nash equilibrium.

Due Friday May 12: Read 4.1 and 4.2 in Lessons in Play, Then, compute the game values of the 8 "stalks" BBB, BBR, etc. in Red-Blue Hackenbush (AKA LR-Hackenbush in the text).

Due Monday May 15: We proved in class that no position in LR HACKENBUSH (AKA BLUE-RED HACKENBUSH) can be in the outcome class N. The proof seems to work even if some edges are green, but something's wrong here, because there are N positions in general HACKENBUSH. (1) Where does our classroom proof go wrong when green edges are present? (2) Can you nonetheless extend our theorem to some situations when green edges are present?

Due Wednesday May 17: Do Problem 1, p. 83 of Lessons in Play. Note that in the text white = red, black = blue, gray = green (see top of p. 269).

Due Friday May 19: Take any partizan game G with blue and red pieces (e.g., CLOBBER) and create an equivalent game G' by having both players play the blue pieces, but the pieces switch colors after each move. Then G' is impartial, right? So how can it be equivalent to a partizan game, like the CLOBBER position with value "up" shown in class?

Due Monday May 15: Let S be a board of size 2n for a selection game in which, prior to each move, the next card is drawn from a well-shuffled deck of n blue cards and n red cards. The next move is then taken by Louise if the card is blue, Richard if red. The payoff to Louise is f(S₁), where f is a function from subsets of S of size n to the real numbers, and the payoff to Richard is -f(S₁), where S₁ is the set Louise ends up with. Show that the (expected) value to Louise of this game is the expected value of f(R), where R is a uniformly random subset of S of size n. References: for random turn games click here; for Knuth's Surreal Numbers, here.

Due Wednesday May 24: Two people participate in a sealed bid, first-price auction. Both players' valuations for the object being sold are uniformly random in [0,1]. Show that each player bidding half of his or her valuation is a Nash equilibrium.

Due Friday May 26: You have the opportunity to make one bid on a widget whose value to its owner is, as far as you know, uniformly random between $0 and $100. What you do know is that you are so much better at operating the widget than he is, that its value to you is 80% greater than its value to him. (Yes, you don't know your own valuation!) If you offer more than the widget is worth to the owner, he will sell it. But you only get one shot. How much should you bid?

Due Wednesday May 31: n people are iinvolved in a pivotal mechanism (see top half of page 299 in Tadelis) to decide where to locate a prison. Person i is just willing to pay $d_i to avoid having the prison in his town, where 0 < d₁ < d₂ < ... < d_n. The prison has to go somewhere. Where does it go, and what does each player earn or pay?

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.