Beta Phase: Square45 is currently in beta testing. Expect some features or content to be incomplete or missing.
45

Game Theory

Field: Optimization & Game Theory

The study of mathematical models of strategic interaction among rational decision-makers.

Sequence of Expressions

A game GG is formally defined as a tuple G=⟨N,(Si)i∈N,(ui)i∈N⟩G = \langle N, (S_i)_{i \in N}, (u_i)_{i \in N} \rangle, where:\\ \\ 1. NN is a finite set of players, N={1,2,…,n}N = \{1, 2, \dots, n\}.\\ \\ 2. For each player i∈Ni \in N, SiS_i is the set of pure strategies available to ii. The combined strategy space is S=∏i∈NSiS = \prod_{i \in N} S_i.\\ \\ 3. For each player i∈Ni \in N, ui:S→Ru_i: S \to \mathbb{R} is the payoff function, mapping a strategy profile s=⟨s1,…,sn⟩∈Ss = \langle s_1, \dots, s_n \rangle \in S to a real payoff ui(s)u_i(s).\\ \\ \\ The set of all payoff vectors is U:S→RnU: S \to \mathbb{R}^n, defined by U(s)=⟨u1(s),…,un(s)⟩U(s) = \langle u_1(s), \dots, u_n(s) \rangle.\\ \\ \\ A mixed strategy σi\sigma_i for player ii is a probability distribution σi∈Δ(Si)\sigma_i \in \Delta(S_i), where Δ(Si)\Delta(S_i) is the simplex over SiS_i. The expected payoff for player ii given a mixed strategy profile σ=⟨σ1,…,σn⟩\sigma = \langle \sigma_1, \dots, \sigma_n \rangle is Ei(σ)=∑s∈Sσ(s)ui(s)E_i(\sigma) = \sum_{s \in S} \sigma(s) u_i(s), where σ(s)=∏i∈Nσi(si)\sigma(s) = \prod_{i \in N} \sigma_i(s_i).\\ \\ \\ A Nash Equilibrium (NE) is a strategy profile σ∗=⟨σ1∗,…,σn∗⟩\sigma^* = \langle \sigma_1^*, \dots, \sigma_n^* \rangle such that for all players i∈Ni \in N, σi∗\sigma_i^* maximizes Ei(σ)E_i(\sigma) given the strategies of all other players: \\ Ei(σi∗,σ−i∗)≥Ei(σi,σ−i∗)for all σi∈Δ(Si).E_i(\sigma_i^*, \sigma_{-i}^*) \ge E_i(\sigma_i, \sigma_{-i}^*) \quad \text{for all } \sigma_i \in \Delta(S_i).
Intermediate
For every two-person, zero-sum game with finite strategies, there exists a value VV and a mixed strategy for each player such that the expected payoff is VV.\nmax⁡xmin⁡yxTAy=min⁡ymax⁡xxTAy=V\max_{x} \min_{y} x^T A y = \min_{y} \max_{x} x^T A y = V