1 Rationalizable strategies
Multi-agent decision problems are conceptually different from single agent decision problems. In a single agent decision problem, a decision maker has to choose a strategy \(s \in \ALPHABET S\) and receives a payoff or utility \(u(s)\) (or, equivalently, incurs a cost \(c(s)\)). In multi-agent decision problems, the utility received by an agent may depend on the strategies of other agents. Such settings are called games. We start with the simplest setting of two player games.
Consider a decision problem where there are two players. Player 1 (\(P_1\) from now on) chooses an strategy \(s_1 \in \ALPHABET S_1\) and player 2 (\(P_2\) from now on) chooses an strategy \(s_2 \in \ALPHABET S_2\). Once both players have chosen their strategies, \(P_1\) receives a payoff of \(u_1(s_1, s_2)\) and \(P_2\) receives a payoff of \(u_2(s_1,s_2)\). How should the players behave?
1.1 Examples
We start with a few examples.
Two criminals are arrested for a crime but the prosecutors have evidence to only charge them for a lesser crime but not enough to charge them for the main crime. The prisoners are kept in separate cells with no means to communicate. The prosecutors simultaneously offer the following bargain to both prisoners: serve as a witness that the other criminal committed the crime and walk free; unless the other also confesses in which case both get sentenced. If both criminals confess, both get a reduced sentenced for the main crime (2 years in prison). If only one confesses, the criminal who confessed walks free while the other gets a full sentence for the main crime (10 years in prison). If neither prisoner takes the bargain, then both get charged for the lesser crime (1 year in prison).
This example can be modeled as a two player game as follow. The strategy sets of both players are \(\ALPHABET S_1 = \ALPHABET S_2 = \{ \mathsf{A}, \mathsf{R} \}\), where \(\mathsf{A}\) means that the player accepts the bargain and \(\mathsf{R}\) means that the player rejects the bargain. The utility functions can be represented compactly as follows, which is called the bimatrix representation of the game.
| \(\mathsf{A}\) | \(\mathsf{R}\) | |||
| \(\mathsf{A}\) | \(-2\) | \(-2\) | \(0\) | \(-3\) |
| \(\mathsf{R}\) | \(-3\) | \(0\) | \(-1\) | \(-1\) |
A couple wants to go out for the evening and there are two events taking place: a football game and an opera. One person (player 1) prefers to go to the football game while the other player (player 2) prefers to go the opera. But they want to go together and are miserable if they go to separate events.
| \(\mathsf{F}\) | \(\mathsf{O}\) | |||
| \(\mathsf{F}\) | \(2\) | \(1\) | \(0\) | \(0\) |
| \(\mathsf{O}\) | \(0\) | \(0\) | \(1\) | \(2\) |
Two drivers are headed for a single lane bridge from opposite directions. The first to swerve away yields the bridge to the other and is called ‘chicken’ (i.e., a coward). If neither swerve, both are involved in a head-on collision.
| \(\mathsf{C}\) | \(\mathsf{H}\) | |||
| \(\mathsf{C}\) | \(3\) | \(3\) | \(1\) | \(10\) |
| \(\mathsf{H}\) | \(10\) | \(1\) | \(0\) | \(0\) |
Consider a parlour game among two players. Each player has a penny and must secretly turn the penny to heads or tails. The players reveal their choices simultaneously. If the pennies match (both heads or both tails), player 1 wins. If they don’t player 2 wins.
| \(\mathsf{H}\) | \(\mathsf{T}\) | |||
| \(\mathsf{H}\) | \(1\) | \(-1\) | \(-1\) | \(1\) |
| \(\mathsf{T}\) | \(-1\) | \(1\) | \(1\) | \(-1\) |
In the games described above, there is a conflict between the players. We cannot simply assert that the players should take an strategy which maximizes their utility because the utility of a player depends on the strategies of other players, who have different incentives. The objective of game theory is to understand how to make decisions in such scenarios.
1.2 Modeling Strategic Games
The above examples described games between two players. General \(n\)-player games can be modeled as follows.
Definition 1.1 (Strategic game) A strategic game is described by a tuple \(\mathscr{G} = \langle N, (\ALPHABET S_i)_{i \in N}, (u_i)_{i \in N} \rangle\), where
- \(N\) is a (finite) set of players
- \(\ALPHABET S_i\) is a non-empty set of strategies for player \(i\), \(i \in N\). Define \(\ALPHABET S = \prod_{i \in N} \ALPHABET S_i\) as the strategy space of the game \(\mathscr{G}\).
- \(u_i \colon \ALPHABET S \to \reals\) is the utility function of player \(i\), \(i \in N\).
- Remarks
-
- The utlity of player \(i\) depends on the strategies of all players and not just the strategy of player \(i\). This is the defining feature of a game.
- When all \(\ALPHABET S_i\) are finite, the game is called a finite game. Such games are also sometimes called matrix games because they can be described by a matrix, as seen in the above examples.
- To play the game, each player chooses a (pure) strategy \(s_i \in \ALPHABET S_i\).
- The collection \(s = (s_i)_{i \in N}\) is called the strategy profile.
- Given a profile \(x = (x_i)_{i \in N}\) (not necessarily strategy profile, but any list of elements, one for each player), \(x_{-i}\) denotes the list \((x_j)_{j \in N \setminus \{i\}}\). We will write \(x = (x_i, x_{-i})\).
1.3 Dominated strategies
We now define the notion of dominance, which can be used to provide a solution concept for some games.
Definition 1.2 (Dominance) Consider a game \(\mathscr{G}\) with standard notation. Let \(s_i, t_i \in \ALPHABET S_i\) be two strategies of player \(i\). We say, strategy \(s_i\) strictly dominates \(t_i\) if \[ u_i(s_i, s_{-i}) \mathbin{\color{red}>} u_i(t_i, s_{-i}), \quad \forall s_{-i} \in \ALPHABET S_{-i}. \] We say that \(s_i\) weakly dominates \(t_i\) if \[ u_i(s_i, s_{-i}) \mathbin{\color{red}\ge} u_i(t_i, s_{-i}), \quad \forall s_{-i} \in \ALPHABET S_{-i} \] and the inequality is strict for at least one \(s_{-i}\).
We will also use the phrase “\(t_i\) is (strongly or weakly) dominated by \(s_i\)” to denote the same fact.
A strategy \(s_i \in \ALPHABET S_i\) is called (strongly or weakly) dominant strategy if it (strongly or weakly) dominates all other strategies \(t_i \in \ALPHABET S_i \setminus \{s_i\}\).
We now impose some assumptions on the players.
Assumption. A rational player will not choose a strictly dominated strategy.
Note that we have not formally defined rationality. That is more of a philosophical discussion, and for the purpose of this course, we will not present a formal definition but rather go with the colloquial meaning of the word.
Assumption. All players in a game are rational.
Irrespective of the definition of rationality, this assumption is often violated in practice. Human decision makers are almost never rational. Even when decisions are made by algorithms, the decisions may not be rational. There is a whole branch of decision theory which considers players with bounded rationality. However, in this course, we will make the simplifying assumption that the players are rational.
1.4 Dominant strategy equilibrium
We now present the simplest solution concept for a game.
Dominant Strategy equilibrium is a strategy profile in which each player is playing a dominant strategy.
For example, consider the game of prisoner’s dilemma. Note that, for \(P_1\), \[\begin{align*} u_1(\mathsf{A}, \cdot) &= \begin{bmatrix} -2 & 0 \end{bmatrix}, \\ u_1(\mathsf{R}, \cdot) &= \begin{bmatrix} -3 & -1 \end{bmatrix}. \end{align*}\] Note that \[ u_1(\mathsf{A}, ⋅) > u_1(\mathsf{R}, ⋅). \] Thus \(\mathsf{A}\) is a dominant strategy for \(P_1\).
Similarly, for \(P_2\), \[\begin{align*} u_2(\cdot, \mathsf{A}) &= \begin{bmatrix} -2 \\ 0 \end{bmatrix}, & u_2(\cdot, \mathsf{R}) &= \begin{bmatrix} -3 \\ -1 \end{bmatrix}. \end{align*}\] Note that \[ u_2(⋅,\mathsf{A}) > u_2(⋅,\mathsf{R}). \] Thus, \(\mathsf{A}\) is a dominant strategy for \(P_2\).
Therefore, \((\mathsf{A}, \mathsf{A})\) is a dominant strategy equilibrium. Note that both players play \(\mathsf{A}\) even though \((\mathsf{R}, \mathsf{R})\) gives a better outcome for both of them!
A game may not have a dominant strategy equilibrium. For example, there are no dominant strategies in the battle of sexes and matching pennies. So, dominant strategy equilibrium is not a useful solution concept because it does not always exist. One option is to generalize the notion of dominance as explained next.
1.5 Rationalizable equilibrium
First, we return to the assumptions imposed on the players. Consider the following game.
| \(\mathsf{L}\) | \(\mathsf{C}\) | \(\mathsf{R}\) | ||||
| \(\mathsf{T}\) | \(1\) | \(0\) | \(1\) | \(2\) | \(0\) | \(1\) |
| \(\mathsf{B}\) | \(0\) | \(3\) | \(0\) | \(1\) | \(2\) | \(0\) |
Strategy \(\mathsf{R}\) is strictly dominated for player 2 (by strategy \(\mathsf{C}\)). So, if \(P_2\) is rational, he will never choose \(\mathsf{R}\). Can we eliminate strategy \(\mathsf{R}\) from consideration?
The argument is not so simple. If \(P_1\) does not know that \(P_2\) is rational, he is liable to believe that \(P_2\) might choose strategy \(\mathsf{R}\), in which case it would be in \(P_1\)’s interest to player strategy \(\mathsf{B}\).
However, if we postulate that
- \(P_2\) is rational, and
- \(P_1\) knows that \(P_2\) is rational.
Then, \(P_1\) knows that \(P_2\) will not player strategy \(\mathsf{R}\). However, \(P_2\) doesn’t know that \(P_1\) knows that \(P_2\) is rational. Therefore, \(P_2\) doesn’t know that \(P_1\) knows that \(P_2\) will not play strategy \(\mathsf{R}\). Thus, we need to assume that
- \(P_2\) knows that \(P_1\) knows that \(P_2\) is rational.
Continuing this way, we can argue that we we need to assume that
- \(P_1\) knows that \(P_2\) knows that \(P_1\) knows that \(P_2\) is rational.
- and so on.
If statements of this type hold for infinite depth, we say that the fact that \(P_2\) is rational is common knowledge. We will revisit common knowledge later in the course. For now, we assume the following.
Assumption. It is common knowledge that all players are rational.
Under the assumption of common knowledge of rationality, we can assume that the players will eliminate strictly dominated strategies. For example, in the previous example, both players can eliminate strategy \(\mathsf{R}\) from consideration and simplify the original game \(\mathscr{G}\) to game \(\mathscr{G}_1\) shown below.
| \(\mathsf{L}\) | \(\mathsf{C}\) | \(\mathsf{R}\) | ||||
| \(\mathsf{T}\) | \(1\) | \(0\) | \(1\) | \(2\) | \(0\) | \(1\) |
| \(\mathsf{B}\) | \(0\) | \(3\) | \(0\) | \(1\) | \(2\) | \(0\) |
| \(\mathsf{L}\) | \(\mathsf{C}\) | |||
| \(\mathsf{T}\) | \(1\) | \(0\) | \(1\) | \(2\) |
| \(\mathsf{B}\) | \(0\) | \(3\) | \(0\) | \(1\) |
We can continue this reasoning. In the reduced game \(\mathscr{G}_1\), strategy \(\mathsf{B}\) for \(P_1\) is dominated by strategy \(\mathsf{T}\). So, we obtain the reduced game \(\mathscr{G}_2\) shown below.
| \(\mathsf{L}\) | \(\mathsf{C}\) | |||
| \(\mathsf{T}\) | \(1\) | \(0\) | \(1\) | \(2\) |
Finally, we can eliminate strategy \(\mathsf{L}\) for \(P_2\), which is strictly dominated by \(\mathsf{C}\) to obtain game \(\mathscr{G}_3\) shown below.
| \(\mathsf{C}\) | ||
| \(\mathsf{T}\) | \(1\) | \(2\) |
This procedure is called IEDS (Iterative elimination of dominated strategies). If the procedure gives a unique strategy, that strategy is called a rationalizable strategy. (The formal definition of rationalizable strategies is different. But the case of two player games, rationalizable strategies are the seame as strategies obtained by IEDS, but they may different for games with more than two players. See Bernheim 1984)
- Remarks
-
- In general, IEDS may not lead to a solution (i.e., we may be left with a game which is not \(1 × 1\) where no strategy is dominated).
- At each step, there may be more than one strictly dominated strategy. If so, we can simultaneously eliminate all of them.
- Irrespective of the order in which strategies are eliminated, IEDS gives the same simplified game.
Rationalizable equilibrium are derived under the assumption of common knowledge of rationality, which appears to be a benign assumption but is not. To see why common knowledge of rationality is a strong assumption, consider the following example, which is known as the beauty contest game.
Each player picks a real number between 0 and 100. The person who was closest to half of the average of the group wins a prize.
:Beauty contest games were introduced by Keynes (1936), where all participants have to guess the average. In \(p\)-beauty contest games, introduced by Moulin (1986), participants have to guess closest to \(p\) times the average, with \(p \in (0, 1)\). For a discussion of an experimental study of \(p\)-beauty contest games, see Nagel (1995).
How will you play this game?
1.6 Iterative elimination of weakly dominated strategies
We can extend the notion of IEDS to IEWDS (Iterative elimination of weakly dominated strategies) if we make the following assumption.
Assumption. A rational player never plays a weakly dominated strategy.
The assumption that a player never plays a weakly domainted strategy is less compelling than the assumption of never playing a strictly dominated strategy.
One way to justify the assumption of never playing a weakly dominated strategy is the concept of trembling hand principle, which is due to Selten (1975). The key idea of this principle is that the player may make mistakes when executing its strategy (hence the metaphor of trembling hand): thus all possible strategies may be used with positive probability. In such a scenario, it is never optimal to play weakly dominated strategies.
Similar to IEDS, we may consider an iterative procedure to eliminate weakly dominated strategies (abbreviated as IEWDS). IEWDS allows us to find solutions of games where IEDS doesn’t work (see the second price auction example below). If IEWDS gives us a unique solution, we call the resulting strategy as a rationalizable strategy
However, unlike IEDS where the order of elimination of strategies does not matter, in IEWDS we can end up with different games depending on the order of elimination of strategies. For example, consider the following game:
| \(\mathsf{L}\) | \(\mathsf{C}\) | \(\mathsf{R}\) | ||||
| \(\mathsf{T}\) | \(1\) | \(1\) | \(1\) | \(1\) | \(0\) | \(0\) |
| \(\mathsf{B}\) | \(0\) | \(0\) | \(1\) | \(2\) | \(1\) | \(2\) |
Note that both strategies \(\mathsf{L}\) and \(\mathsf{R}\) are weakly dominated by \(\mathsf{C}\).
Case 1: Eliminate \(\mathsf{L}\)
If we eliminate \(\mathsf{L}\), we obtain the following reduction.
| \(\mathsf{C}\) | \(\mathsf{R}\) | |||
| \(\mathsf{T}\) | \(1\) | \(1\) | \(0\) | \(0\) |
| \(\mathsf{B}\) | \(1\) | \(2\) | \(1\) | \(2\) |
Now, for \(P_1\), strategy \(\mathsf{T}\) is dominated by strategy \(\mathsf{B}\). Eliminating \(\mathsf{T}\) we get
| \(\mathsf{C}\) | \(\mathsf{R}\) | |||
| \(\mathsf{B}\) | \(1\) | \(2\) | \(1\) | \(2\) |
Case 2: Eliminate \(\mathsf{R}\)
If we eliminate \(\mathsf{R}\) in the original game, we get the following reduction.
| \(\mathsf{L}\) | \(\mathsf{C}\) | |||
| \(\mathsf{T}\) | \(1\) | \(1\) | \(1\) | \(1\) |
| \(\mathsf{B}\) | \(0\) | \(0\) | \(1\) | \(2\) |
Here, for \(P_1\), strategy \(\mathsf{B}\) is weakly dominated by strategy \(\mathsf{T}\). Eliminating \(\mathsf{B}\), we get
| \(\mathsf{L}\) | \(\mathsf{C}\) | |||
| \(\mathsf{T}\) | \(1\) | \(1\) | \(1\) | \(1\) |
Note that games \(\mathscr{G}_L\) and \(\mathscr{G}_R\) cannot be reduced further. The resulting payoffs are also different.
1.7 Second price auction
We will study auctions in detail later in the course, but here we use the concept of dominance to identify a rationalizable strategy in what are knows as sealed bid, second price auctions. This is an example of a game with continuous strategy spaces.
Sealed bid second price auctions work as follows:
- An indivisible object is for sale.
- The set of buyers is known as \(N\). Each buyer \(i\) attaches a value \(v_i\) to the object, i.e., he is willing to pay at most \(v_i\) for the object. The value \(v_i\) is the buyer’s internal assessment.
- Each buyer \(i\) bids \(b_i\), presented to the auctioneer in a sealed envelop.
- The buyer with the highest bid wins the object. If more than one buyer have the same highest bid, then the object goes to one of them at random.
- The key feature of second price auction is that, unlike the standard auctions, the winner does not pay what he bid. Instead, he pays the second highest bid offered (and hence the name, second price auctions).
How should a rational player act in such an auction.
Proposition 1.1 : In sealed bid second price auctions, the bidding strategy \(b_i = v_i\) weakly dominates all other strategies.
Consider a buyer \(i\) with value \(v_i\). Given a bid profile \(b = (b_j)_{j \in N}\), let
- \(B_{-i}\) be the highest bid by buyers other than \(i\).
- \(N_{-i}\) be the number of buyers (excluding \(i\)) who bid \(B_{-i}\)
Then, the payoff to player \(i\) is \[ u_i(b) = \begin{cases} 0, & \text{if $b_i < B_{-i}$} \\ \dfrac{v_i - B_{-i}}{N_{-i} + 1}, & \text{if $b_i = B_{-i}$} \\ v_i - B_{-i}, & \text{if $b_i > B_{-i}$} \end{cases}\]
Divide the set of strategies \(\ALPHABET S_i = [0, ∞)\) into three sets:
- Under bid, i.e., bid less than \(v_i\): i.e., the set \([0, v_i)\).
- Bid truthfully, bid equal to \(v_i\): i.e., the set \(\{v_i\}\).
- Over bid, i.e., bid greater than \(v_i\), i.e., the set \((v_i,∞)\).
See the plot in the figure above to see utility (as a function of \(B_{-i}\) for different values of \(b_i\).
Note that the curve for truthful bidding (i.e., \(b_i = v_i\)) weakly dominates the curves for under bidding as well as over bidding.
The rationalizability of truthful bidding holds in many situations. More on that later.
1.8 Dominance by mixed strategies
Consider a strategic game \(\mathscr{G} = \langle N, (\ALPHABET S_i)_{i \in N}, (u_i)_{i \in N} \rangle\) where \(\ALPHABET S_i = \{s_{i1}, \dots, s_{ik}\}\). Then a mixed strategy \(σ_i\) for player \(i\) is a probability distribution over pure strategies, i.e., \(σ_i \colon \ALPHABET S_i \to [0,1]\) such that \[ \sum_{s_i \in \ALPHABET S_i} σ_{i}(s_i) = 1 \]
For example, suppose \(\ALPHABET A = \{1,2,3\}\) and \(σ_i = (0.2, 0.3, 0.5)\). This means that player \(i\) chooses strategy \(1\) with probability \(0.2\), strategy \(2\) with probability \(0.3\), and strategy \(3\) with probability \(0.5\).
When other players are playing pure strategies \(s_{-i}\) and player \(i\) is playing a mixed strategy \(σ_i\), then the expected payoff to player \(i\) is \[ U_i(σ_i, s_{-i}) = \sum_{s_i \in \ALPHABET S_i} σ_{i}(s_i) u_i(s_{i}, s_{-i}). \]
For example, consider the matching pennies game where \(σ_1 = (p, 1-p)\). Then,
\[\begin{align*} U_1(σ_1, H) &= p - (1-p) = 2p - 1, \\ U_1(σ_1, T) &= -p + (1-p) = 1 - 2p. \end{align*}\]
We can think of a mixed strategy as a virtual row or virtual column in the bimatrix representation of the game as follows:
| \(\mathsf{H}\) | \(\mathsf{T}\) | |||
| \(\mathsf{H}\) | \(1\) | \(-1\) | \(-1\) | \(1\) |
| \(\mathsf{T}\) | \(-1\) | \(1\) | \(1\) | \(-1\) |
| \(σ_1\) | \(2p-1\) | \(\bullet\) | \(1-2p\) | \(\bullet\) |
We will revisit mixed strategies later in the course. For now, we will simply use the idea of mixed strategies to extend the notion of IEDS and IEWDS. For example consider the game shown below (where \(\bullet\) means that the value is not specified because it is not important for the discussion)
| \(\mathsf{L}\) | \(\mathsf{C}\) | \(\mathsf{R}\) | ||||
| \(\mathsf{T}\) | \(\bullet\) | \(3\) | \(\bullet\) | \(1\) | \(\bullet\) | \(0\) |
| \(\mathsf{B}\) | \(\bullet\) | \(0\) | \(\bullet\) | \(1\) | \(\bullet\) | \(3\) |
Note that none of the strategies of \(P_2\) are dominated. However, if we consider the mixed strategy \(σ_2 = (0.5, 0, 0.5)\), then
\[ U_2(\cdot, σ_2) = \begin{bmatrix} 1.5 \\ 1.5 \end{bmatrix} \] which dominates \(\mathsf{C}\). So we can eliminate strategy \(\mathsf{C}\).
1.9 Cournot competition
This is a model from economics and we will study it because of its simplicity. It is based on a model proposed by Cournot in 1839. The model describes the strategic interstrategy between firms in an oligopoly market (i.e., a market where a few sellers serve the entire market; both monopoly and duopoly are special cases of oligopoly). Cournot competition is used to model competition between energy generators in electricity markets, e.g., see Willems (2002), Acemoglu et al. (2017), Lundin and Tangerås (2020).
Formally, the Cournot competition model considers a homogeneous-goods market with \(n\) firms. A homogeneous-goods market is a market where all firms produce a homogeneous product which are perfect substitutes (e.g., consider a commodities market such as metal or oil or electricity).
Each firm decides how much to produce. Let \(s_i \in \reals_{\ge 0}\) denote the production of firm \(i\) and \(a = \sum_{i = 1}^n s_i\) denote aggregate production. The price of the product depends on the aggregate production. We capture this relationship using a generic function \(p \colon \reals_{\ge 0} \to \reals_{\ge 0}\), i.e., price of product is \(p(a)\) when the aggregate production is \(a\).
Furthermore, there is a cost \(c\) to produce one unit of goods. For simplicity, we assume that the cost is the same for all firms, though it is possible to consider the model this cost depends on the firm. Thus, the utility of firm \(i\) is \[ u_i(s_i, s_{-i}) = s_i \cdot p(a) - s_i \cdot c. \] We will analyze this game in the special case when the price function is \[ p(a) = \max \{ M - a, 0 \} \] where \(M\) is the market capacity. Thus, we are assuming that prices are proportional to marginal demand.
Case \(n = 1\)
To fix ideas, we consider the special case of \(n=1\) (i.e., a monopoly). In this case, for \(s_1 \in [0, M]\), \[ u_1(s_1) = s_1(M - s_1) - c s_1 = (M - c -s_1) s_1. \] To find the optimal value of \(s_1\), note that \(u_1(s_1)\) is concave in \(s_1\). Thus, we pick \(s_1\) such that \(∂u_1(s_1)/∂s_1 = 0\), i.e., \[ \frac{∂u_1(s_1)}{∂s_1} = (M - c -s_1) - s_1 = 0. \] Thus, \[ s_1 = \frac{M - c}{2} \quad\text{and}\quad u_1(s_1) = \frac{(M-c)^2}{4}. \]
Case \(n = 2\)
Now, let’s consider the case when \(n = 2\) (a duopoly). In this case, \[ u_i(s_1, s_2) = s_i( p(s_1 + s_2) - c). \] Again, we can verify that for a fixed \(s_2\), \(u_1(s_1, s_2)\) is concave in \(s_1\) and for a fixed \(s_1\), \(u_2(s_1, s_2)\) is concave in \(s_2\). So, the BR can be obtained by the first order optimality condition \(∂ u_i(s_1, s_2)/∂ s_i = 0\).
Note that \[ p(s_1 + s_2) = \begin{cases} M - (s_1 + s_2), & \text{if $s_1 + s_2 \le M$} \\ 0, & \text{otherwise} \end{cases}\] Therefore, (ignoring the non-differentiable point \(s_1 + s_2 = M\)), we have \[ \frac{∂p(s_1 + s_2)}{∂s_i} = \begin{cases} -1, & \text{if $s_1 + s_2 < M$} \\ 0, & \text{otherwise} \end{cases}\] So, \[\begin{align*} \frac{∂ u_i(s_1, s_2)}{∂ s_i} &= p(s_1 + s_2) - c + s_i \frac{∂ p(s_1 + s_2)}{∂ s_i} \\ &= \begin{cases} M - (s_1 + s_2) - c - s_i, & \text{if $s_1 + s_2 \le M$} \\ -c, & \text{otherwise}. \end{cases} \end{align*}\] So, if \(s_1 + s_2 < M\), the BR of firm 1 and firm 2 are: \[ B_1(s_2) = \frac{M - c -s_2}{2} \quad\text{and}\quad B_2(s_1) = \frac{M - c - s_1}{2}. \] We plot the BR relationships below.
Now we show that the game can be simplified using the elimination of never-best response strategies.
- After first round of elimination, we have \(\ALPHABET S_1 = \ALPHABET S_2 = \left[ 0, \frac{M-c}{2} \right]\).
- After second round of elimination, we have \(\ALPHABET S_1 = \ALPHABET S_2 = \left[ \frac{M-c}{4}, \frac{M-c}{2} \right]\).
- …
Continuing this way, we can show that the process converges to the intersection point \(\left( \frac{M-c}{3}, \frac{M-c}{3} \right)\) with payoff \(\left( \frac{(M-c)^2}{9}, \frac{(M-c)^2}{9}\right)\).
This example shows that we can find a rationalizable strategy for continuous strategy games as well.
Note that if the firms collude and fix production to \((M-c)/4\) (which ensures that the total production is the same as the monopoly level), it will result in a higher price and increased profits. However, this feature depends on the assumptions of the model, some of which are unrealistic. For a more realistic market model, consider the later example of Bertrand competition, where players set prices rather than production levels.
1.10 Beyond rationalizable strategies: Maxmin strategies
The concept of rationalizable strategies is attractive ut it makes strong assumption about the common knowledge of rationality of all players and even then does not always precribe a solution.
We now describe a notation of rationality of a player that does not rely on the rationality of other others; in fact, it makes the most pessimistic assessment of their potential behavior.
As an example, consider the following game.
| \(\mathsf{L}\) | \(\mathsf{R}\) | |||
| \(\mathsf{T}\) | \(2\) | \(1\) | \(2\) | \(-20\) |
| \(\mathsf{C}\) | \(3\) | \(0\) | \(-10\) | \(1\) |
| \(\mathsf{B}\) | \(-100\) | \(2\) | \(3\) | \(3\) |
In this game, the row player may prefer the strategy \(\mathsf{T}\) because it gaurantees a payoff of \(2\) and also ensures that the “risky” payoffs of \(-10\) and \(-100\) are avoided.
Similarly, the column player may prefer the strategy \(\mathsf{L}\) because it gaurantees a payoff of \(1\) and avoids the “risky” outcome of \(-20\).
This motivates the following question: What is the minimum payoff that player \(i\) can guarantee for himself?
If player \(i\) chooses strategy \(s_i\), the worst payoff that he can get is \[ \min_{s_{-i} \in \ALPHABET S_{-i}} u_i(s_i, s_{-i}). \] Player \(i\) can then choose the strategy \(s_i\) to maximize the above value. In other words, risregarding the possible rationality (or irrationality) of other players, \(P_i\) can gurantee for himself a payoff of \[ \underline v_i = \max_{s_i \in \ALPHABET S_i} \min_{s_{-i} \in \ALPHABET S_{-i}} u_i(s_i, s_{-i}). \] This quantity is called the maxmin value of player \(i\) (sometimes also called the security level). The strategy \(s_i^*\) that gurantees this value is called a maxmin strategy.
The maxmin strategy satisfies \[ \min_{s_{-i} \in \ALPHABET S_{-i}} u_i(s^*_i, s_{-i}) \ge \min_{s_{-i} \in \ALPHABET S_{-i}} u_i(s_i, s_{-i}) , \quad \forall s_i \in \ALPHABET S_i \] which is equivalent to \[ u_i(s_i^*, s_{-i}) \ge \underline v_i, \quad \forall s_{-i} \in \ALPHABET S_{-i}. \] Thus, if a player plays his maxmin strategy, his minimum guaranteed payoff equals to his maxmin value, irrespective of what the other players do.
Returning to our example, we have
| \(\mathsf{L}\) | \(\mathsf{R}\) | \(\min_{s_2 \in \ALPHABET S_2} u_1(s_1, s_2)\) | |||
| \(\mathsf{T}\) | \(2\) | \(1\) | \(2\) | \(-20\) | \(2\) |
| \(\mathsf{C}\) | \(3\) | \(0\) | \(-10\) | \(1\) | \(-10\) |
| \(\mathsf{B}\) | \(-100\) | \(2\) | \(3\) | \(3\) | \(-100\) |
| \(\min_{s_1 \in \ALPHABET S_1} u_2(s_1,s_2)\) | \(0\) | \(-20\) | \(2, 0\) | ||
- Some remarks
-
- The maxmin value of \(P_1\) is \(2\) (guaranteed by strategy \(\mathsf{T}\))
The maxmin value of \(P_2\) is \(0\) (guaranteed by strategy \(\mathsf{L}\)).
If both players play their maxmin strategies, the outcome is \((\mathsf{T}, \mathsf{L})\) which gives a payoff of \((2,1)\), in which player 2’s payoff is greater than her maxmin value.
In general, a player may have several maxmin strategies. In such a case, when the players play thier maxmin strategies, the payoff depends on which strategy they choose.
As an example consider the following game.
| \(\mathsf{L}\) | \(\mathsf{R}\) | \(\min_{s_2 \in \ALPHABET S_2} u_1(s_1, s_2)\) | |||
| \(\mathsf{T}\) | \(3\) | \(1\) | \(0\) | \(4\) | \(0\) |
| \(\mathsf{B}\) | \(2\) | \(3\) | \(1\) | \(1\) | \(1\) |
| \(\min_{s_1 \in \ALPHABET S_1} u_2(s_1,s_2)\) | \(1\) | \(1\) | \(1, 1\) | ||
- Some remarks
-
- The maxmin value of \(P_1\) is \(1\) (guaranteed by strategy \(\mathsf{B}\))
The maxmin value of \(P_2\) is \(1\) (guaranteed by either strategy \(\mathsf{L}\) or \(\mathsf{R}\)).
When both players play their maxmin strategies, the outcome is either \((\mathsf{B}, \mathsf{L})\) with a payoff of \((2,3)\) or is \((\mathsf{B}, \mathsf{R})\) with a payoff of \((1,1)\). Thus, the payoff depends on the strategy chosen by player 2.
1.11 Relation between maxmin strategies and dominant strategies
Theorem 1.1 A (strict or weak) dominant strategy of a player is also a maxmin strategy.
A dominant strategy of a player is his best respose to any strategy of the other player.
As an example, consider sealed bid second price autions. We had shown that truthful bidding is a weakly dominant strategy of each player. It can also be obsereved that truthful bidding guarantees a payoff of \(0\), which is equal to the maxmin value of each player.
Strategies obtained by iterative elimination are not maxmin strategies. Construct an example to show that.
Theorem 1.2 A strictly dominant strategy equilibrium is the unique vector of maxmin strategies.
A dominant strategy of a player is his best respose to any strategy of the other player.
As an example, consider prisoner’s dilemma.
| \(\mathsf{A}\) | \(\mathsf{R}\) | \(\min_{s_2 \in \ALPHABET S_2} u_1(s_1, s_2)\) | |||
| \(\mathsf{A}\) | \(-2\) | \(-2\) | \(0\) | \(-3\) | \(-2\) |
| \(\mathsf{R}\) | \(-3\) | \(0\) | \(-1\) | \(-1\) | \(-3\) |
| \(\min_{s_1 \in \ALPHABET S_1} u_2(s_1,s_2)\) | \(-2\) | \(-3\) | \(-2, -2\) | ||
As we can see, the maxmin strategy is \((\mathsf{A}, \mathsf{A})\), which is the same as the dominant strategy equilibrium.
Exercises
Exercise 1.1 Find the solution of the following games using iterative elimitation of strongly dominated strategies. Explicitly state the strategy that you are eliminating at each step and write the corresponding reduced game.
- Game \(\mathscr{G}_a\)
| \(\mathsf{L}\) | \(\mathsf{C}\) | \(\mathsf{R}\) | ||||
| \(\mathsf{T}\) | \(73\) | \(30\) | \(57\) | \(36\) | \(66\) | \(32\) |
| \(\mathsf{M}\) | \(80\) | \(26\) | \(35\) | \(12\) | \(32\) | \(54\) |
| \(\mathsf{B}\) | \(28\) | \(27\) | \(63\) | \(31\) | \(54\) | \(29\) |
- Game \(\mathscr{G}_b\)
| \(\mathsf{L}\) | \(\mathsf{C}\) | \(\mathsf{R}\) | ||||
| \(\mathsf{T}\) | \(-5\) | \(-1\) | \(2\) | \(2\) | \(3\) | \(3\) |
| \(\mathsf{M}\) | \(1\) | \(-3\) | \(1\) | \(2\) | \(1\) | \(1\) |
| \(\mathsf{B}\) | \(0\) | \(10\) | \(0\) | \(0\) | \(0\) | \(3\) |
Exercise 1.2 Find the solution of the following games using iterative elimitation of weakly dominated strategies. Explicitly state the strategy that you are eliminating at each step and write the corresponding reduced game. At each step, eliminate all weakly dominated strategies for a player.
- Game \(\mathscr{G}_a\)
| \(\mathsf{A}\) | \(\mathsf{B}\) | \(\mathsf{C}\) | \(\mathsf{D}\) | |||||
| \(\mathsf{T}\) | \(6\) | \(2\) | \(6\) | \(3\) | \(7\) | \(6\) | \(2\) | \(8\) |
| \(\mathsf{B}\) | \(8\) | \(5\) | \(6\) | \(9\) | \(4\) | \(6\) | \(4\) | \(7\) |
- Game \(\mathscr{G}_b\)
| \(\mathsf{W}\) | \(\mathsf{X}\) | \(\mathsf{Y}\) | \(\mathsf{Z}\) | |||||
| \(\mathsf{A}\) | \(3\) | \(7\) | \(0\) | \(13\) | \(4\) | \(5\) | \(5\) | \(3\) |
| \(\mathsf{B}\) | \(5\) | \(3\) | \(4\) | \(5\) | \(4\) | \(5\) | \(3\) | \(7\) |
| \(\mathsf{C}\) | \(4\) | \(5\) | \(3\) | \(7\) | \(4\) | \(5\) | \(5\) | \(3\) |
| \(\mathsf{D}\) | \(4\) | \(5\) | \(4\) | \(5\) | \(4\) | \(5\) | \(4\) | \(5\) |
Exercise 1.3 Find the solution of the following games using iterative elimitation of strongly dominated mixed strategies. Explicitly state the strategy that you are eliminating at each step and write the corresponding reduced game.
- Game \(\mathscr{G}_a\)
| \(\mathsf{L}\) | \(\mathsf{C}\) | \(\mathsf{R}\) | ||||
| \(\mathsf{T}\) | \(2\) | \(5\) | \(4\) | \(3\) | \(6\) | \(0\) |
| \(\mathsf{B}\) | \(1\) | \(1\) | \(5\) | \(2\) | \(1\) | \(4\) |
Exercise 1.4 For each of the games in Exercise 1.1, Exercise 1.2, and Exercise 1.3, find the maxmin strategies and the maxmin value of both players.
Exercise 1.5 Consider the following two player game: \(\ALPHABET S_1 = \ALPHABET S_2 = \{1, \dots, 100 \}\) and \[ u(s_1, s_2) = \begin{cases} (s_1, s_2), & \text{if $s_1 + s_2 < 100$} \\ (s_1, 100-s_1), & \text{if $s_1 + s_2 > 100$ and $s_1 < s_2$}\\ (100-s_2, s_2), & \text{if $s_1 + s_2 > 100$ and $s_2 < s_1$}\\ (50,50), & \text{if $s_1 + s_2 > 100$ and $s_1 = s_2$} \end{cases}\] Find the rationalizable strategies using IEWDS.