COMP 3200 - Intro to Artificial Intelligence - Lecture 08 - Intro to Game Theory

Overview

Dave Churchill introduces matrix-game theory as a way to model strategic decisions using players, available strategies, and numerical payoffs that represent utility. Through examples including the Prisoner’s Dilemma, Split or Steal, a defense game, and a group investment decision, he explains strict and weak dominance, best responses, iterated deletion of dominated strategies, and Nash equilibrium.

Key takeaways

A strictly dominated strategy yields a lower payoff than another strategy against every possible opponent action, so it should never be played.
Weak dominance permits ties: in Split or Steal, stealing beats splitting when the other player splits and ties it when the other player steals.
Payoff values encode player preferences, not objective prize measurements; a realistic model must account for factors such as risk, relationships, and diminishing value of money.
A best response is always conditional on a specific action by the other player, and predicting that action can guide a choice even when one's own matrix has no dominated strategy.
A Nash equilibrium is a full strategy profile where no individual player can improve by changing their action alone; a game can have multiple equilibria with very different payoffs.
Iterated deletion in the 1–100, two-thirds-of-the-average game can narrow the rational-choice range toward 1, but the outcome depends on how many levels of reasoning players expect from one another.

Chapters

0:00 The 2/3-Average Numbers Game and Its 24 Winner

Students secretly chose integers from 1 to 100; the winner was closest to two-thirds of the class average.
With 28 responses, the average was 35.8 and the target was 23.8, so the student who chose 24 won.
Churchill notes that repeated rounds tend to push choices downward, setting up a later discussion of strategic reasoning.

4:24 Game Theory Begins with the Grades Game

Game theory uses mathematical models to analyze strategic decisions in economics, computer science, social science, and everyday situations.
In the grades game, two players independently choose alpha or beta; the outcomes include B−, A, C, and B+.
Different students favor alpha or beta for different reasons, illustrating why a clear representation helps compare choices.

9:22 Turning Grade Outcomes into a Two-Player Matrix

An outcome matrix places one player's alpha/beta choices in rows and the other player's choices in columns.
Each cell first records the outcome for one player; combining both players' results gives payoff pairs in each cell.
The two-player, two-action format is a visual simplification; games can include many players and different strategy sets.

13:15 Payoffs Convert Outcomes into Utility

A game needs numerical payoffs to specify what players are trying to maximize; assigning values to real-world outcomes is part of modeling.
In a greedy grades example, B− is assigned utility 0, an A is worth 3, and a C is worth −1.
Against either alpha or beta, choosing alpha gives the higher payoff, showing how a payoff matrix can make a choice mathematically clear.

19:53 Strict Dominance: Never Choose an Always-Worse Strategy

A strategy strictly dominates another when it gives a higher payoff for every possible choice by the other players.
In the greedy grades game, alpha strictly dominates beta because alpha pays better whether the opponent chooses alpha or beta.
Dominance identifies strategies to avoid; with more than two choices, it does not necessarily identify one best strategy.

22:01 The Prisoner’s Dilemma Makes Telling Dominate Silence

Two prisoners independently choose whether to tell on the other; the example assigns payoffs of −1 for one year, −2 for two years, −5 for five years, and 0 for freedom.
For either action by the other prisoner, telling produces a higher payoff than staying silent.
Telling therefore strictly dominates silence in the example; Churchill emphasizes that real-world risks, such as retaliation, would need to be included in the payoffs.

26:44 Split or Steal: Weak Dominance and Payoff Assumptions

In the game-show example, splitting with another splitter yields half the prize, while stealing against a splitter yields the whole prize.
If the other player steals, either choice yields zero; stealing is therefore weakly dominant because it is better in one case and tied in another.
The calculated result depends on how players value money: $100,000 need not be worth twice as much as $50,000 to every player.

33:15 Greedy and Caring Players Can Have Different Payoffs

A greedy player values their own grade, while a caring player may dislike outcomes where a friend receives a C.
Changing the caring player's utility values can remove dominance: alpha is better against one opponent action, while beta is better against the other.
Different preferences make the payoff matrix asymmetric, so each player must be analyzed using their own utility values.

36:21 Best Responses Use Predictions About the Other Player

A best response is the strategy that performs best against one specific strategy chosen by another player.
In the greedy-versus-caring example, alpha dominates beta for the greedy player, so the caring player can predict alpha and choose their best response to it.
A best response must be stated relative to a particular opponent action, not to the opponent in general.

41:06 Formal Game Notation: Players, Strategy Sets, and Profiles

A strategy is one action by a player; a strategy set is all actions available to that player.
A strategy profile records one action for every player, while the profile excluding player i's action is written as the other players' choices.
The utility function assigns player i a payoff for a complete strategy profile, such as the outcome when everyone chooses a number in the 1–100 game.

45:58 Finding Dominated Actions in a 2-by-3 Matrix

In the example, player one chooses top or bottom, while player two chooses left, center, or right.
Player one has no dominated strategy because top and bottom each outperform the other in at least one column.
For player two, center strictly dominates right across both rows, so right should never be chosen even though center does not dominate left.

51:22 The Defense Game: Weak Dominance Guides a Best Response

A defender chooses the easy or hard gate while an attacker chooses a route; taking the hard path costs the attacker one of two armies.
The attacker receives at least as much utility by choosing the easy route, so easy weakly dominates hard.
If the defender predicts the attacker will choose easy, defending the easy gate is the defender's best response.

58:09 Iterated Deletion Drives the Numbers Game Toward One

If everyone chose 100, the target would be about 67, making choices from 68 to 100 worse than 67; similar reasoning can eliminate more choices.
Assuming players avoid dominated strategies repeatedly reduces the candidate range from 1–100 toward 1.
The prediction depends on how many layers of rationality players expect from one another; observed choices and the class average of 35.8 show people do not automatically reason all the way down.

1:04:16 Nash Equilibrium: Every Player Is Best-Responding

A Nash equilibrium is a complete strategy profile in which every player's action is a best response to the other players' actions.
Equivalently, no single player can change their strategy and achieve a strictly higher payoff while everyone else's choices stay fixed.
In the matrix example, player one choosing down and player two choosing right is an equilibrium; another example has two equilibria, at middle/center and down/right.

1:12:36 Investment Game Equilibria and Exam Applications

In the investment game, investing $100 doubles the money if more than 80% invest and loses $100 if fewer than 80% invest; not investing yields zero.
The two Nash equilibria are everyone investing and nobody investing: a lone deviation from either outcome does not improve the deviator's payoff.
Churchill lists likely exam tasks including identifying dominated strategies, finding best responses, defining Nash equilibrium, and finding every equilibrium in a payoff matrix.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Dave Churchill.