Lecture Notes by Anthony Zhang.

CO456

Game theory.

Gabriel Gauther-Shalom
Section 001
Email: g3gauthiershalom@uwaterloo.ca
Office Hours: Tuesdays/Wednesdays/Fridays 1:15pm-2:15pm in MC 6017
TA Office Hours: Matt Buckley, MC 5462 on Thursdays 5pm-6pm, Justin Toth, MC5-23B on Thursdays 3:30pm-4:30pm
Mondays/Wednesdays/Fridays 11:30pm-12:20pm

8/9/17

Course info available on LEARN.

A game consists of a set of rational agents that are trying to maximize their own payoff, within a certain set of constraints. For example, tic-tac-toe, chess, bargaining, prisoner's dilemma.

In this course we'll study games where players make decisions, which determine the payoff for each player.

Combinatorial Games

A combinatorial game is one that is deterministic - the outcome is determined entirely by the players' decisions. For example, tic-tac-toe or chess.

We study these by just looking at the set of all possible games, usually by looking at the game tree (a tree where vertices represent game states, the root vertex is the initial state, and edges represent transitions to possible next states, leaf nodes represent termination states).

As it turns out, the root node will be marked with outcome "draw" - tic-tac-toe will always end in a draw if players play optimally. For games like tic-tax-toe, we can actually do this by hand with a few shortcuts - for example, we can flip the board vertically/horizontally, or rotate it 90, 180, or 270 degrees without changing the outcome, which significantly reduces our search space.

We could do the same thing for chess, which is also a combinatorial game, but it would be totally infeasible to do this game tree analysis in real life. It's even infeasible with the rest of the tools we'll look at in this course.

For chess, the board state isn't the entire game state, unlike for tic-tac-toe. For example, the history of moves determines whether castling is possible, and how many times moves have been repeated (chess terminates if moves are repeated 3 times, to prevent loops).

Consider the game Nim, in which there are 3 piles of tokens or sizes 2, 4, and 5, and two players. Players take turns choosing a pile and removing any number of tokens from it, with the goal of removing the last token.

Just like how we can exploit symmetry in tic-tac-toe, we can also simplify our game tree. It's feasible to draw out the game tree, bit it's not really practical. Instead, players usually exploit the mathematical structure of the game - using a strategy.

A strategic game is similar . For example, the prisoner's dilemma - two players make independent decisions about whether to confess (defect) or stay quiet (cooperate), and the combination of those two decisions determines the outcome of both players. If both players stay quiet, they both get 2 years in prison. If both players confess, they both get 3 years. Otherwise, the one who confesses gets 0 years and the who doesn't gets 5 years. A rational player wants to minimize their prison time, but knows that the other player is also trying to minimize their own. We consider "years in prison" as a negative payoff.

Let's look at the possibilities. If player 1 confesses, player 2 should confess as well to minimise their prison time to 3 years. If player 1 doesn't confess, player 2 should still confess, to minimize their prison time to 0 years. Rationally, confessing is the dominating strategy - regardless of the other player's actions, it's always optimal to confess.

11/9/17

Midterm potentially on November 3, 2:30pm-4pm.

Assignment 1 due September 21 at 3:30 in MC6017. New assignments semi-weekly.

Formally, a combinatorial game is one in which two players make moves in alternation, there's no element of chance, the game is finite (guaranteed to terminate in finite steps containing finite numbers of moves), and there's perfect information (no hidden information). The outcome of a game typically results in a winner and a loser, or a draw.

In a combinatorial game, a winning position for a player is a state in which the player has a move that puts the other player in a losing position, and a losing position for a player is a state in which all moves put the other player in a winning position, assuming they're both playing to win. Note that the winning position only requires one move to satisfy the criteria, while a losing position requires every move to.

Consider the tic-tac-toe example. If at a certain vertex v, every leaf node that is a child of v is a winning state for X, then v is a winning position for X and a losing position for O. Starting from the leaf nodes and working our way up, we can mark every vertex as either "X wins", "O wins", or "draw", representing what the final outcome will be if both players play optimally - if they do the best move available to them for any given starting state. Of course, actually doing this is impractical for larger games.

Impartial games are combinatorial games where there are no draws, each move leads to an option that is also an impartial game, the set of possible moves doesn't depend on who the current player is, and each option results in a simpler game (the game tree is smaller - we can't get back to the current state from our new state). In normal play, a player loses when there are no moves possible, and in misere play, a player wins when there are no moves possible. Chess is not impartial because possible moves depend on the current player, while Nim is impartial because it satisfies all of these conditions.

The Algebra of Impartial Games

It is often useful to determine whether two games are "the same". One way to define game equivalence is to say "two games are equivalent if their game trees are isomorphic" (e.g., we take chess and replace pawns with juggling balls).

A less strict way is to say "two games are equivalent when they have the same outcome". For impartial games, we can do something more suited for formalization.

Given two impartial games G_0, G_1, the game sum G_0 + G_1 has the options H_0 + G_1 for every option H_0 of G_0 and G_0 + H_1 for each option H_1 of G_1.

Consider *n, a game of Nim with one pile of n tokens. Clearly, *0 is losing for player 1 because there are no moves, while *n for any other n is winning for player 1, because player 1 can just take all the tokens in the pile. The game sum simply adds the piles together - *5 + *4 is a Nim game in which there are two piles of sizes 5 and 4. For any *m + *n, the options are *u + *n for any 0 \le u < m and *m + *v for any 0 \le v \le n.