Instructor | Graham Denham |
---|---|

Office hours | Tuesday 1:30-2:30, Thursday 2-3pm |

Class times | Tuesday 11:30-12:20; Thursday 10:30-12:20 |

Class location | MC 107 |

Textbook | library reserve |

Prerequisites | 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. |

Midterm exam date |
March 1, in class. |

Final exam | 15 April, 10am-1pm, SSC 3010. |

Evaluation | 40% Final exam; 35% midterm; 25% assignments |

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).

- 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

- 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.

**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.