Game Theory for Agents
Game theory provides the mathematical framework for analyzing strategic interaction among rational agents, predicting how self-interested decision makers behave when each one's outcome depends on the others' choices.
Definition
Game theory studies situations in which multiple rational agents each choose actions whose payoffs depend on all the agents' choices, and characterizes stable or rational joint behavior through solution concepts such as equilibria.
Scope
This topic covers the game-theoretic foundations used in multi-agent AI: normal-form and extensive-form games, dominant strategies, the Nash equilibrium and its existence, mixed strategies, and key examples such as the prisoner's dilemma and zero-sum games; together with algorithmic questions of computing equilibria. It addresses how agents reason about each other and what joint behaviors are stable. The engineering of interaction rules is treated under mechanism design, and learning to play games belongs to the machine-learning subfield.
Core questions
- How are strategic interactions represented as games in normal or extensive form?
- What solution concepts (dominant strategies, Nash equilibrium) predict how rational agents behave?
- When is an equilibrium guaranteed to exist, possibly in mixed strategies?
- How hard is it to compute equilibria, and how does this affect their use by agents?
Key concepts
- normal-form and extensive-form games
- payoffs and strategies
- dominant strategy
- Nash equilibrium
- mixed strategies
- zero-sum games and minimax
- prisoner's dilemma
- equilibrium computation
Key theories
- Nash equilibrium
- A Nash equilibrium is a profile of strategies in which no agent can improve its payoff by unilaterally changing its own strategy; Nash proved that every finite game has at least one such equilibrium, possibly in mixed strategies.
- Minimax in zero-sum games
- In two-player zero-sum games, von Neumann's minimax theorem guarantees a value and optimal (possibly randomized) strategies for both players, connecting game theory to adversarial decision making.
- Dominant strategies and dilemmas
- Analyzing games via dominant strategies explains outcomes such as the prisoner's dilemma, where individually rational choices lead to a collectively worse result, illustrating the tension between individual and group rationality.
Clinical relevance
Game-theoretic analysis informs the design of auctions and markets, security and patrolling strategies, network routing and congestion, and automated negotiation, by predicting how strategic agents will act and identifying stable outcomes in competitive settings.
History
Game theory was founded by von Neumann and Morgenstern (1944) and extended by Nash's equilibrium concept (1950). It became central to economics and, from the 1990s, to AI and computer science through algorithmic game theory, which studies the computational complexity of equilibria and their use in multi-agent systems.
Key figures
- John von Neumann
- Oskar Morgenstern
- John F. Nash
- Yoav Shoham
- Kevin Leyton-Brown
Related topics
Seminal works
- nash1950
- vonneumann1944
- shoham2009
Frequently asked questions
- What is a Nash equilibrium?
- A Nash equilibrium is a combination of strategies, one per agent, such that no single agent can do better by changing only its own strategy while the others keep theirs fixed. It captures a notion of stable, mutually consistent rational behavior.
- Why does the prisoner's dilemma matter for AI agents?
- The prisoner's dilemma shows that agents acting in their own rational self-interest can reach an outcome that is worse for all of them than if they had cooperated. It highlights why designing incentives and coordination mechanisms is important when building systems of self-interested agents.