Lecture 06.1: Game Theory and Nash Equilibrium

Adversarial search algorithms are fundamental in AI when agents operate in environments with competing interests and conflicting goals. These algorithms model strategic decision-making where each agent's success depends on anticipating and countering the actions of others.

Game Theory Foundation

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

Games can be:

• Cooperative: Players can form enforceable agreements.
• Competitive: No binding commitments exist; players act independently. (Historically developed around zero-sum games, where one player's gain is the other's loss).

Single Move Games

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

Important Terminologies:

• Players: Agents making decisions (humans, AI).
• Actions: Choices available to the players.
• Payoff Function: A mapping that assigns a numerical utility (reward/penalty) based on the combination of actions.
• Strategic Form (Normal Form): Organizing payoffs in a matrix format.

The Prisoner's Dilemma

A classic example of a single-move game is the Prisoner's Dilemma. Consider two agents, Alice and Bob.

To solve this, we look for solution concepts—subsets of outcomes that rational agents would gravitate towards.

Dominant Strategy

• Strongly Dominates: Strategy $S$ is strictly better than $S'$ regardless of what the other player does.
• Weakly Dominates: Strategy $S$ is better than $S'$ in at least one profile, and no worse in any other.

In the Prisoner's Dilemma, "Testify" is a dominant strategy for both Alice and Bob. No matter what Bob does, Alice gets a better payoff by testifying, and vice versa.

Therefore, the Dominant Strategy Equilibrium is for both players to testify, resulting in a payoff of $(-5, -5)$.

Pareto Optimality

An outcome is Pareto optimal if there is no other outcome that all players would prefer. In our matrix, the $(-1, -1)$ outcome (both refuse) is strictly better for both players than the $(-5, -5)$ outcome. Thus, the $(-5, -5)$ equilibrium is Pareto dominated by $(-1, -1)$.

Nash Equilibrium

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

• Every game has at least one Nash equilibrium.
• A dominant strategy equilibrium is always a Nash equilibrium, but the reverse is not true.
• As seen in the Prisoner's Dilemma, a Nash equilibrium is not necessarily Pareto optimal. Rational agents might end up at a worse global outcome $(-5, -5)$ because neither can risk unilaterally switching to "Refuse" without being heavily penalized $(-10)$.

Games Without Dominant Strategies

Sometimes, optimal choices completely depend on mutual coordination.

In the "Battle of the Sexes" game above, there are no dominant strategies. However, there are two Nash Equilibria: Both choosing Football, or both choosing Opera. Coordination is the key to achieving these equilibria.