Math 5750-3. Topics in Applied Mathematics: Game Theory. Spring 2016.

Alternative number: 6680-3. This is for PhD students. Course requirements are the same.

Time and place: 10:45--11:35 MWF in BU C 210.

Instructor: Stewart Ethier (Prof.), JWB 119, 581-6148, ethier@math.utah.edu. Office hours 2:00-2:50 MWF JWB 119.

Text: Game Theory, Second Edition, by Thomas Ferguson. Free download at http://www.math.ucla.edu/~tom/Game_Theory/Contents.html.

Prerequisite: Math 2270, Linear Algebra (or the equivalent).

Topics covered, if time permits: Impartial Combinatorial Games (Take-Away Games, The Game of Nim, Graph Games, Sums of Combinatorial Games), Two-Person Zero-Sum Games (The Strategic Form of a Game, Matrix Games, Domination, The Principle of Indifference, Solving Finite Games, The Extensive Form of a Game), Two-Person General-Sum Games (Bimatrix Games -- Safety Levels, Noncooperative Games -- Equilibria, Cooperative Games), and n-Person Games in Coalitional Form (Many-Person TU Games, Imputations and the Core, The Shapley Value).

Grades: Grades will be based on weekly homework assignments (20%), a midterm exam (25%), a term project (20%), and a final exam (35%). The midterm exam will occur during the 8th week of classes. The final exam will occur at the scheduled time, Wednesday, May 4, 10:30--12:30.

Assignments: Assignments on the week's material will be posted Fridays on this page. They will be due the following Friday (deadline is 2:50 pm at my office). Late assignments will not be accepted. (Do not use paper torn from a spiral notebook; staple pages together; reduced credit for illegible handwriting; extra credit for typed assignments.) Hard copies are preferred but electronic copies can be submitted in emergencies. Submit as pdf file, not as a Word doc.

Project: For the project there is some flexibility. It could be a report on an application of game theory or it could be an analysis of a game we didn't cover. It could be applied or theoretical. Grades will be based on how interesting it is and on how well you appear to understand it. Also important: It should be related to the course. For example, a study of blackjack would not be closely related because it is a one-person game. Any original contribution (such as a computation that hadn't been done previously) should be identified as such because it will enhance your score. It should be 5--10 pages (it is not a thesis). The project is due at last class period. Projects may be done individually or in a group of two. How should you find a topic? Do a literature search based on your interests. If you are on campus, you can use JSTOR (journal storage) or MathSciNet. The former is better because you can download the article, whereas the latter may be more complete but you may have to get the article from the library. Google Scholar may also be useful, and you don't have to be on campus. Important: If you use a published source, please submit an Internet link or a photocopy of it with your project. It is OK to use someone else's ideas as long as proper credit is given. And you can use someone else's words if they appear as properly attributed quotations. Example: The link below to Garrison Hansen's combinatorial games was created as a project for this class in 2011. It received the highest possible score.

Expected learning outcomes: The student who completes this course successfully will have a working knowledge of several areas of game theory, specifically Impartial Combinatorial Games, Two-Person Zero-Sum Games, Two-Person General-Sum Games, and n-Person Games in Coalitional Form. This knowledge should be sufficient to apply game theory to your own area of interest.

Some useful links:
Games you can play. Includes Chomp!, Fibonacci Nim, Moore's Nim, Dawson's Chess, Dots and Boxes, and Dominotion.
Garrison Hansen's combinatorial games. (A project for Math 5750, Spring 2011.)
Stuart Schulthies's games. (A project for Math 5750, Spring 2015.)
Matrix game solver (five decimal places).
Bimatrix game solver (12 decimal places, and exact; up to 15 x 15). This is excellent!

Week 1 (Jan. 11, 13, 15). Lecture 1, course overview. We finished Section 1 of Part I (Take away games). Assignment 1: page I-6, Exercises 2, 3, 4. If you want something more challenging, try Exercise 7, but do not turn it in.
Week 2 (Jan. 20, 22). We studied the game of Nim. Assignment 2: page I-11, Exercises 2, 3, 5.
Week 3 (Jan. 25, 27, 29). We proved the Sprague-Grundy theorem (Section 4 of Part I). Assignment 3: page I-19, Exercise 5; page I-26, Exercises 3, 5.
Week 4 (Feb. 1, 3, 5). We started Part II, covering Chapter 1. Assignment 4: page I-26, Exercise 6; page II-8, Exercises 2, 4. In Exercise 4, to avoid possible misinterpretation, note that the phrase, "I let you off with a payment of a dime," means that Olaf pays Alex 10 cents.
Week 5 (Feb. 8, 10, 12). We discussed the game of Le Her (not in our textbook), and we finished Section 2.2 of Part II. Assignment 5: page II-15, Exercises 2, 5, 6.
Week 6 (Feb. 17, 19). We covered the Indifference Principle. The game of baccara chemin de fer was briefly discussed. See baccara for more info. (There is a typo in Table 5.5, namely the two columns are reversed but the column headings are correct.) Complete solutions of all problems in the book are now available at http://www.math.ucla.edu/~tom/Game_Theory/Contents.html. Therefore, we will not assign problems from the book from now on. Assignment 6: click here.
Week 7 (Feb. 22, 24, 26). We finished Chapter 3 of Part II, omitting Section 3.6. Midterm exam next week on what we have covered so far. Assignment 7: click here.
Week 8 (Feb. 29, Mar. 2, 4). We proved the Minimax Theorem and had the midterm exam. Solutions. No new assignment this week.
Week 9 (Mar. 7, 9, 11). We studied the extensive form of a game (Part II, Chapter 5). Assignment 8: click here.
Week 10 (Mar. 21, 23, 25). We began Part III, getting through the definition of Nash equilibrium. Assignment 9: click here.
Week 11 (Mar. 28, 30, Apr. 1). We finished Part III, Chapter 2 (noncooperative games), and began Part III, Chapter 4 (cooperative games), skipping applications to economics. Assignment 10: click here.
Week 12 (Apr. 4, 6, 8). We finished Part III, Chapter 4 (cooperative games). A graph used in class for the example in eq. (11) on page III-36 is here. Assignment 11: click here.
Week 13 (Apr. 11, 13, 15). We covered Part IV (games in coalitional form) through Chapter 2 (Imputations and the Core). Assignment 12 (last one): click here. Note: For Exercise 3, you will need concepts from Chapter 3 (Shapley Value), to be covered Monday, Apr. 18.
Week 14 (Apr. 18, 20, 22). We covered Part IV, Chapter 3 (Shapley value).
Week 15 (Apr. 25). Review.

Final exam is scheduled for Wednesday, May 4, at 10:30. Old exam. Solutions. You may bring one sheet of prepared notes to use during the final exam.

Final exam. Solutions.

Notes on final exam: The median score was 79. There were 3 100s (GA, MD, WS) and 2 99s (HK, TM). (Congratulations!) Problem 4 was interpreted as asking for all PNEs and at least one NE that is not a PNE. (There is more than one.)