1 Fundamentals of Game Theory
1.1 Informal Game Definition
Informally, a game is a system of interacting decision making agents with conflicting aims. The flexibility of this definition has lead to a wide variety of different games depending on their underlying structure. For example, games can be:
- Cooperative or Non-cooperative
- Static vs Dynamic
- Deterministic vs Stochastic
- Simultaneous vs Sequential vs Continuous Time
- Symmetric vs Asymmetric
- Perfect Information vs Imperfect Information
- Zero-Sum vs Non-Zero-Sum
The solution to games from a mathematical perspective is to find equilibriums, i.e. states that the game will move into if left to run.
1.2 Formal Game Definition
Denote agents \(j\in \{ 1, \dots, J \}:=\mathcal{J}\) gather in agent space \(\mathcal{J}\). The fundamental underpinnings of game theory are studied in Decision Theory which involves the study of single agent decision making under uncertainty.
Each agent can select from set of possible strategy \(s_{j}\in\mathcal{S}_{j}\) (also called actions or decisions) called the strategy space.
We denote the agent wide strategy space by the Cartesian product \(\mathcal{S}:=\mathcal{S}_{1}\times\cdots\times \mathcal{S}_{J}\). Typically strategies are driven by decision rules which are functions mapping from an observation to an appropriate strategy.
A strategy is said to be pure if it is deterministic i.e. there is no randomness to the strategy. Otherwise the strategy is said to be mixed.
All elements of the strategy spaces \(\mathcal{S}_{j}\) are pure. The space of mixed strategies for agent \(j\) is the simplex over \(\mathcal{S}_{j}\).
The simplex \(\Delta \mathcal{S}_{j}\) of pure decision space \(\mathcal{S}_{j}\) is the set of probability distributions over \(\mathcal{S}_{j}\). A mixed strategy for player \(j\) is an element \(\sigma_{j}\in\Delta\mathcal{S}_{j}\) so that \(\sigma_{j}\) is a probability distribution over \(\mathcal{S}_{j}\). We denote by \(\sigma(s_{j})\) the probability that player \(j\) employs \(s_{j}\).
Example (Pure vs Mixed Strategy): Suppose we are playing poker and we construct a strategy on how to handle strong hands. A pure strategy could be “for 3-of-a-kind or stronger go all in”. Although the game itself is random, the strategy is deterministic, if this then that. Alternatively, a mixed strategy could be “for a 3-of-a-kind or stronger go all in 75% of the time”. Now we have introduced a stochastic component to our strategy.
Each agent has a utility function (also called payoff or profit) \[ U_{j}:\mathcal{S}\to \mathbb{R}, \] which describes their utility gain (or loss) based on an strategy profile \(s\in\mathcal{S}\). We denote the combined agent utility function space by the Cartesian product \(\mathcal{U}:=\prod_{j\in \mathcal{J}}U_{j}\). The game is therefore mathematically represented by the tuple \((\mathcal{J},\mathcal{S},\mathcal{U})\).
Given that the game involved only pure strategies each agent \(j\) chooses strategy \(s_{j}\in\mathcal{S}_{j}\) to maximize her utility \[ \max_{s_{j}\in \mathcal{S}_{j}}U_{j}(s_{j},s_{{-j}}), \] where \(s_{-j}\) denotes the strategies of all players except \(j\). For games with mixed strategies an agent chooses mixed strategy \(\sigma_{j}\in \Delta \mathcal{S}_{j}\) to maximize her expected utility \[ \max_{\sigma_{j}\in \Delta\mathcal{S}_{j}}\mathbb{E}[U_{j}(s_{j},s_{-j})]. \]