Game Theory

Strategic Games

So far, we have been discussing the structure of interconnecting links. Now we are going to look at the interdependence in behavior of agents.

$n$-Player Games

Strategic games are used to model and analyse situations where the outcome of a person’s decisions depend also on choices made by people they interact with. This includes, for example, the question of how to defend against a penalty kick in a soccer match, the pricing of a new product in a competitive market, how to bid at an auction, or how to choose a route through a transportation network. Games have also been applied as models in evolutionary biology.

The players involved in a strategic game are regarded as selfish agents, only interested in maximizing their own payoff. Some of the central questions in strategic game theory are: When is selfish behavior essentially benign? How do selfish players reach an equilibrium (and do they)?

A game has the following ingredients.

  1. Players (these are the decision makers)
  2. Action (strategies, one set of options for each player)
  3. Payoffs (to be maximized)

On this basis, one has the following formal definition.

Definition. A finite $n$-person normal form game is a triple $(N, A, u)$, where

  • $N = \{1, 2, \dots, n\}$ is a (finite) set of $n$ players,

  • $A = A_1 \times A_2 \times \dots \times A_n$, and $A_i$, for $i \in N$, is the finite set of actions for player $i$ (we call $a = (a_1, a_2, \dots, a_n) \in A$ an action profile),

  • $u = (u_1, u_2, \dots, u_n)$ is a profile of utility functions, and $u_i \colon A \to \mathbb{R}$ is the utility function (payoff) for player $i$.

For $n = 2$, there is a standard matrix representation of a $2$-player game by a matrix whose

  • rows correspond to the actions $a_1 \in A_1$,
  • columns correspond to the actions $a_2 \in A_2$,
  • cells contain the payoffs $u_1(a_1, a_2)$ and $u_2(a_1, a_2)$.

Example. Two students have both an exam and a joint presentation on the next day. Each student only has time to prepare for one, the exam, or the joint presentation. The outcomes can be predicted as follows. On the exam, each student will score $92\%$ if prepared, and $80\%$ if not. For the presentation, they will score $100\%$ if both prepare for it, $92\%$ if only one prepares for it, and $84\%$ if none prepares for it.

On average then, if both prepare for the presentation (and not for the exam), they both score $\frac12(100+80) = 90$. If both prepare for the exam (and not for the presentation), they both score $\frac12(92 + 84) = 88$. And if student $1$ prepares the presentation, and student $2$ studies for the exam, then, on average, student $1$ will score $\frac12(92 + 80) = 86$ and student $2$ will score $\frac12(92 + 92) = 92$. Similar if student $1$ studies for the exam and student $2$ prepares the presentation. These outcomes (payoffs) can be summarized in a matrix, where the rows correspond to student $1$’s options ($P$: prepare presentation, $E$: prepare for the exam), and the columns correspond to student $2$’s options:

The game can now be analyzed under the following assumptions.

  • The utility functions include everything the players care about (so that, e.g., their partner’s score would be accounted for if they did care),
  • complete information: the payoff matrix is known to all players,
  • rationality: each player aims at maximizing their payoff, and they know how to find an optimal strategy.

Example (cont’d). If player $2$ plays $P$, then player $1$ maximizes their payoff by playing $E$ (as $92 > 90$). If player $2$ plays $E$, then player $1$ maximizes their payoff again by playing $E$ (as $88 > 86$). So regardless of what action player $2$ is choosing, player $1$ will yield a higher payoff if they choose option $E$. For the same reason, option $E$ is preferable for player $2$.

So both players most likely will opt for $E$, yielding a payoff of $88$, despite the fact that there is an action profile (both opting for $P$) that would yield a higher payoff for both of them.

This game is an example of a situation, which in game theory is known as the Prisoner’s Dilemma.

Prisoner’s Dilemma. A prisoner’s dilemma is a $2$-player game, where each player has two options, $C$ and $D$, with payoffs as in the matrix

where $c > a > d > b$.

Concepts. In a game $(N, A, u)$, for $i \in N$, it will be convenient to write $A_{-i}$ for $A_1 \times \dots \times A_{i-1} \times A_{i+1} \times \dots A_n$, the product of all sets $A_j$ but $A_i$, and $a_{-i}$ for $(a_1, \dots, a_{i-1}, a_{i+1}, \dots, a_n)$.

An action $a_i \in A_i$ is a best response to $a_{-i} \in A_{-i}$ if $u_i(a_i, a_{-i}) \geq u_i(a_i’, a_{-i})$ for all $a_i’ \in A_i$, and it is a strict best response to $a_{-i} \in A_{-i}$ if $u_i(a_i, a_{-i}) > u_i(a_i’, a_{-i})$ for all $a_i’ \neq a_i$.

An action $a_i \in A_i$ is a (strictly) dominant strategy for player $i \in N$, if it is a (strict) best response to each $a_{-i} \in A_{-i}$.

In a Prisoner’s Dilemma, each player has a strictly dominant strategy. A rational agent will always play a dominant strategy, if they have one.

Even if only one player in a $2$-player game has a dominant strategy, it is still possible to analyze the game, as in the following example.

Example. There are two companies, C1 and C2, planning to introduce a new product into a market that is cleanly divided into a low-price segment and an upscale segment. Each company has two options, as to whether their product will be low-priced ($L$) or upscale ($U$). The sales are predicted on the basis of the following two assumptions.

  • The low-priced segment accounts for 60% of the population, the upscale segment for the other 40%.
  • Company 1, being the more popular of the two will attract 80% of the sales in case of direct competition, leaving only 20% to company 2.

This leads to the following payoff matrix (with rows corresponding to the options for company 1, and columns to company 2):

Here, strategy $L$ is a strictly dominant strategy for company 1, which they will play as a rational agent. Consequently, company 2 will play strategy $U$, as it is more profitable for them in this case.