Skip to content
Tutorials Center
My learning

Topics

Lesson 5 of 37 ยท Games and Strategies

Normal-Form Games and Strategies

Define normal-form games formally with players, strategy sets and payoff functions, enumerate strategy profiles with itertools, and handle games with three or more players.

The matrix you built in Payoff Matrices in NumPy is a special case of the most common way to describe a game: the normal form, also called the strategic form. It describes a game in which every player chooses a strategy once, all at the same time, and then everyone receives a payoff that depends on the combination of choices.

This lesson makes the definition precise. Precision pays off: once the objects are clear (players, strategies, profiles, payoff functions), every later concept in the course, from dominance to Nash equilibrium to mixed strategies, is a short sentence about them. We also leave the two-player world and see how the same ideas handle three or more players.

The formal definition

A normal-form game has three components.

  1. A finite set of players N = {1, 2, ..., n}.
  2. For each player i, a set of strategies S_i. A strategy is a complete plan of action. In a simultaneous one-shot game, a strategy is just an action.
  3. For each player i, a payoff function u_i, which assigns a number to every strategy profile.

A strategy profile is one strategy for every player, written s = (s_1, s_2, ..., s_n). The set of all profiles is the Cartesian product S = S_1 x S_2 x ... x S_n. If Ann has 2 strategies and Bob has 3, there are 6 profiles. The payoff u_i(s) is player i's utility when the profile s is played.

A very useful notation is s_{-i}, which means "everyone's strategy except player i's." Then the profile can be written (s_i, s_{-i}). We use it constantly: "player i compares u_i(a, s_{-i}) with u_i(b, s_{-i})" means "holding everyone else fixed, is a better than b?"

flowchart TD
    G["Normal-form game"] --> P["Players N"]
    G --> S["Strategy sets S1, S2, ..."]
    G --> U["Payoff functions u1, u2, ..."]
    S --> PR["Strategy profile s = (s1, s2, ...)"]
    PR --> U

A game is complete once you know who plays, what they can choose and what each profile pays.

Enumerating profiles in Python

For small games, itertools.product produces the whole profile set. We can store a game as a dictionary from profiles to payoff tuples, which works for any number of players.

Python Profiles and payoffs for two players

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The number of profiles is the product of the sizes of the strategy sets. It grows fast: ten players with two strategies each already give 1,024 profiles, and 20 players give more than a million. That growth is why large games are described by rules instead of tables.

Three or more players

The normal form does not care how many players there are. For three players the payoff table becomes a 3D array: one slice per strategy of the third player. In NumPy, you can store the payoffs as an array U with shape (players, |S_1|, |S_2|, |S_3|), so that U[i][s1, s2, s3] is the payoff of player i.

As an example, take a voting game. Three friends each vote for Pizza (0) or Sushi (1). Majority wins. Each friend gets 2 points if their own preferred dish wins, and 0 otherwise. The first two prefer pizza, the third prefers sushi.

Python A three-player voting game

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the last section you can see one of the quirks of voting: friend 2's vote only matters when the other two split. When both others vote pizza, nothing friend 2 does changes the outcome. A voter whose choice can change the result is called pivotal, a concept that returns in the chapter on mechanism design.

Pure strategies and complete plans

In a one-shot simultaneous game, a strategy and an action are the same thing. In games with several moves, a strategy is a complete contingency plan: it says what to do at every point where the player might have to move. Chess has more strategies than there are atoms in the universe because a strategy must say what to play in every possible position. We use the word "pure strategy" for a plan with no randomness, and "mixed strategy" for a random choice among plans; mixed strategies get their own chapter, starting with Mixed Strategies.

Symmetric games

A two-player game is symmetric if both players have the same strategies and the payoff to playing a against b is the same for either player. Formally u_1(a, b) = u_2(b, a). In matrix form, B = A.T (the column player's matrix is the transpose of the row player's). Symmetric games are common: the prisoner's dilemma, hawk-dove and rock-paper-scissors are all symmetric. Symmetry simplifies analysis because you only need one matrix.

Python Testing symmetry with B = A.T

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Reading a game table well

When you meet a new game, ask these questions in order:

  1. Who are the players, and how many strategies does each have?
  2. Is the move order simultaneous? (This chapter assumes yes.)
  3. Are the payoffs ordinal rankings or real utilities? Does the game involve risk?
  4. Is the game symmetric or zero-sum, which allows shortcuts?
  5. Are there obviously bad strategies? That is the topic of the next lesson, Dominant Strategies.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How many strategy profiles does a game have if three players have 2, 3 and 4 strategies?

    The number of profiles is the product of the strategy-set sizes: 2 * 3 * 4 = 24.
  2. 2. What does the notation s_{-i} mean?

    s_{-i} bundles everyone else's strategies, so (s_i, s_{-i}) is the full profile.
  3. 3. A two-player game is symmetric when...

    Symmetry means swapping the roles of the players swaps the payoffs; in matrix form B = A transposed.
  4. 4. In a one-shot simultaneous game, what is a strategy?

    With a single simultaneous move, a plan of action is just one action. In multi-move games, a strategy must specify an action at every decision point.
  5. 5. Why do large games usually not appear as payoff tables?

    Adding a player multiplies the number of profiles, so tables become astronomically large and rules or formulas are used instead.

Summary

  • A normal-form game consists of players, a strategy set for each player and a payoff function for each player over strategy profiles.
  • A profile picks one strategy for every player; s_{-i} is everyone but player i.
  • itertools.product enumerates profiles; three-player games fit a 3D array.
  • Symmetric two-player games satisfy B = A.T and need only one matrix.
  • The number of profiles multiplies with each additional player.

Next: Dominant Strategies