Game Theory Fundamentals
1 Intuition
Informally, a game is a system of interacting decision making agents with conflicting aims. The flexibility of this definition has led to a wide variety of games, which can be classified as:
- cooperative (players can bind themselves to mutually beneficial agreements) or non-cooperative;
- static (one decision) or dynamic (decisions over time);
- deterministic or stochastic (see Stochastic Games);
- simultaneous, sequential or continuous time;
- symmetric or asymmetric;
- perfect or imperfect information;
- zero-sum ([zero-sum-games]) or non-zero-sum.
The mathematical solution of a game is an equilibrium: a state the game settles into if left to run (see [nash-equilibrium]). The single-agent problem underlying everything here is studied in Decision Theory.
2 Normal-form games
Let \(j\in\{1,\dots,J\}=:\mathcal{J}\) index the agents, who form the agent space \(\mathcal{J}\).
Each agent \(j\) selects a strategy \(s_{j}\in\mathcal{S}_{j}\) (also called an action or decision) from the strategy space \(\mathcal{S}_{j}\). The joint strategy space is the Cartesian product \(\mathcal{S}:=\mathcal{S}_{1}\times\cdots\times\mathcal{S}_{J}\), whose elements are strategy profiles \(s=(s_{j})_{j\in\mathcal{J}}\).
Strategies are typically generated by decision rules, functions mapping an observation to a strategy.
A strategy \(s_{j}\in\mathcal{S}_{j}\) is pure (deterministic). The simplex \(\Delta\mathcal{S}_{j}\) is the set of probability distributions over \(\mathcal{S}_{j}\); a mixed strategy is an element \(\sigma_{j}\in\Delta\mathcal{S}_{j}\), and \(\sigma_{j}(s_{j})\) is the probability that player \(j\) plays \(s_{j}\).
In poker, a pure strategy for strong hands is “with three-of-a-kind or better go all in”. A mixed strategy is “with three-of-a-kind or better go all in 75% of the time”. The game is random in both cases, but only the second strategy is itself random.
Each agent has a utility function (also called payoff or profit) \[ U_{j}:\mathcal{S}\to\mathbb{R}, \] giving the utility gain (or loss) for a strategy profile \(s\in\mathcal{S}\). With \(\mathcal{U}:=(U_{j})_{j\in\mathcal{J}}\), the game in normal form is the tuple \((\mathcal{J},\mathcal{S},\mathcal{U})\).
With pure strategies each agent \(j\) solves \[ \max_{s_{j}\in\mathcal{S}_{j}}U_{j}(s_{j},s_{-j}), \] where \(s_{-j}\) denotes the strategies of all players except \(j\). With mixed strategies she maximizes her expected utility \[ \max_{\sigma_{j}\in\Delta\mathcal{S}_{j}}\mathbb{E}_{\sigma}[U_{j}(s_{j},s_{-j})]. \]
The canonical model of quantity competition in oligopoly. Each firm chooses a production quantity \(q_{j}\geq0\) at some cost, and the market price depends on total output through an inverse demand function. It is a static non-cooperative game with continuous strategy sets whose equilibria are Nash equilibria in quantities.
3 Extensive-form games
In a deterministic game tree with complete information we start from a directed tree \(T\) (see Graph Theory) in which each non-terminal vertex is owned by a player who makes a move there.
A game tree consists of a directed tree \(T\), a player assignment mapping each non-terminal vertex \(v\) to the player controlling it, and a payoff vector (one payoff per player) at each terminal vertex. The out-edges of \(v\) are the moves available to its owner, and terminal vertices represent end-of-game conditions.
Here there are no chance moves and every player knows exactly who is moving and what has been played. Such games are solved by backward induction from the terminal vertices.
4 Solution concepts
The main solution concepts are developed in their own notes:
- theorem;
For large populations of agents, see Mean Field Games; for dynamics driven by a random state, see Stochastic Games.
5 References
- T. Basar and G. J. Olsder, Dynamic Noncooperative Game Theory.
- R. Carmona, Lectures on BSDEs, Stochastic Control, and Stochastic Differential Games.
- M. Lauriere and others, “Learning in mean field games and finite-player games” (arXiv:2106.06231).