Math 5750-2. Topics in Applied Mathematics: Game Theory. Spring 2011.

Time and place: 2:00--2:50 MWF in LCB 215.

Instructor: Stewart Ethier (Prof.), JWB 119, 581-6148, ethier@math.utah.edu. Office hours 12:55-1:45 MWF.

Text: Game Theory by Thomas Ferguson. Available free at http://www.math.ucla.edu/~tom/Game_Theory/Contents.html.

Prerequisite: Math 2270, Linear Algebra.

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, Models of Duopoly, Cooperative Games), and Games in Coalitional Form (Many-Person TU Games, Imputations and the Core, The Shapley Value, The Nucleolus).

Grades: Grades will be based on weekly homework assignments (20%), a midterm exam (25%), a term project (20%), and a final exam (35%). The final exam is scheduled for Friday, April 29, 1:00--3:00.

Assignments: Assignments on the week's material will be posted Fridays on this page. They will be due the following Friday. Because homework will be graded by a grader, 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.)

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. It should not exceed 10 pages (it is not a thesis). The project is due April 22. 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'll 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 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.

Some useful links:
Games you can play. Includes Chomp!, Fibonacci Nim, Moore's Nim, Dawson's Chess, Dots and Boxes, and Dominotion.
Martin Chlond's games, including Nim.
Garrison Hansen's combinatorial games. (A project for Math 5750, Spring 2011.)
Matrix game solver (five decimal places).
Bimatrix game solver (four decimal places, and exact).

Week 1 (Jan. 10, 12, 14). We gave an overview of the subject and covered Chapter 1 of Part I (Take-Away Games). Assignment for next week: page I-6, Exercises 2, 3, 4.
Week 2 (Jan. 19, 21). We studied Nim (Chapter 2 of Part I) and started graph games. Assignment for next week: page I-11, Exercises 2, 3, 5.
Week 3 (Jan. 24, 26, 28). We nearly covered through Section I-4.2, omitting Section 3.4. Assignment for next week: page I-19, Exercise 5, and page I-26, Exercises 1, 2, 3.
Week 4 (Jan. 31, Feb. 2, 4). We finished Chapter 4 of Part I and began Part II, finishing Chapter 1. We also studied the game of le her. Assignment for next week: page I-26, Exercises 5, 10; page II-7, Exercise 4. In the last exercise, 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. 7, 9, 11). We finished Section 2.4 of Part II. We also studied the game of chemin de fer. Assignment for next week: page II-14, Exercises 4, 5, 7.
Week 6 (Feb. 14, 16, 18). We finished Section II.3.1. Assignment for next week: page II-15, Exercises 9, 11; page II-29, Exercise 1.
Week 7 (Feb. 23, 25). We covered Chapter 3 of Part II through symmetric games (Section 3.5). Assignment for next week: page II-29, Exercises 2, 3, 6. And prepare for midterm exam on the material we have covered through Part II, Section 3.2 only.
Week 8 (Feb. 28, Mar. 2, 4). We finished Chapter 3 of Part II (Indifference Principle), omitting Section 3.6 (invariance), and we proved the minimax theorem using linear algebra instead of linear programming. We also had a midterm exam. midterm exam with solutions. Assignment for next week: page II-29, Exercises 8, 9, 11. (Show your method, i.e., don't just use the online game solver.)
Week 9 (Mar. 7, 9, 11). We finished Part II, Chapter 5 (extensive form). Assignment for next week: page II-55, Exercises 3, 5, 6. (Sorry for posting this late.)
Week 10 (Mar. 14, 16, 18). We started Part III, Chapter 2 (noncooperative games). Assignment for next week (Apr. 1): page III-6, Exercises 1, 2, 3.
Week 11 (Mar. 28, 30, Apr. 1). We covered through Part III, Section 3.1 (Cournot's model). We will begin cooperative games next. Assignment for next week: page III-13, Exercises 3, 4, 6.
Week 12 (Apr. 4, 6, 8). We began Part III, Section 4.3 (NTU games), getting to Nash's theorem on page III-32. Assignment for next week: page III-39, Exercises 1, 2*, 3. *There are two problems labeled 2, and it is the second 2 that is intended.
Week 13 (Apr. 11, 13, 15). We finished Part III and began Part IV. Last assignment, due Apr. 25 (so as not to conflict with your project, due Apr. 22): page III-39, Exercises 4, 5, 6.
Week 14 (Apr. 18, 20, 22). We finished Chapter 2 (Imputations and the Core) of Part IV. Assignment for next week: prepare for final exam.
Week 15 (Apr. 25, 27). We finished Chapter 3 (Shapley Value) of Part IV.

Final Exam scheduled for Friday, April 29, 1:00--3:00. You may bring one crib sheet to the exam (8.5 x 11). You may not use (and will not need) a calculator or other electronic devices. Practice Final Exam. Solutions.

Final grades have been posted. Distribution: A (6), A- (4), B+ (3), B (10), B- (3), C (3), C- (1), D (2). Total (32). Congratulations to Nathan Barnes and Dennis Steorts for perfect scores on the final exam.