Game-Theory
Pages in this section
- Battle of the sexesLast edited: 2024-04-07Battle of the sexes
Suppose two friends $A$ and $B$ are going to a town to see a concert. There is two concerts on $x$ and $y$ but unfortunately they forgot to agree which one to go to and can’t communicate. They will both be unhappy if they go to a different concert and both get a score $0$. $A$ slightly prefers concert $x$ and if they go there together will get a score of $2$ whereas $B$ gets a score $1$ - whereas it is vice versa for concert $B$. In summary this can be represented in a payoff table as follows.
- Elimination and Nash Equilibrium
Last edited: 2026-01-28# Statement
LemmaIn an $n$-player pure strategy game, if elimination of Strictly dominated strategy eliminates all but one combination of strategies, that combination is the unique Nash equilibrium . Similarly a Nash equilibrium can never be strictly dominated .
- Existence of Nash equilibrium
Last edited: 2026-02-05# Statement
LemmaIn an $n$-player game where $n$ is finite and each player has a finite choice of pure strategies $\vert S_i \vert < \infty$, then there exists a (possibly mixed) Nash equilibrium .
- Folk Theorem
Last edited: 2026-01-28# Statement
LemmaAny feasible payoff that is in the Security region can be realised as a Nash equilibrium with a sufficiently large discount factor.
- Game theory
Last edited: 2026-02-05Game theoryGame theory is the study of systems where there are more than one rational players.
- Grim trigger strategy
Last edited: 2026-02-05Grim trigger strategyGiven we have some agreed cooperation strategy $C$ and a strategy that guarantees the minmax profile for the other player $P$, the grim trigger strategy is as follows: as long as the other player is following strategy $C$, we follow strategy $C$ too—if they ever do not follow strategy $C$, we switch to strategy $P$ for the rest of time.
- Minimax-Q
Last edited: 2026-02-05Minimax-QThis is a generalisation of Q-learning to Stochastic games and is defined for each player.
- Minmax decision
Last edited: 2026-02-05Minmax decisionIf you choose to minmax, you want to minimise the maximum loss. In terms of gain you want to maximise the minimum gains, which is why it is sometimes referred to as maximin.
- Minmax profile
Last edited: 2026-02-05Minmax profileFor a game, the minmax profile is the expected score a player can achieve assuming your opponents only want to harm you. They are allowed to take any strategy, this can be a Pure strategy or Mixed strategy .
- Mixed strategy
Last edited: 2026-02-05Mixed strategyIn Game theory a pure strategy is non-deterministic i.e. you have access to a random variable $X$ that can be used to make your strategy $s: S \times [0,1] \rightarrow A$ from states of the game and the result of the random variable to actions.
- Nash equilibrium
Last edited: 2026-02-05Nash equilibriumIn a game with $n$ players where player $i$ has choice of strategies in $S_i$. The state $(s^{\ast}_1, s^{\ast}_2, \ldots, s^{\ast}_n) \in S_1 \times S_2 \times \ldots \times S_n$ is in Nash equilibrium if for all $i$ we have
- Optimum play exists for 2-player zero-sum games with perfect information
Last edited: 2025-12-05# Statement
LemmaIn a 2-player zero-sum game with perfect information there exists an optimal pure strategy for each player.
- Pavlov strategy
Last edited: 2026-02-05Pavlov strategyThe Pavlov strategy for Prisoner’s dilemma is given by the following rules:
- Plausible threat
Last edited: 2026-02-05Plausible threatA threat is plausible if it is Subgame perfect .
- Prisoner's dilemma
Last edited: 2024-04-06Prisoner’s dilemmaTwo people are caught mid crime and put in separate cells where they can’t talk to each other. They are both offered a plea deal if they testify against their companion, where:
- Pure strategy
Last edited: 2026-02-05Pure strategyIn Game theory a pure strategy is deterministic i.e. it is a map $s: S \rightarrow A$ from states of the game to actions.
- Security region
Last edited: 2026-02-05Security regionFor a game, the security region is any outcome where both players get more than or equal to the Minmax profile .
- Semi-wall stochastic game
Last edited: 2024-04-07Semi-wall stochastic gameThe semi-wall game is a Gridworld game played on a 3x3 grid. With player $A$ starting in the bottom left corner and player $B$ starting in the bottom right. The goal of the game is to arrive at the money in the centre top - whoever does that first gets a point. If two players try to enter the same spot with even odds one player moves in and the other stays where they are. There is a semi-wall above each player to start with which has a 50% chance of letting them through, otherwise they stay where they are. The game looks as follows:
- Stochastic games
Last edited: 2026-02-05Stochastic gamesA stochastic game is defined by the following data:
- Strictly dominated strategy
Last edited: 2026-02-05Strictly dominated strategyIn a game with $n$ players where player $i$ has choice of strategies in $S_i$ and has utility function $U_i$. For a player $i$ strategy $s^{+} \in S_i$ strictly dominates $s^- \in S_i$ if and only if for all $(s_1, \ldots, s_{i-1}, s_{i+1}, \ldots, s_n) \in S_1 \times \ldots \times S_{i-1} \times S_{i+1} \times \ldots \times S_n$ we have
- Subgame perfect
Last edited: 2026-02-05Subgame perfectA strategy is subgame perfect if it is always the best strategy to follow independent of the history of the game.
- Tit for Tat
Last edited: 2026-02-05Tit for TatIn a symmetric two player game, the tit for tat strategy just copies the opponents move. In the first round it will do something random.
- Zero-sum game
Last edited: 2026-02-05Zero-sum gameA game is zero-sum if the sum of all players’ gains and losses equals zero.
- Elimination and Nash Equilibrium