Game Theory
Deciding when the other side is deciding too. Equilibria, mechanisms, and the strategic reasoning that multi-agent systems rest on.
Learning paths (1)
Encyclopedia (5)
Minimax
A decision rule for two-player zero-sum games in which each player chooses the move maximizing their own worst-case outcome against optimal opposition.
Dominant Strategy
A strategy that yields a better outcome than an alternative regardless of what the other players do, and a dominant one if it beats every alternative.
Prisoner’s Dilemma
A game in which each player has a dominant strategy, yet both playing it produces an outcome worse for both than mutual cooperation would have been.
Nash Equilibrium
A combination of strategies, one per player, such that no player can improve their outcome by changing strategy alone.
Mixed Strategy
A strategy that selects among the available actions according to a probability distribution rather than choosing one deterministically.
Articles (2)
Adversarial Search and Minimax
How a program plays a game against an opponent who is trying to beat it: the minimax value, why alpha-beta pruning reaches the same answer while examining fewer nodes, and a game tree pruned move by move.
Game Theory and Nash Equilibrium
Strategic reasoning when players are not strictly opposed: dominant strategies, the prisoner's dilemma worked from its payoff matrix, Nash equilibrium, Pareto optimality, and why equilibrium and efficiency can conflict.
Research (3)
Equilibrium Points in N-Person Games
Proves that every finite game with any number of players has at least one equilibrium point, provided players may use mixed strategies.
Programming a Computer for Playing Chess
Lays out how a machine might play chess: represent positions, generate legal moves, search the game tree with minimax, and evaluate non-terminal positions with a heuristic scoring function.
Games with Incomplete Information Played by Bayesian Players
Shows how games in which players are uncertain about one another’s payoffs can be transformed into games of complete but imperfect information, by treating each player as having a randomly assigned "type".