Normal-Form Games and Mixed Strategies

1. What is a Normal-Form Game?

In game theory, we need a precise way to describe a strategic situation. The most fundamental representation is the normal-form game. It specifies three core components: the players, the possible actions for each player, and the outcomes or payoffs for every combination of actions.

To get a conceptual overview, let's start with a short video.

The video provides a good intuitive foundation. Now, let's formalize this. As a computer science student, you'll find that these formal definitions are what allow us to reason about games algorithmically.

To summarize, a normal-form game is defined by a tuple (P, A, u):

• P (or N): A set of players, e.g., {1, 2}.
• A: A set of action profiles. This is the Cartesian product of each player's individual action set, $A=A_1\times A_2\times \cdots \times A_n$. An action profile a = (a_1, a_2, ..., a_n) is a specific combination of one action from each player. In this context of one-shot, simultaneous-move games, "actions" and "pure strategies" are used interchangeably.
• u: A tuple of utility or payoff functions, u = (u_1, u_2, ..., u_n). Each function $u_i:A\to \mathbb{R}$ maps an action profile to a real number, representing the payoff for player $i$.

For two-player games, this structure is almost always represented by a payoff matrix. The first player (Player 1) is the "row player" and the second (Player 2) is the "column player". Each cell in the matrix corresponds to an action profile, and contains the payoffs as a tuple (u_1, u_2).

2. Pure vs. Mixed Strategies

So far, we've implicitly assumed that a player chooses a single, definite action. This is called a pure strategy. For example, in Rock-Paper-Scissors, always choosing "Rock" is a pure strategy.

However, players can also randomize their choices. A mixed strategy is a probability distribution over a player's set of pure strategies. Instead of committing to one action, the player commits to a set of probabilities for choosing each action.

Let's return to the lecture notes for the formal definition.

The key takeaway is the formula for the expected payoff for player $i$ given a mixed-strategy profile $s=(s_1,\dots ,s_n)$:

Let's break this down:

• $a=(a_1,\dots ,a_n)$ is a pure-strategy (action) profile.
• $u_i(a)$ is the payoff to player $i$ if that specific profile $a$ is played.
• $s_j(a_j)$ is the probability that player $j$ chooses action $a_j$ according to their mixed strategy $s_j$.
• ${\prod }_{j=1}^n{s}_j(a_j)$ is the probability of the pure-strategy profile $a$ occurring, assuming players choose their actions independently.

The formula is the standard definition of mathematical expectation: a weighted average of all possible payoff values, where each weight is the probability of that payoff occurring.

3. Calculating Expected Payoffs

Knowing the formula is one thing; applying it is another. Let's watch a clear, practical demonstration of how to compute these payoffs in a 2x2 game.

This method is a direct application of the formula we just saw. Let's work through another example to solidify this. Consider the game of Matching Pennies. Player 1 wins if the pennies match (H,H or T,T), and Player 2 wins if they don't (H,T or T,H). The payoff matrix looks like this:

Suppose Player 2 adopts a mixed strategy $s_2$ of playing Head with probability $q$ and Tail with probability $1-q$. What is Player 1's expected payoff if they play the pure strategy Head?

We calculate the expectation over Player 2's choices:

• Player 2 plays Head (with prob $q$), outcome is (H,H), P1's payoff is 1.
• Player 2 plays Tail (with prob $1-q$), outcome is (H,T), P1's payoff is -1.

So, Player 1's expected payoff for playing Head, given Player 2's strategy $s_2$, is:

This is exactly what the following image illustrates.

Similarly, let's calculate Player 1's expected payoff for playing the pure strategy Tail, given Player 2's same strategy $s_2$:

Now, what if Player 1 also plays a mixed strategy, $s_1$, choosing Head with probability $p$ and Tail with probability $1-p$?

The overall expected payoff for Player 1, $u_1(s_1,s_2)$, is the weighted average of the expected payoffs of their pure strategies:

This calculation is fundamental. Being able to compute a player's expected payoff given their opponents' strategies is a prerequisite for finding optimal strategies and game equilibria.

Conclusion

In this lesson, we have established the essential vocabulary and mechanics for analyzing games.

Key Takeaways:

• A normal-form game is formally defined by a set of players, a set of action profiles, and a set of payoff functions (P, A, u).
• A pure strategy is a deterministic choice of an action, while a mixed strategy is a probability distribution over the set of pure strategies.
• The expected payoff of a mixed-strategy profile is the sum of the payoffs of all possible pure-strategy outcomes, each weighted by its probability of occurring. We can calculate this systematically by considering each player's strategy.

This foundation is crucial. You can't determine the "best" way to play a game without first being able to evaluate the outcome of playing it in a certain way.

Preview of the next lesson:
In the next lesson, we will build directly on this by asking: given an opponent's strategy, what is my best response? This will lead us to the concepts of best response and dominated strategies, which are the first tools we use to start "solving" games by eliminating irrational choices.