Agents in Conflict — Game Theory
What a second rational player changes about an optimization — everything.
Your search agent (like the A* algorithm from the previous article) found the optimal path through the maze. But what happens when someone on the other side is actively rearranging the walls? The moment a second intelligent agent enters the picture — one with goals that directly oppose yours — everything changes.
This chapter shows why the jump from a single agent to a multi-agent system is not simply "more of the same" but a fundamental paradigm shift. Game theory provides the mathematical toolkit for this transformation — and it is the foundation upon which all adversarial AI algorithms are built.
From Solo to Duel — Multi-Agent Systems
In the previous articles, your agent always worked against a static environment: a maze, a road network, a puzzle. The environment had no goals of its own. Now that changes fundamentally.
Definition
Multi-Agent System
Analogy
Example
Definition
Static environment. No counter-moves. The optimal path remains stable. Pure optimization.
Dynamic environment. The opponent responds intelligently. Every move changes the situation. Strategic thinking required.
Legal positions in Tic-Tac-Toe: A computer solves the game in milliseconds
5,478
Legal positions in chess: Exhaustive analysis impossible — heuristics required
~10 ⁴⁴
Tic-Tac-Toe has only 9 squares yet 5,478 legal game positions. Because this state space is tiny by computational standards, a computer can exhaustively analyze every possible game in milliseconds and compute a mathematically perfect strategy (the game is "solved"). Chess, by contrast, has approximately 10⁴⁴ legal positions — exhaustive analysis is impossible, which is why chess engines need heuristic strategies.
AlphaZero Masters Three Games
The birth of a universal game AI through pure self-learning. In December 2017, DeepMind presented AlphaZero — a system that mastered three completely different strategy games without any prior knowledge: chess, shogi, and Go. The tabula rasa approach meant: no opening databases, no human strategies, only the rules of the game as a starting point. Within 24 hours, AlphaZero achieved superhuman performance — in chess after just 4 hours, in shogi after 2 hours. In the 100-game match against Stockfish, it won 28 games, lost none, and drew 72. Its distinctiveness lay in efficient search behavior: while Stockfish evaluates 70 million positions per second, AlphaZero analyzes only 80,000 — but far more purposefully through its deep neural network. This performance impressively demonstrated the generalizability and domain-independence of pure reinforcement learning.
Caution
Misconception: An opponent just makes the search tree bigger
It is not about size. The fundamental NATURE of the problem changes. In single-agent search, the environment is passive. In adversarial search, the "environment" actively works against you. You cannot simply find the best path — you must find the best path assuming the opponent plays optimally against you. This is a qualitative shift, not a quantitative one.
Zero-Sum Games — The Fixed Pie
Now that you understand the paradigm shift, we need a mathematical model for pure competition. The zero-sum game is that model: what one player gains, the other loses — exactly.
Definition
Zero-Sum Game
Analogy
Example
Definition
Payoff Matrix: Rock-Paper-Scissors
Consider the 3×3 payoff matrix from Player 1's perspective (row) against Player 2 (column):
| Player 1 / Player 2 | Rock | Paper | Scissors |
|---|---|---|---|
| Rock | 0 | −1 | +1 |
| Paper | +1 | 0 | −1 |
| Scissors | −1 | +1 | 0 |
Each cell shows Player 1's payoff. Player 2 receives the negative value (zero-sum). Reading the matrix: Rock beats Scissors (+1), loses to Paper (-1). Key insight: the optimal strategy is to play each option with exactly 1/3 probability (mixed strategy). Any deviation — even slightly favoring Rock — is exploitable by an observant opponent.
If you play a non-uniform strategy in Rock-Paper-Scissors — say 34% Rock, 33% Paper, 33% Scissors — an observant opponent can detect the pattern and play Paper more often. Any deviation from 1/3 per option gives the opponent exploitable information. That is why the optimal strategy is strictly uniform: maximum unpredictability.
Caution
Misconception: Every competitive situation is zero-sum
Most real-world competition is NOT zero-sum. Business competition often expands markets (positive-sum). International trade creates mutual benefits. Even in some games, cooperation can improve outcomes for all players (see Nash Equilibrium and the Prisoner's Dilemma). The zero-sum assumption is a deliberate simplification for mathematical tractability, not a universal law.
Nash Equilibrium — When Nobody Can Do Better
You now know zero-sum games and payoff matrices. But how do you find a "good" strategy? John Nash provided the answer in 1950: the equilibrium where no player can unilaterally improve.
Definition
Nash Equilibrium
Analogy
Example
Definition
The Prisoner's Dilemma — Stability Without Optimality
The most famous game in game theory. Two suspects are interrogated separately. Each can either Cooperate (stay silent) or Defect (betray the other). Note: Here the payoffs are measured in years of imprisonment — less is better, unlike Rock-Paper-Scissors.
- 1. SetupTwo suspects, interrogated separately. Each has two options: Cooperate (stay silent) or Defect (betray the other).
- 2. PayoffsBoth cooperate: 1 year each. One defects, the other cooperates: defector goes free, cooperator gets 6 years. Both defect: 3 years each.
- 3. Dominant StrategyNo matter what the other does: Defecting is always better. If the other cooperates? Defecting gives 0 instead of 1 year. If the other defects? Defecting gives 3 instead of 6 years.
- 4. The ParadoxThe Nash equilibrium is (Defect, Defect) with 3 years each — even though (Cooperate, Cooperate) with 1 year each would be better for BOTH. Stability is not optimality.
| Player 1 / Player 2 | Cooperate | Defect |
|---|---|---|
| Cooperate | 1 / 1 years | 6 / 0 years |
| Defect | 0 / 6 years | 3 / 3 years |
Each cell: years in prison for player 1 (row) / player 2 (column). Green: best for both. Orange: the Nash equilibrium. The Nash equilibrium of the Prisoner's Dilemma is (Defect, Defect) because Defecting is the dominant strategy for both players: regardless of what the other does, Defecting is always the better choice. Yet mutual cooperation (1 year instead of 3) would benefit both. The equilibrium is stable but collectively suboptimal — a key result of game theory.
Caution
Misconception: Nash equilibrium is the best outcome
The Prisoner's Dilemma proves exactly the opposite. The Nash equilibrium (mutual betrayal, 3 years each) is WORSE for both players than mutual cooperation (1 year each). A Nash equilibrium guarantees stability (nobody can improve alone), not optimality (best possible result). This distinction is fundamental for AI agent design: agents that blindly optimize individually can produce collectively worse outcomes.
Interactive: Where Is the Nash Equilibrium?
Choose Cooperate or Defect for both suspects — with the buttons or directly in the table. The box shows the years in prison and checks, for each player, whether switching alone would get them fewer years. Where that holds for neither player, you have found the Nash equilibrium; it is marked in the table.
Mathematical game theory was founded in 1944 by John von Neumann and Oskar Morgenstern in their work "Theory of Games and Economic Behavior." They formalized zero-sum games; von Neumann had already proved the Minimax theorem for them in 1928. Six years later, in 1950, mathematician John Nash decisively expanded the field in his PhD dissertation at Princeton University: he proved that every finite game — not just zero-sum games — has at least one equilibrium. For this contribution, Nash received the 1994 Nobel Prize in Economics (shared with John Harsanyi and Reinhard Selten). Game theory is now a cornerstone of AI research: from the MinMax algorithm (next article) to multi-agent reinforcement learning to automated auction systems.
Note
Key Takeaways
- A second intelligent agent transforms optimization into strategic reasoning — you must anticipate the opponent's response to every move you make.
- In a zero-sum game, gains and losses always sum to zero (the "fixed pie"). Payoff matrices make all possible outcomes visible and analyzable.
- A Nash equilibrium is a stable state where no player can improve by unilaterally changing strategy — but stability does not guarantee optimality (the Prisoner's Dilemma proves it).
Check Your Understanding
Can you explain this in your own words? Tick what you've got.
0 of 3 done
Check
Quiz: Game Theory
A robot navigates a warehouse alone, avoiding static obstacles. A second robot is introduced that competes for the same pickup locations. What fundamentally changes about the first robot's planning problem?
Select one answer
1. A robot navigates a warehouse alone, avoiding static obstacles. A second robot is introduced that competes for the same pickup locations. What fundamentally changes about the first robot's planning problem?
2. Two street vendors sell identical ice cream on a beach. Vendor A's profit is always the negative of Vendor B's profit (all customers choose one vendor). Is this a zero-sum game?
3. In the Prisoner's Dilemma, both players choosing "Defect" is the Nash equilibrium. Why is this outcome paradoxical?
4. In Rock-Paper-Scissors, Player A plays Rock 50% of the time, Paper 25%, Scissors 25%. How should Player B respond?