Lecture 06.1: Game Theory and Nash Equilibrium

Adversarial search algorithms are fundamental in Artificial Intelligence when agents operate in environments with competing interests and conflicting goals. Unlike single-agent pathfinding, adversarial search models strategic decision-making in competitive settings where an agent's success depends on anticipating and countering the actions of opposing agents.

The ultimate goal of adversarial search is to formulate optimal strategies that pursue one's own objectives while responding effectively to an adversary's moves.

Fundamentals of Adversarial Search

Key Challenges

1. Strategic Decision-Making under Opposition: Formulating optimal policies when adversaries actively attempt to minimize your payoff or defeat your goal.
2. Balancing Progress and Defense: Simultaneously making forward progress toward individual objectives while defending against opponent counter-attacks.

Application Domains

• Strategic Games: Chess, Go, Checkers, Tic-Tac-Toe.
• Competitive Decision-Making: Auction Design (e.g., oil drilling rights), Wireless Spectrum Allocation, Bankruptcy Proceedings, Product Development & Competitive Pricing, and Strategic National Defense.

---

Game Theory as a Foundation

Game Theory studies mathematical models of strategic interactions among rational decision-makers. It models scenarios where each agent's decisions influence—and are influenced by—the actions of others.

Game theory was initially developed for zero-sum games, where one player's gain is exactly equal to another player's loss. Broadly, games are categorized into:

• Cooperative Games: Players can form enforceable, binding agreements.
• Competitive (Non-Cooperative) Games: No binding commitments exist; players act independently to maximize their own utility.

[!NOTE] Mechanism Design (Inverse Game Theory): While traditional game theory takes game rules as given and predicts player behavior, Mechanism Design seeks to design the rules and payoffs of a game so that self-interested rational agents naturally act in a way that leads to a desired system-wide outcome.

Single-Move (Simultaneous) Games

In single-move games, all players choose their actions independently without prior knowledge of others' choices. The outcome is determined by the combination of these single-shot decisions.

[!IMPORTANT] Actions in a simultaneous game do not need to occur at the exact same physical second. The critical requirement is that choices are made independently and without prior knowledge of the opponent's choice.

---

Key Terminologies

• Players (Agents): Rational decision-makers (humans, bots, or AI systems).
• Actions: Choices available to players. Different players may or may not have the same set of available actions.
• Payoff Function ($U_i$): A mapping that assigns a numerical utility (reward or penalty) to each player based on the complete combination of actions taken by all players.
• Strategic Form (Normal Form): Organizing payoffs into a matrix format capturing utility for all possible action profiles.

Example Payoff Matrix: Two-Finger Morra

In the game of Two-Finger Morra, two players (Even $E$ and Odd $O$) simultaneously show either one or two fingers. If the sum is even, player $E$ wins points equal to the total fingers shown; if odd, player $O$ wins.

Strategies: Pure vs. Mixed

• Strategy (Policy): The course of action a player commits to in a game.
• Pure Strategy: A deterministic approach where a player selects a single, unchanging action.
• Mixed Strategy: A probabilistic approach where a player selects actions based on a probability distribution.
  • Notation: $[p: a; (1-p): b]$, or for Two-Finger Morra: $[0.5: \text{one}; 0.5: \text{two}]$.
• Strategy Profile: A set $S = (s_1, s_2, \dots, s_n)$ assigning a specific strategy to each player in the game.
• Outcome: The resulting numerical utility vector $(U_1(S), U_2(S), \dots, U_n(S))$.

[!IMPORTANT] The Core Problem of Game Theory: A solution to a game is a strategy profile in which each player adopts a rational strategy. The central challenge of game theory is defining what "rational" means when each agent only controls their own piece of the strategy profile that determines the outcome.

---

The Prisoner's Dilemma & Solution Concepts

Consider the classic Prisoner's Dilemma featuring two suspects, Alice ($A$) and Bob ($B$):

To solve such games, game theory defines several solution concepts—subsets of outcomes toward which rational decision-makers gravitate.

---

1. Dominant Strategy Equilibrium

Dominance Definitions

• Strong Dominance: A strategy $s$ for player $p$ strongly dominates strategy $s'$ if the outcome for $s$ is strictly better for $p$ than $s'$, for every choice of strategies by the other player(s).
• Weak Dominance: Strategy $s$ weakly dominates $s'$ if $s$ is better than $s'$ on at least one strategy profile and no worse on any other.

Analyzing Prisoner's Dilemma:

• For Alice:
  • If Bob testifies: Testify gives $-5$, Refuse gives $-10 \implies$ Testify is better.
  • If Bob refuses: Testify gives $0$, Refuse gives $-1 \implies$ Testify is better.
• For Bob:
  • If Alice testifies: Testify gives $-5$, Refuse gives $-10 \implies$ Testify is better.
  • If Alice refuses: Testify gives $0$, Refuse gives $-1 \implies$ Testify is better.

Definition of Dominant Strategy Equilibrium

A strategy profile $S^* = (s_1^*, s_2^*, \dots, s_n^*)$ is a Dominant Strategy Equilibrium if each $s_i^*$ is a dominant strategy for agent $i$. Agent $i$ does best by playing $s_i^*$ regardless of what strategies other players adopt.

In the Prisoner's Dilemma, the dominant strategy for both Alice and Bob is "Testify". The dominant strategy equilibrium is $(\text{Testify}, \text{Testify})$ with payoff $(-5, -5)$.

---

2. Pareto Optimality

Let $S$ be a strategy profile and $U_i(S)$ be the numerical payoff for player $i$.

Pareto Domination

A strategy profile $S$ Pareto dominates a strategy profile $S'$ if:

1. No agent receives a worse payoff with $S$ than with $S'$: $U_i(S) \ge U_i(S') \quad \forall i$
2. At least one agent receives a strictly better payoff: $U_i(S) > U_i(S') \quad \text{for at least one } i$

Pareto Optimal (Strictly Pareto Efficient)

A strategy profile $s$ is Pareto optimal if there is no other strategy profile $s'$ that Pareto dominates $s$. An outcome is Pareto optimal if there is no alternative outcome that all players would prefer.

Key Properties of Pareto Optimality

• Existence: Every finite game has at least one Pareto optimal strategy profile.
• Pure Strategy Guarantee: There is always at least one Pareto optimal profile in which all strategies are pure.

Fundamental Axioms of Rationality

• It is irrational to play a dominated strategy.
• It is irrational not to play a dominant strategy if one exists.

In the Prisoner's Dilemma, the outcome $(\text{Testify}, \text{Testify})$ with payoff $(-5, -5)$ is Pareto dominated by $(\text{Refuse}, \text{Refuse})$ with payoff $(-1, -1)$. This illustrates the fundamental paradox: rational individual choices can lead to a Pareto-inefficient group outcome.

---

3. Nash Equilibrium

Definition & Intuition

A strategy profile forms a Nash Equilibrium if no player can benefit by unilaterally switching strategies, given that every other player sticks with their strategy.

[!TIP] The Unilateral Thought Experiment: Imagine each player is informed of the strategies selected by all other players. Each player asks: "Knowing the strategies of the other players, and treating them as set in stone, can I benefit by unilaterally changing my strategy?" If no player can benefit from changing, the strategy profile is in Nash Equilibrium.

Key Insights on Nash Equilibrium

• Necessary vs. Sufficient Condition: Game theorists agree that being a Nash equilibrium is a necessary condition for an outcome to be a rational solution—although they disagree on whether it is a sufficient condition.
• Dominant Strategy vs. Nash Equilibrium: All dominant strategy equilibria are Nash equilibria, but the reverse is not true. Games can have multiple Nash equilibria without any dominant strategies existing.
• Nash Equilibrium vs. Pareto Optimality: A Nash equilibrium is not necessarily Pareto optimal (as seen in the Prisoner's Dilemma equilibrium $(-5, -5)$, which is Pareto dominated by $(-1, -1)$).

---

Games Without Dominant Strategies: Battle of the Sexes

When no dominant strategy exists, players must coordinate based on mutual expectations. Consider the classic Battle of the Sexes game:

• Alice and Bob want to spend the evening together, but have preferences for different activities.
• Alice prefers going to the Opera ($A=2, B=1$), while Bob prefers watching a Football game ($A=1, B=2$).
• However, both players prefer being together over going to an activity alone ($A=0, B=0$).

Absence of Dominant Strategies:

• There is no dominant strategy for either player. Optimal choices depend entirely on what the other player does.
• Alice prefers Football if Bob chooses Football, but prefers Opera if Bob chooses Opera.
• Bob's reasoning is identical—he chooses Opera if he knows Alice will, despite preferring Football.

Multiple Nash Equilibria:

• Two Pure Nash Equilibria Exist:
  1. $(\text{Football}, \text{Football})$ with payoff $(1, 2)$.
  2. $(\text{Opera}, \text{Opera})$ with payoff $(2, 1)$.
• Coordination is Key: Neither player can unilaterally improve their payoff from these points. Players must align their choices to achieve equilibrium.

---

Escaping the Prisoner's Dilemma: Repeated & Sequential Games

In a single-shot Prisoner's Dilemma, rational self-interest leads both players to defect ($\text{Testify}, \text{Testify}$). However, rational agents can arrive at the cooperative outcome ($-1, -1$) under modified game structures:

1. Repeated Games (Iterated Play)

• If players face the exact same choice repeatedly over multiple moves and know they will meet again, the game becomes a Repeated Game.
• Because each player knows the history of previous choices, strategies like Tit-for-Tat (cooperate first, then mirror opponent's previous move) punish defection and make mutual cooperation a stable equilibrium.

2. Moral Beliefs & Social Norms

• Agents may possess moral beliefs or social norms that encourage cooperation and fairness.
• Intrinsically valuing fairness alters the agent's internal utility function, resulting in a different payoff matrix where mutual cooperation becomes the dominant strategy.

3. Sequential Games

• Unlike simultaneous games where choices are made blindly, a Sequential Game consists of a sequence of turns executed in order.
• Players make choices with full knowledge of all previous actions taken by other players, leading to strategic game-tree search methods like Minimax.