# Math 3157b -- Game Theory

Instructor Graham Denham Tuesday 1:30-2:30, Thursday 2-3pm Tuesday 11:30-12:20; Thursday 10:30-12:20 MC 107 library reserve Prerequisite(s): Mathematics 1600A/B, Calculus 1301A/B or Calculus 1501A/B, and one of Mathematics 1120A/B, Mathematics 2120A/B, Mathematics 2122A/B, Mathematics 2124A/B or Mathematics 2155F/G, the former Mathematics 2155A/B. March 1, in class. 15 April, 10am-1pm, SSC 3010. 40% Final exam; 35% midterm; 25% assignments

## Assignments

In order for a course in Game Theory to be of use to you outside of the classroom, you will need to get some practice.  Accordingly, there will be regular homework assignments.  This is the most important part of the course -- if you keep up on your homework, you will find that the exams are easy.

No late assignments are accepted for any reason; instead, your lowest homework score will not be counted.  See the homework page for assignments and solutions.  Please make sure you do your own work (see below).

## Syllabus

This is an introductory course in Game Theory, intended for 2nd or 3rd year undergraduate students.  More precisely, this course indicates how mathematical methods can be used to analyze various kinds of two-player games.  Some topics include:
• how to model games: extensive and strategic forms; perfect information; chance
• strategies: backwards induction; Nash equilibria
• Nim, and the theory of Nim-like games (combinatorial games)
• modelling imperfect information
• von Neumann-Morgenstern utility functions
• mixed strategies, and domination of strategies
• optimization: matching problems, convex hulls, and maximizing functions on convex polyhedra
• cooperative games

## Schedule

Here is a reminder of what we've been doing.
• 9, 11 Jan.: an introduction.  Perfect information, extensive and strategic forms of games. The value of a game.  Zermelo's algorithm for win-loss games.
• 23, 25 Jan.: backward induction in any strictly competitive game.  Nonconstructive arguments about the value of a game (Hex).  All about Nim.
• 30 Jan, 1 Feb.: Sprague-Grundy theory of impartial games.  Nim-equivalence.
• 6, 8 Feb: a quick review of probability theory: probability distributions on finite sets, expected value, and random variables.  Outcomes of games as lotteries (random variables).
• 13. 15 Feb: in a win-loss game with perfect information, it was easy to apply Zermelo's algorithm to compute the value of the game (which was a lottery), and we did some examples of this.  What made it work was the (reasonable) assumption that a player would always choose the option which maximized the probability of winning.
• 20, 22 Feb: reading week.  Midterm I covers material up to this point.
• 27 Feb: utility functions address what to do when the game has more than two possible outcomes.  A Von Neumann-Morgenstern utility function is one whose expected value rational players seek to maximize.  The problem of the St Petersburg lottery.
• (1 Mar.) Midterm
• 6 Mar.: how to construct Von Neumann-Morgenstern utility functions.  Using them to analyze games by Zermelo's algorithm.
• 8 Mar.: examples: Binmore's Russian Roulette.  The Kelly bet: how to optimize investment return if your utility function for money is logarithmic.
• 13, 15 Mar.: Nash equilibria.  Eliminating strongly and (maybe) weakly dominated strategies.  Binmore's Duel.  A quick introduction to convexity.
• 20 Mar.: the definition of mixed strategies.  Some $$2\times 2$$ games show these can be useful.
• 22 Mar.: zero-sum games with mixed strategies.  We define $$v_I=\max_{\mathbf x}\min_j (\mathbf x^TA)_j$$, where $$\mathbf x$$ runs over all mixed strategies for Player I, and the index $$j$$ over the columns of the matrix $$A$$.  Similarly, we defined $$v_{II}$$ and showed that, by general principles, $$v_I\leq v_{II}$$.
• 27 Mar.: In fact, it's always the case that $$v_I=v_{II}$$! For this, we proved the "supporting hyperplane" lemma and the Matrix Alternative.  Conclusion: zero-sum games given by just a strategic form always have a value, provided we allow mixed strategies.
• 29 Mar.: For $$2\times 2$$ games without saddle points, if the matrix is invertible, we can calculate the value and the (unique) equilibrium pair directly.  For games in which one player had only two strategies, more generally, a graphical analysis allowed us to compute the value and equilibrium mixed-strategy pairs, using the observation that mixed strategies are best responses only when the payoffs associated two two or more pure strategies are tied.
• 3 Apr.: For general-sum bimatrix games, we showed that there are always Nash equilibria (provided you take the Brouwer Fixed Point Theorem on faith.)
• 5 Apr.: Symmetric games have symmetric equilibria.  If $$A,A^T$$ is a symmetric bimatrix game, an evolutionarily stable strategy is a (mixed) strategy $$x$$ with the following property: for all $$y\neq x$$, there exists a number $$\delta$$ depending on $$y$$ for which, whenever $$0<t<\delta$$, we have $$x^TAz_t>y^TAz_t$$, where $$z_t=ty+(1-t)x$$.  We saw that, if $$x$$ is an evolutionarily stable strategy, then $$(x,x)$$ is a Nash equilibrium.
• 10 Apr.: a quick look at cooperative games.  We considered the payoffs that become available in a bimatrix game if the players enter a binding contract to play a strategy pair according to a probability distribution of their choice.   Cooperative payoff regions are convex sets in $${\mathbb R}^2$$, and Pareto-efficient outcomes lie on the boundary.  A simple model of cooperation amounts to a choice of a Pareto-efficient outcome.

## Further information

Academic dishonesty: Scholastic offences are taken seriously and students are directed to read the official policy

Accessibility Statement: Please contact the course instructor if you require material in an alternate format or if you require any other arrangements to make this course more accessible to you. You may also wish to contact Services for Students with Disabilities (SSD) at 661-2111 ext. 82147 for any specific question regarding an accommodation.

Support Services: Learning-skills counsellors at the Student Development Centre are ready to help you improve your learning skills. Students who are in emotional/mental distress should refer to Mental Health@Western for a complete list of options about how to obtain help. Additional student-run support services are offered by the USC. The website for Registrarial Services is http://www.registrar.uwo.ca.

Eligibility: You are responsible for ensuring that you have successfully completed all course prerequisites and that you have not taken an antirequisite course. Unless you have either the requisites for this course or written special permission from your Dean to enroll in it, you may be removed from this course and it will be deleted from your record. This decision may not be appealed. You will receive no adjustment to your fees in the event that you are dropped from a course for failing to have the necessary prerequisites.