Algorithmic Game Theory: Strategic Games, Support Enumeration, and Nash's Theorem

Strategic Form Games and Fundamental Solution Concepts

• Strategic Form Representation:

  • A strategic (or normal) form game is formally defined as a tuple $\Gamma = (N, (S_i)_{i \in N}, (u_i)_{i \in N})$:

    • $N = \{1, 2, \dots, n\}$ is the finite set of players.

    • $S_i$ is the set of actions (or pure strategies) available to player $i$.

    • $S = \prod_{i \in N} S_i$ is the set of all action profiles (joint actions).

    • $u_i: S \to \mathbb{R}$ is the payoff (utility) function for player $i$.

  • In a two-player game, actions and utilities are represented via a payoff matrix where the row player is denoted by $i$ and the column player is denoted by $j$.

  • In each round, player $i$ selects a row and player $j$ selects a column. The payoff resulting from the intersection of row strategy $s_i$ and column strategy $s_j$ is expressed as an ordered pair $(x, y)$, where $x = u_i(s_i, s_j)$ represents the payoff to the row player, and $y = u_j(s_i, s_j)$ represents the payoff to the column player.

• Dominant and Dominated Strategies:

  • Strategy Dominance: A strategy $s_1 \in S_i$ dominates a strategy $s_2 \in S_i$ if, for every possible choice of the opponent player $j$, player $i$ achieves at least as high a payoff playing $s_1$ as playing $s_2$, and for at least one choice of player $j$, player $i$ achieves a strictly higher payoff playing $s_1$ than playing $s_2$:

    • $\forall s_j \in S_j, \quad u_i(s_1, s_j) \ge u_i(s_2, s_j)$

    • $\exists s_j \in S_j, \quad u_i(s_1, s_j) > u_i(s_2, s_j)$

  • Dominant Strategy: A strategy $s_1 \in S_i$ is defined as dominant if it dominates every other strategy available to player $i$ in $S_i$.

  • Rationality Criterion: A rational player will never play a dominated strategy. Consequently, dominated strategies can be eliminated through iterated deletion of dominated strategies (IDDS) to reduce the game's complexity.

  • Analytical Caveat: An undominated strategy is not guaranteed to be unique in every scenario; multiple undominated strategies can coexist.

• Pure Nash Equilibrium:

  • Informal Definition: Two strategies $s_1$ and $s_2$ constitute a Nash equilibrium if:

    1. Under the assumption that player $i$ plays $s_1$, player $j$ can achieve no higher payoff by selecting any strategy other than $s_2$.

    2. Under the assumption that player $j$ plays $s_2$, player $i$ can achieve no higher payoff by selecting any strategy other than $s_1$.

  • Formal Definition: Let $\mathbf{s} = (s_i)_{i \in N} \in S$ be an action profile, and let $(s_i', \mathbf{s}_{-i})$ be the action profile resulting from $\mathbf{s}$ when player $i \in N$ unilaterally deviates to action $s_i' \in S_i$, while all other players $N \setminus \{i\}$ maintain their chosen actions. An action profile $\mathbf{s}^* \in S$ is a pure Nash equilibrium of the strategic game $\Gamma = (N, (S_i)_{i \in N}, (u_i)_{i \in N})$ if and only if, for all players $i \in N$:         $u_i(\mathbf{s}^*) \ge u_i(s_i', \mathbf{s}_{-i}^*) \quad \forall s_i' \in S_i$

  • At a Nash equilibrium, no player possesses an incentive to unilaterally deviate.

  • Fundamental Limitations:

    1. A pure Nash equilibrium does not exist in every game scenario.

    2. Games may exhibit multiple pure Nash equilibria, leading to coordination dilemmas.

• Pareto Efficiency (Pareto Optimality):

  • Pareto efficiency evaluates the collective quality of an outcome:

    • An outcome $\omega \in S$ is Pareto efficient (or Pareto optimal) if there exists no alternative outcome $\omega' \in S$ that strictly improves at least one player's utility without strictly decreasing the utility of any other player:             $\neg \exists \omega' \in S \text{ such that } (\forall i \in N, \, u_i(\omega') \ge u_i(\omega)) \land (\exists j \in N, \, u_j(\omega') > u_j(\omega))$

    • An outcome is Pareto inefficient if an alternative outcome exists that makes at least one player strictly better off without causing any participant to be worse off.

• Maximizing Social Welfare:

  • Social Welfare Definition: The social welfare of an outcome $\omega \in S$, denoted $sw(\omega)$, is the aggregate sum of utilities accrued across all players:         $sw(\omega) = \sum_{i \in N} u_i(\omega)$

  • Social Welfare Maximization: A solution maximizes social welfare if it maximizes this aggregate sum across all feasible outcomes in $S$.

  • Equity and Fairness Limitations: Maximizing aggregate utility does not ensure fairness or distributive justice. For example, an outcome distributing $£101$ to a single player and $£0$ to 100 other players yields $sw = 101$, whereas distributing $£1$ to each of 100 players yields $sw = 100$. Social welfare maximization is most suitable when all participants belong to or act on behalf of the same user, entity, or collective owner.

Classical 2x2 Strategic Games

• The Prisoner's Dilemma:

  • Two suspects must choose whether to Defect ($D$) or Cooperate ($C$).

*   **Payoff Structure:**
    *   $(D, D) = (2, 2)$
    *   $(D, C) = (5, 0)$
    *   $(C, D) = (0, 5)$
    *   $(C, C) = (3, 3)$
*   **Strategic Analysis:**
    *   **Dominant Strategy:** For player $i$, if player $j$ plays $D$, playing $D$ yields $2$ versus $0$ from $C$. If player $j$ plays $C$, playing $D$ yields $5$ versus $3$ from $C$. Thus, Defect ($D$) is a strictly dominant strategy for both players.
    *   **Nash Equilibrium:** The unique pure Nash equilibrium is $(D, D)$ with payoffs $(2, 2)$.
    *   **Pareto Efficiency:** $(D, D)$ is the *only* outcome in the game that is Pareto inefficient, as $(C, C)$ provides strictly greater utility to both players ($3 > 2$). The outcomes $(D, C)$, $(C, D)$, and $(C, C)$ are all Pareto efficient.
    *   **Social Welfare:** The social welfare values are $sw(D, D) = 4$, $sw(D, C) = 5$, $sw(C, D) = 5$, and $sw(C, C) = 6$. The intuitive cooperative outcome $(C, C)$ uniquely maximizes social welfare.

• The Game of Chicken:

  • Illustrates dangerous brinkmanship, modeled on teenage street-racing challenges (e.g., James Dean in Rebel Without a Cause).

*   **Payoff Structure:**
    *   $(D, D) = (1, 1)$
    *   $(D, C) = (4, 2)$
    *   $(C, D) = (2, 4)$
    *   $(C, C) = (3, 3)$
*   **Structural Comparison to Prisoner's Dilemma:**
    *   In the Prisoner's Dilemma, the sucker's payoff (cooperating while the opponent defects, yielding $0$) is the most feared outcome.
    *   In the Game of Chicken, mutual defection (head-on collision, yielding $1, 1$) is the most catastrophic and feared outcome.
    *   Neither action dominates the other: If player $j$ plays $D$, player $i$ prefers $C$ ($2 > 1$); if player $j$ plays $C$, player $i$ prefers $D$ ($4 > 3$).
    *   The game features two pure Nash equilibria: $(D, C)$ and $(C, D)$.

• The Battle of the Sexes:

  • A coordination game between a girl ($g$) and a boy ($b$) deciding between attending the Opera ($O$) or a Football match ($F$).

  • Payoff Matrix:

    • $(O, O) = (3, 2)$

    • $(O, F) = (0, 0)$

    • $(F, O) = (0, 0)$

    • $(F, F) = (2, 3)$

  • Pure Nash Equilibria:

    • Both choosing Opera: $(O, O)$, returning $(3, 2)$.

    • Both choosing Football: $(F, F)$, returning $(2, 3)$.

    • Inherent Asymmetry: Each pure equilibrium favors one player over the other, creating strategic conflict within coordination.

  • Mixed Nash Equilibrium:

    • Let $p_b(O)$ be the probability boy chooses Opera, and $p_g(O)$ be the probability girl chooses Opera.

    • Equating boy's expected utility across pure actions:             $u_b(O) = 2 \cdot p_g(O) + 0 \cdot (1 - p_g(O)) = 2 p_g(O)$             $u_b(F) = 0 \cdot p_g(O) + 3 \cdot (1 - p_g(O)) = 3 - 3 p_g(O)$             $2 p_g(O) = 3 - 3 p_g(O) \implies 5 p_g(O) = 3 \implies p_g(O) = \frac{3}{5}, \quad p_g(F) = \frac{2}{5}$

    • Equating girl's expected utility across pure actions:             $u_g(O) = 3 \cdot p_b(O) + 0 \cdot (1 - p_b(O)) = 3 p_b(O)$             $u_g(F) = 0 \cdot p_b(O) + 2 \cdot (1 - p_b(O)) = 2 - 2 p_b(O)$             $3 p_b(O) = 2 - 2 p_b(O) \implies 5 p_b(O) = 2 \implies p_b(O) = \frac{2}{5}, \quad p_b(F) = \frac{3}{5}$

    • Evaluation: The mixed equilibrium provides equal treatment, but the expected utility for each player is:             $u_g = 3 \left(\frac{2}{5}\right) = \frac{6}{5} = 1.2 < 2$             $u_b = 2 \left(\frac{3}{5}\right) = \frac{6}{5} = 1.2 < 2$             Both players receive strictly lower expected payoff than in either pure Nash equilibrium.

• Matching Pennies (Asymmetric Zero-Sum Formulation):

  • Two players simultaneously call Heads ($H$) or Tails ($T$). If their choices match, player $i$ wins; if they differ, player $j$ wins.

  • Payoff Matrix:

    • $(H, H) = (1, -1)$

    • $(H, T) = (-1, 1)$

    • $(T, H) = (-1, 1)$

    • $(T, T) = (1, -1)$

  • Pure Equilibrium Non-Existence: For any action pair, one player always has an incentive to deviate. No pure Nash equilibrium exists.

  • Mixed Nash Equilibrium:         $p_i(H) = \frac{1}{2}, \quad p_i(T) = \frac{1}{2}$         $p_j(H) = \frac{1}{2}, \quad p_j(T) = \frac{1}{2}$

• Rock, Paper, Scissors (Symmetric Formulation):

  • Players simultaneously choose Rock ($R$), Paper ($P$), or Scissors ($S$).

  • Payoff Matrix:

    • $(R, R) = (0, 0), \quad (R, P) = (0, 1), \quad (R, S) = (1, 0)$

    • $(P, R) = (1, 0), \quad (P, P) = (0, 0), \quad (P, S) = (0, 1)$

    • $(S, R) = (0, 1), \quad (S, P) = (1, 0), \quad (S, S) = (0, 0)$

  • The game contains no pure Nash equilibrium because any deterministic choice can be exploited by the opponent.

Mixed Strategies and Expected Payoffs

• Mixed Strategy Formalization:

  • A mixed strategy $p_i$ for player $i \in N$ is a probability distribution over their finite set of pure actions $S_i$:         $p_i: S_i \to [0, 1]$         $\sum_{s_i \in S_i} p_i(s_i) = 1$

  • The set of all mixed strategies for player $i$ is the probability simplex denoted by $\Delta(S_i)$.

  • A pure strategy is a degenerate mixed strategy that places probability $1$ on a specific action $s_i \in S_i$ (i.e., $p_i(s_i) = 1$), denoted simply by $s_i$.

• Strategy Profiles:

  • A mixed strategy profile is a vector representing one mixed strategy for every player:         $\mathbf{p} = (p_i)_{i \in N} \in \prod_{i \in N} \Delta(S_i)$         or $\pi = (p_1, p_2, \dots, p_n)$.

  • $\pi_{-i} = (p_1, \dots, p_{i-1}, p_{i+1}, \dots, p_n)$ denotes the strategy profile of all players excluding player $i$.

  • $(p_i', \pi_{-i})$ designates the profile where player $i$ unilaterally adopts strategy $p_i'$ while all other players remain at $\pi_{-i}$.

• Expected Payoff Computation:

  • Under the assumption that players randomize independently, the probability of an action profile $(s_1, \dots, s_n) \in S$ occurring is the product of the individual probabilities $\prod_{j=1}^n p_j(s_j)$.

  • The expected payoff $u_i(\mathbf{p})$ of player $i$ under profile $\mathbf{p}$ is:         $u_i(\mathbf{p}) = \sum_{s_1 \in S_1} \cdots \sum_{s_n \in S_n} \left( \prod_{j=1}^n p_j(s_j) \right) u_i(s_1, \dots, s_n)$

• Numerical Example in Rock, Paper, Scissors:

  • Let player $i$ adopt mixed strategy $p_R = 0.2$, $p_P = 0.5$, $p_S = 0.3$.

  • Let player $j$ adopt mixed strategy $p_R = 0.4$, $p_P = 0.4$, $p_S = 0.2$.

*   Player $j$ receives a payoff of $1$ only when winning: $(R, P)$, $(P, S)$, and $(S, R)$.
*   Probability of $(R, P)$: $p_i(R) \times p_j(P) = 0.2 \times 0.4 = 0.08$.
*   Probability of $(P, S)$: $p_i(P) \times p_j(S) = 0.5 \times 0.2 = 0.10$.
*   Probability of $(S, R)$: $p_i(S) \times p_j(R) = 0.3 \times 0.4 = 0.12$.
*   Expected utility of player $j$:

        $u_j(\mathbf{p}) = 0.08 + 0.10 + 0.12 = 0.30$ * Exploitation of Known Probabilities: If player $i$'s strategy is fixed at $(0.2, 0.5, 0.3)$, player $j$'s expected utilities for pure actions are: * Playing $R$: beats $S$ ($0.3$), so $u_j(R) = 0.3$. * Playing $P$: beats $R$ ($0.2$), so $u_j(P) = 0.2$. * Playing $S$: beats $P$ ($0.5$), so $u_j(S) = 0.5$. * The optimal response for player $j$ is to play Scissors as a pure action ($u_j = 0.5$). * Unique Mixed Nash Equilibrium: The only mixed strategy profile immune to exploitation is the uniform distribution:         $p_i(R) = p_i(P) = p_i(S) = \frac{1}{3}, \quad p_j(R) = p_j(P) = p_j(S) = \frac{1}{3}$

Best Response and Support Characterization

• Best Response Definition:

  • A strategy $p_i \in \Delta(S_i)$ is a best response of player $i$ to opponents' strategies $\pi_{-i}$ if and only if:         $u_i(p_i, \pi_{-i}) \ge u_i(p_i', \pi_{-i}) \quad \forall p_i' \in \Delta(S_i)$

• Mixed Nash Equilibrium Definition:

  • A strategy profile $\pi^* = (p_1^*, \dots, p_n^*)$ is a mixed Nash equilibrium if, for every player $i \in N$, strategy $p_i^*$ is a best response to $\pi_{-i}^*$:         $u_i(p_i^*, \pi_{-i}^*) \ge u_i(p_i, \pi_{-i}^*) \quad \forall p_i \in \Delta(S_i), \; \forall i \in N$

• The Support of a Strategy:

  • The support of a mixed strategy distribution $p_i$, denoted $\text{supp}(p_i)$, is the subset of pure strategies assigned strictly positive probability:         $\text{supp}(p_i) = \{s_k \in S_i \mid p_i(s_k) > 0\}$

• The Indifference Principle (Fundamental Characterization):

  • Let $p_i$ be a best response to $\pi_{-i}$. For any pure strategy $s_k \in S_i$:         $u_i(p_i, \pi_{-i}) \ge u_i(s_k, \pi_{-i})$

  • Because the expected payoff is linear in the probabilities:         $u_i(p_i, \pi_{-i}) = \sum_{s_k \in S_i} p_i(s_k) u_i(s_k, \pi_{-i}) \le \max_{s_k \in S_i} u_i(s_k, \pi_{-i})$

  • Equality holds if and only if every pure strategy that receives positive probability attains the maximum expected utility:         $p_i(s_k) > 0 \implies s_k \in \operatorname{argmax}_{s \in S_i} u_i(s, \pi_{-i})$

  • Indifference Property: In any Nash equilibrium, a player is indifferent among all pure strategies in the support of their equilibrium strategy. Each pure strategy in the support must produce the exact same expected payoff, and this payoff must be greater than or equal to the expected payoff of any strategy outside the support.

Support Enumeration Algorithm

• Theoretical Principle:

  • To find all Nash equilibria of a finite game, one can iterate through all possible non-empty candidate supports for each player, write down the corresponding linear systems of equations, solve them, and verify whether the solutions satisfy all required constraints.

• Step-by-Step Procedure:

  1. Enumerate Supports: For each player $i$, select a non-empty subset $D_i \subseteq S_i$. A candidate support profile is given by the Cartesian product:         $D = D_1 \times D_2 \times \cdots \times D_n$

  2. Formulate Linear Equations:

     • Equal Return within Support: For each player $i$, all strategies $s_i \in D_i$ must yield the same expected payoff, denoted by the unknown scalar $w_i$:             $u_i(s_i, \mathbf{p}_{-i}) = w_i \quad \forall s_i \in D_i$

     • Zero Probability Outside Support:             $p_i(s_i) = 0 \quad \forall s_i \in S_i \setminus D_i$

     • Probability Normalization:             $\sum_{s_i \in D_i} p_i(s_i) = 1$

  3. Count Unknowns and Equations:

     • For each player $i$, the unknowns are the probabilities $p_i(s_i)$ for $s_i \in D_i$ (total $|D_i|$) plus the expected payoff $w_i$, totaling $|D_i| + 1$ unknowns.

     • The equations are $|D_i|$ payoff equalities plus $1$ normalization condition, totaling $|D_i| + 1$ equations.

     • Summing over all players, the number of equations matches the number of unknowns.

  4. Solve the Linear Systems: Solve the equations using standard linear algebra.

  5. Apply Validation Tests:

     • Test 1 (Solvability): If the linear system has no solution, discard the support.

     • Test 2 (Probability Bounds): Ensure all computed probabilities satisfy strictly positive support constraints: $p_i(s_i) > 0$ for $s_i \in D_i$, and $\sum_{s_i \in D_i} p_i(s_i) = 1$. If any probability is negative or exceeds $1$, discard the support.

     • Test 3 (Maximality / No Profitable Deviation): Verify that unsupported pure strategies do not yield higher payoffs:             $u_i(s_i', \mathbf{p}_{-i}) \le w_i \quad \forall s_i' \in S_i \setminus D_i$             If an unsupported strategy yields an expected utility strictly exceeding $w_i$, the candidate is discarded.

  6. By Nash's Theorem, at least one candidate support profile will satisfy all conditions.

Detailed Support Enumeration Examples

• Matching Pennies Support Enumeration:

  • Absence of Pure or Semi-Mixed Equilibria:

    • If player 1 chooses a pure action $H$, player 2's best response is $T$. If player 2 plays $T$, player 1's best response is $T$, which contradicts player 1 playing $H$. Thus, no pure Nash equilibrium exists.

    • If one player plays a pure strategy and the other plays a mixed strategy, the pure player's choice induces a unique pure best response from the other player, collapsing back into a pure profile and creating a contradiction.

    • Consequently, any equilibrium must have full support:             $p_1(H) > 0, \quad p_1(T) > 0, \quad p_2(H) > 0, \quad p_2(T) > 0$

  • Deriving Equations:

    • Player 2's expected payoffs must be equal for $H$ and $T$:             $u_2(H, p_1) = u_2(T, p_1)$             $(-1) \cdot p_1(H) + (1) \cdot p_1(T) = (1) \cdot p_1(H) + (-1) \cdot p_1(T)$             $p_1(T) - p_1(H) = p_1(H) - p_1(T) \implies 2 p_1(T) = 2 p_1(H) \implies p_1(H) = p_1(T)$

    • Normalization condition: $p_1(H) + p_1(T) = 1$.

    • Solving gives $p_1(H) = p_1(T) = \frac{1}{2}$.

    • By symmetry, the exact same equations hold for player 2, yielding $p_2(H) = p_2(T) = \frac{1}{2}$.

• Analysis of a Two-Player Game with Dominated Strategy Deletion:

  • Consider a game where player 1 initially has actions $\{T, B, X\}$ and player 2 has actions $\{L, M, R\}$.

  • Dominance Check: Strategy $X$ for player 1 is strictly dominated by strategy $B$.

  • Because $u_1(B, s_2) > u_1(X, s_2)$ for all $s_2 \in S_2$, strategy $X$ can never yield an expected utility as high as $B$ in any equilibrium.

  • Eliminating $X$ reduces player 1's action set to $\{T, B\}$, turning the game into a $2 \times 3$ matrix.

  • Support Combinatorics:

    • Without reduction, player 1 would have $2^3 - 1 = 7$ possible supports, and player 2 would have $2^3 - 1 = 7$ supports, creating $7 \times 7 = 49$ support profiles.

    • After deleting $X$, player 1 has $2^2 - 1 = 3$ candidate supports: $\{T\}$, $\{B\}$, or $\{T, B\}$.

    • Player 2 has $2^3 - 1 = 7$ candidate supports: 3 of size 1 ($\{L\}$, $\{M\}$, $\{R\}$), 3 of size 2 ($\{L, M\}$, $\{M, R\}$, $\{L, R\}$), and 1 of size 3 ($\{L, M, R\}$).

    • Total candidate pairs to examine: $3 \times 7 = 21$.

• Elimination of Pure Strategy Supports (Size 1):

  • Case $D_1 = \{T\}$: Player 2's best response to $T$ is $M$. Player 1's best response to $M$ is $B$. Contradiction ($T \ne B$).

  • Case $D_1 = \{B\}$: Player 2's best response to $B$ is $L$. Player 1's best response to $L$ is $T$. Contradiction ($B \ne T$).

  • Case $D_2 = \{L\}$: Player 1's best response to $L$ is $T$. Player 2's best response to $T$ is $M$. Contradiction ($L \ne M$).

  • Case $D_2 = \{M\}$: Player 1's best response to $M$ is $B$. Player 2's best response to $B$ is $L$. Contradiction ($M \ne L$).

  • Case $D_2 = \{R\}$: Player 1's best response to $R$ is $B$. Player 2's best response to $B$ is $L$. Contradiction ($R \ne L$).

  • Conclusion: There are no pure Nash equilibria, nor can either player use a pure strategy in a mixed equilibrium. Thus, player 1's support must be $D_1 = \{T, B\}$.

• Testing Mixed Support Candidates:

  • Candidate 1: $D_1 = \{T, B\}$, $D_2 = \{L, M, R\}$.

    • Equating player 2's expected utilities across all three strategies:             $u_2(L, p_1) = w_2, \quad u_2(M, p_1) = w_2, \quad u_2(R, p_1) = w_2$             $p_1(T) + p_1(B) = 1$

    • Equating $u_2(L, p_1)$ and $u_2(M, p_1)$ gives:             $2 p_1(T) + 7 p_1(B) = 7 p_1(T) + 2 p_1(B)$             $5 p_1(B) = 5 p_1(T) \implies p_1(T) = p_1(B)$

    • Evaluating payoff equalities with $p_1(T) = p_1(B)$, one equation yields:             $9 p_1(T) = w_2$             While another equation yields:             $11 p_1(T) = w_2$

    • Equating them requires $9 p_1(T) = 11 p_1(T) \implies 2 p_1(T) = 0 \implies p_1(T) = 0$.

    • This contradicts $p_1(T) + p_1(B) = 1$ with $p_1(T) = p_1(B)$.

    • Result: No solution exists. Discard candidate.

  • Candidate 2: Support yields negative probabilities.

    • Solving the linear system for another subset yields:             $p_2(M) = -\frac{1}{4}, \quad p_2(R) = \frac{5}{4}$

    • Result: Violates probability constraints ($p_i(s) \in [0, 1]$). Discard candidate.

  • Candidate 3: $D_1 = \{T, B\}$, $D_2 = \{L, M\}$.

    • Solving the linear system yields valid probabilities with expected payoffs:             $w_1 = w_2 = 4.5$

    • Maximality Check: Test the unsupported strategy $R$ for player 2:             Evaluate $u_2(R, p_1)$. If $u_2(R, p_1) > 4.5$, player 2 has an incentive to deviate to $R$.

    • Result: The check reveals $u_2(R, p_1) > w_2$. Discard candidate.

  • Candidate 4: $D_1 = \{T, B\}$, $D_2 = \{L, R\}$.

    • Player 1 expected utility balance:             $7 p_2(L) + 3 p_2(R) = w_1$             $2 p_2(L) + 4 p_2(R) = w_1$

    • Equating both expressions:             $7 p_2(L) + 3 p_2(R) = 2 p_2(L) + 4 p_2(R)$             $5 p_2(L) = p_2(R)$

    • Using $p_2(L) + p_2(R) = 1$:             $5 p_2(L) + p_2(L) = 1 \implies 6 p_2(L) = 1 \implies p_2(L) = \frac{1}{6}, \quad p_2(R) = \frac{5}{6}$

    • Player 2 expected utility balance:             $u_2(L, p_1) = u_2(R, p_1) = w_2$             $2 p_1(T) + 7 p_1(B) = w_2$             $p_1(T) + p_1(B) = 1$

    • Solving yields valid probabilities in $[0, 1]$ and an equilibrium payoff of $w_2 = \frac{16}{3}$.

    • Maximality Check: Calculate player 2's payoff for the unsupported strategy $M$:             $u_2(M, p_1) \le \frac{16}{3}$

    • Result: Because no unsupported strategy yields a higher payoff, this support defines a valid mixed Nash equilibrium.

Nash's Existence Theorem and Fixed Point Proof

• Theorem Statement (John Forbes Nash Jr., 1950):

  • Every strategic game in which every player has a finite set of actions has at least one Nash equilibrium in mixed strategies.

• Geometric and Topological Foundation:

  • Let $S_i$ be the finite action set of player $i$, and let $d = \sum_{i \in N} |S_i|$.

  • A mixed strategy profile $\pi = (p_1, \dots, p_n)$ is an element of the Euclidean space $\mathbb{R}^d$, constrained by:         $\forall i \in N, \quad \sum_{s \in S_i} p_i(s) = 1 \quad \text{and} \quad p_i(s) \ge 0$

  • The total strategy space $\Delta = \prod_{i \in N} \Delta(S_i) \subset \mathbb{R}^d$ is a non-empty, compact (closed and bounded), and convex subset of $\mathbb{R}^d$.

• Brouwer's Fixed Point Theorem:

  • Theorem: Let $K \subset \mathbb{R}^d$ be a non-empty, compact, and convex set. Any continuous function $f: K \to K$ has at least one fixed point; that is, there exists an $\mathbf{x}^* \in K$ such that $f(\mathbf{x}^*) = \mathbf{x}^*$.

  • One-Dimensional Demonstration ($d = 1$):

    • Let $f: [0, 1] \to [0, 1]$ be a continuous function.

    • If $f(0) = 0$, then $0$ is a fixed point.

    • If $f(1) = 1$, then $1$ is a fixed point.

    • If neither, then $f(0) > 0$ and $f(1) < 1$.

    • Define $g(x) = f(x) - x$. The function $g$ is continuous, with $g(0) = f(0) - 0 > 0$ and $g(1) = f(1) - 1 < 0$.

    • By the Intermediate Value Theorem, there must exist some $x^* \in (0, 1)$ such that $g(x^*) = 0$, meaning $f(x^*) = x^*$.

    • Geometrically, the graph of $f(x)$ starts on the left boundary above the diagonal line $y = x$ and ends on the right boundary below it, which guarantees that it must intersect the line $y = x$.

*   **Necessity of Topological Conditions:**
    *   *Non-convex sets:* Brouwer's theorem fails. For example, consider an annulus in $\mathbb{R}^2$ centered at the origin: rotating the annulus by an angle $\theta \in (0, 2\pi)$ maps the set continuously to itself, yet no point remains fixed.
    *   *Non-compact (open) sets:* Consider the open interval $(0, 1)$ and the continuous function $f(x) = x^2$. For all $x \in (0, 1)$, $x^2 < x$, so there is no fixed point within the domain.

• Detailed Construction of Nash's Continuous Function:

  • Gain Function: For each player $i \in N$ and each pure strategy $s \in S_i$, define the unilateral gain function:         $\text{gain}_{i, s}(\pi) = \max\{0, \, u_i(s, \pi_{-i}) - u_i(\pi)\}$         This function quantifies the payoff increase that player $i$ achieves by unilaterally switching from their current mixed strategy $p_i$ to the pure strategy $s$, returning $0$ if switching yields no improvement.

  • Strategy Modification Function: Define player $i$'s updated strategy distribution $q_i$ as:         $q_i(s) = \frac{p_i(s) + \text{gain}_{i, s}(\pi)}{N_i(\pi)}$         where the normalization factor $N_i(\pi)$ is:         $N_i(\pi) = 1 + \sum_{s' \in S_i} \text{gain}_{i, s'}(\pi)$         Because $p_i(s) \ge 0$ and $\text{gain}_{i, s}(\pi) \ge 0$, we have $N_i(\pi) \ge 1$, which prevents division by zero.         Summing $q_i(s)$ over all $s \in S_i$ confirms that $q_i$ is a valid probability distribution:         $\sum_{s \in S_i} q_i(s) = \frac{\sum_{s \in S_i} p_i(s) + \sum_{s \in S_i} \text{gain}_{i, s}(\pi)}{1 + \sum_{s' \in S_i} \text{gain}_{i, s'}(\pi)} = \frac{1 + \sum_{s \in S_i} \text{gain}_{i, s}(\pi)}{1 + \sum_{s' \in S_i} \text{gain}_{i, s'}(\pi)} = 1$

  • Composite Mapping: Define the global function $f: \Delta \to \Delta$ as:         $f(\pi) = (q_1, q_2, \dots, q_n)$

  • Continuity: Payoff functions $u_i(\pi)$ are multilinear polynomials in the probability variables and are therefore continuous. Because $u_i$ is continuous, each $\text{gain}_{i, s}(\pi)$ is continuous, which ensures that both $N_i(\pi)$ and $f(\pi)$ are continuous.

• Equivalence of Fixed Points and Nash Equilibria:

  • By Brouwer's Fixed Point Theorem, there exists at least one profile $\pi^* \in \Delta$ such that $f(\pi^*) = \pi^*$.

  • At this fixed point, for every player $i$ and strategy $s \in S_i$:         $p_i^*(s) = \frac{p_i^*(s) + \text{gain}_{i, s}(\pi^*)}{1 + \sum_{s' \in S_i} \text{gain}_{i, s'}(\pi^*)}$         $p_i^*(s) \left( 1 + \sum_{s' \in S_i} \text{gain}_{i, s'}(\pi^*) \right) = p_i^*(s) + \text{gain}_{i, s}(\pi^*)$         $p_i^*(s) \sum_{s' \in S_i} \text{gain}_{i, s'}(\pi^*) = \text{gain}_{i, s}(\pi^*)$

  • Proof that Gain Must Be Zero:

    • Observe that player $i$'s expected payoff is the weighted average of payoffs from pure strategies:             $u_i(\pi^*) = \sum_{s \in S_i} p_i^*(s) u_i(s, \pi_{-i}^*)$

    • It is impossible for every pure strategy to perform strictly better than the average. Therefore, there must exist at least one strategy $s^* \in S_i$ with $p_i^*(s^*) > 0$ such that:             $u_i(s^*, \pi_{-i}^*) \le u_i(\pi^*)$

    • For this strategy $s^*$, the definition of gain gives:             $\text{gain}_{i, s^*}(\pi^*) = \max\{0, \, u_i(s^*, \pi_{-i}^*) - u_i(\pi^*)\} = 0$

    • Substituting this back into the fixed point identity for $s^*$:             $p_i^*(s^*) \sum_{s' \in S_i} \text{gain}_{i, s'}(\pi^*) = \text{gain}_{i, s^*}(\pi^*) = 0$

    • Because $p_i^*(s^*) > 0$, the summation must evaluate to zero:             $\sum_{s' \in S_i} \text{gain}_{i, s'}(\pi^*) = 0$

    • Since $\text{gain}_{i, s'}(\pi^*) \ge 0$ for all $s'$, every term in the sum must be zero:             $\text{gain}_{i, s}(\pi^*) = 0 \quad \forall s \in S_i, \; \forall i \in N$

  • Conclusion: Because $\text{gain}_{i, s}(\pi^*) = \max\{0, \, u_i(s, \pi_{-i}^*) - u_i(\pi^*)\} = 0$, no pure strategy $s \in S_i$ yields an expected utility strictly greater than $u_i(\pi^*)$. Consequently, no player can unilaterally deviate to any pure or mixed strategy to improve their payoff, establishing that $\pi^*$ is a Nash equilibrium.