**Course: Math 499, Game Theory, Spring 2025**

**Recommended Prerequisite:** 1 from [Math 407 or Math 307] and 1 from [Math 225 or Math 235].

**Course Content:** This course will present the mathematics of game theory, i.e. the quantitative modeling of strategic interaction. Topics include: impartial games, partisan games, zero sum games, von Neumann's Minimax Theorem, general sum games, Nash equilibrium, fixed point theorems, evolutionary game theory, signaling, coalitions, auctions, and social choice theory. Time permitting, we will cover quantum games, algorithmic game theory, and applications of game theory to neural networks, such as generative adversarial networks or Monte Carlo Tree Search. The target audience of this course is advanced undergraduate students in mathematics, economics, computer science, or related fields, with an interest in a mathematically focused course on game theory.

*Last update:* 10 October 2024

**Instructor:** Steven Heilman, stevenmheilman(@-symbol)gmail.com

**Office Hours:** Mondays, 10AM-12PM, KAP 406G

**Lecture Meeting Time/Location:** Mondays, Wednesdays, and Fridays, 12PM-1250PM, GFS 105

**Textbook: **The following textbook is recommended but **not required**.

Karlin and Peres, Game Theory, Alive.

Some other non-required textbooks: __Game Theory__, Maschler, Solan and Zamir. Compared to the book of Karlin-Peres, this book is larger and more comprehensive. However, it is also a more advanced textbook, so it might be difficult to read if you have not taken several advanced math classes. See also the A course in game theory book of Thomas S. Ferguson

**Exam 1**: Wednesday, February 19, 12PM-1250PM, GFS 105

**Exam 2**: Friday, March 28, 12PM-1250PM, GFS 105

**Final Exam**: Friday, May 9, 11AM-1PM, GFS 105

**Other Resources:** An introduction to mathematical arguments, Michael Hutchings, An Introduction to Proofs, How to Write Mathematical Arguments

**Email Policy:**

- My email address for this course is stevenmheilman@gmail.com
- It is your responsibility to make sure you are receiving emails from stevenmheilman@gmail.com , and they are not being sent to your spam folder.
- Do NOT email me with questions that can be answered from this syllabus.

**Extra Credit Project**: There will be an optional extra credit project, where students will create a computer program that plays a game (such as connect four or chess) in Python, and the top performers of a tournament will be awarded around 1% to 3% extra credit points for the course. The project would be due in the last week of class, and the ``finals'' of the tournament would occur in class during this time as well. Students can work in groups of up to three, and if a team wins some amount of extra credit, that credit will be split evenly among the participants. Also, copying any code from any online resource will result in automatic disqualification. Since I will be running the finals on a Microsoft Surface Tablet (without much memory or processing power), you should not use too many extra Python packages beyond some standard ones. More details are TBD.

**Exam Procedures**: Students must bring their USCID cards to the midterms and to the final exam. Phones must be turned off. Cheating on an exam results in a score of zero on that exam. Exams can be regraded at most 15 days after the date of the exam. This policy extends to homeworks as well. All students are expected to be familiar with the USC Student Conduct Code. (See also here.)

Accessibility Services: If you are registered with accessibility services, I would be happy to discuss this at the beginning of the course. Any student requesting accommodations based on a disability is required to register with Accessibility Services (OSAS) each semester. A letter of verification for approved accommodations can be obtained from OSAS. Please be sure the letter is delivered to me as early in the semester as possible. OSAS is located in 301 STU and is open 8:30am-5:00pm, Monday through Friday.

https://osas.usc.edu/

213-740-0776 (phone)

213-740-6948 (TDD only)

213-740-8216 (fax)

OSASFrontDesk@usc.edu

Discrimination, sexual assault, and harassment are not tolerated by the university. You are encouraged to report any incidents to the *Office of Equity and Diversity* http://equity.usc.edu/ or to the *Department of Public Safety* http://capsnet.usc.edu/department/department-public-safety/online-forms/contact-us. This is important for the safety whole USC community. Another member of the university community - such as a friend, classmate, advisor, or faculty member - can help initiate the report, or can initiate the report on behalf of another person. *The Center for Women and Men* http://www.usc.edu/student-affairs/cwm/ provides 24/7 confidential support, and the sexual assault resource center webpage sarc@usc.edu describes reporting options and other resources.

**Exam Resources:** Here are the exams and solutions I used when I last taught this class: Exam 1, Exam 1 Solution, Exam 2, Exam 2 Solution, Final, Final Solution, Exam 1, Exam 1 Solution, Exam 2, Exam 2 Solution, Final, Final Solution, Here is a page containing practice exams for another game theory class. Here is a page containing practice exams for another game theory class. Here is a page containing a practice midterm for another game theory class. Here is a page containing a practice final for another game theory class. Occasionally these exams will cover slightly different material than this class, or the material will be in a slightly different order.

**Homework Policy**:

- Homeworks are
**due at 11:59PM Thursdays**. - Homeworks are submitted in brightspace. To avoid internet issues, I recommend making your first submission of an assignment well in advance of the deadline.
- Homeworks should be submitted as single PDF documents. One way to create a PDF document from paper homework assignments is the freely available Adode Scan App
- Late homework is
**not accepted**. - If you still want to turn in your homework late, then the number of minutes late divided by ten will be deducted from the homework score. The exact deduction and rounding procedure is not guaranteed to be accurate.
- The
**two lowest**homework scores will be dropped. This policy is meant to account for illnesses, emergencies, dropped internet connections, etc. - You may not use the internet to try to find answers to homework problems.
- Do not submit homework via email.
- Collaboration on homeworks is allowed and encouraged.
- All homework assignments must be written by you, i.e. you cannot copy someone else`s solution verbatim.

**Grading Policy:**

- The final course grade is weighted as the larger of the following two schemes.
- Scheme 1: class participation (3%), homework (17%), the first midterm (20%), the second midterm (25%), and the final (35%).
- Scheme 2: class participation (3%), homework (17%), the largest midterm grade (30%), and the final (50%).

- If you cannot attend one of the exams, you must notify me within the first two weeks of the start of the quarter. Later requests for rescheduling will most likely be denied.
- Class participation is not the same as attendance. I will never explicitly take attendance, but I will notice if someone is frequently absent. Things that increase your class participation grade include: asking good questions, paying attention in class, showing up on time or early to class, etc. Things that decrease your class participation grade include: excessive talking or disruptions during class, frequent absences, excessive texting/smartphone usage in class, frequent tardiness, etc.
- You must take the final exam to pass the course.

**Tentative Schedule:** (This schedule may change slightly during the course.)

Week | Monday | Tu | Wednesday | Thursday | Friday |

1 | Jan 13: 1.1, Impartial Games | Jan 15: 1.1.1, 1.1.2, Chomp, Nim | Jan 16: Homework 0 due (ungraded) | Jan 17: 1.1.3, Sprague-Grundy Theorem | |

2 | Jan 20: No class | Jan 22: 1.2, Partisan Games | Jan 23: Homework 1 due | Jan 24: 1.2.1, Hex | |

3 | Jan 27: 2.1, Two-Person Zero Sum Games | Jan 29: 2.2, Minimax Theorem, Background | Jan 30: Homework 2 due | Jan 31: 2.2, Minimax Theorem | |

4 | Feb 3: 2.3, Domination | Feb 5: 3.1, General Sum Games | Feb 6: Homework 3 due | Feb 7: 3.2, Nash equilibria | |

5 | Feb 10: 3.3, Correlated equilibria | Feb 12: 3.6, Fixed Point Theorems | Feb 13: Homework 4 due | Feb 14: 3.5, Nash's Theorem | |

6 | Feb 17: No class | Feb 19: Midterm #1 | Feb 20: No homework due | Feb 21: 3.7, Evolutionary Game Theory | |

7 | Feb 24: 3.8, Signaling and Asymmetric Information | Feb 26: 4.1, Coalitions and Shapley Value | Feb 27: Homework 5 due | Feb 28: 5.1, Mechanism design | |

8 | Mar 3: 5.2, Auctions | Mar 5: 5.2, Auctions | Mar 6: Homework 6 due | Mar 7: 6.1, 6.2, Social Choice | |

9 | Mar 10: 6.3, Arrow's impossibility theorem | Mar 12: Influences, Fourier analysis | Mar 13: Homework 7 due | Mar 14: Noise Sensitivity | |

10 | Mar 17: No class | Mar 19: No class | Mar 21: No class | ||

11 | Mar 24: Quantum Games | Mar 26: CHSH inequality, Bell's inequality | Mar 27: No homework due | Mar 28: Midterm #2 | |

12 | Mar 31: Algorithmic Game Theory | Apr 2: Algorithmic Game Theory | Apr 3: Homework 8 due | Apr 4: Complexity of Nash Equilibria | |

13 | Apr 7: Complexity of Nash Equilibria | Apr 9: Complexity of Nash Equilibria | Apr 10: Homework 9 due | Apr 11: Price of Anarchy | |

14 | Apr 14: Bandits and Reinforcement Learning | Apr 16: Bandits and Reinforcement Learning | Apr 17: Homework 10 due | Apr 18: Monte Carlo Tree Search | |

15 | Apr 21: Monte Carlo Tree Search | Apr 23: Monte Carlo Tree Search | Apr 24: Homework 11 due | Apr 25: Leeway | |

16 | Apr 28: Leeway | Apr 30: Leeway | May 1: Homework 12 due | May 2: Review of Course |

**Advice on succeeding in a math class:**

- Review the relevant course material before you come to lecture. Consider reviewing course material a week or two before the semester starts.
- When reading mathematics, use a pencil and paper to sketch the calculations that are performed by the author.
- Come to class with questions, so you can get more out of the lecture. Also, finish your homework at least two days before it is due, to alleviate deadline stress.
- Write a rough draft and a separate final draft for your homework. This procedure will help you catch mistakes.
- If you are having difficulty with the material or a particular homework problem, review Polya's Problem Solving Strategies, and come to office hours.

**Supplementary Notes**