标准式博弈

标准式博弈

对于$3$元组$\Gamma=(I,S,\pi)$，$\Gamma$被称为标准式博弈（normal form game），如果满足以下条件：

1. 规定$I$表示（在$\Gamma$中）玩家集合，$I$是可列的
2. 记$S=\bigg\{S[i]\bigg|i \in I\bigg\}$，规定$S[i]$表示玩家$i$（在$\Gamma$中）的策略集合，$S$表示（在$\Gamma$中）策略空间
3. 记$\pi=\bigg\{\pi[i]\bigg|i \in I\bigg\}$，规定$\pi[i]$表示玩家$i$（在$\Gamma$中）的收益函数，$\pi$表示（在$\Gamma$中）收益函数组合，即有

$\pi[i]:S \to \mathbb R$

补充说明 对于标准式博弈$\Gamma=(I,S,\pi)$，令$J$是$I$的某一全排序，记$S[J] = \underset{j \in J}\times S[j]$，$\pi[J] = \underset{j \in J}\times \pi[j]$，即有

$\forall s \in S, \space \pi[J](s) = \underset{j \in J}\times \pi[j](s) \in \mathbb{R}^{|J|}$

。特别的，如果$I$本身是有序的，那么可默认$S=S[I]$和$\pi=\pi[I]$。

有限标准式博弈

对于标准式博弈$\Gamma=(I,S,\pi)$，$\Gamma$被称为有限标准式博弈（finite normal form game）或者是有限的，如果满足以下条件：

1. $0<|I|<\infty$
2. $\forall i \in I,\space 0<|S[i]|<\infty$

扩展博弈

对于标准式博弈$\Gamma=(I,S,\pi)$，标准式博弈$\mathrm{H}=(I,\Delta,u)$被称为$\Gamma$的（混合策略）扩展博弈（extensive game），如果满足以下条件：

1. $\Gamma$和$\mathrm{H}$的玩家集合都是$I$
2. 记$\Delta=\bigg\{\Delta[i]\bigg|i \in I\bigg\}$，规定$\Delta[i]$表示玩家$i$（在$\mathrm{H}$中）的策略集合，$\Delta$表示（在$\mathrm{H}$中）策略空间，即有

$\Delta[i] = \bigg\{x[i]\in\mathbb{R}_+^{|S[i]|}\bigg|\sum_{k \in S[i]} x[i,k]=1\bigg\}$

3. 记$u=\bigg\{u[i]\bigg|i \in I\bigg\}$，规定$u[i]$表示玩家$i$（在$\mathrm{H}$中）的收益函数，$u$表示（在$\mathrm{H}$中）收益函数组合，即有

$u[i]:\Delta \to \mathbb R$

；对于$s \in S$和$x \in \Delta$，记$x(s)=\displaystyle\prod_{i \in I}x[i,s[i]]$，则有

$u[i](x)=\sum_{s \in S} x(s)\cdot\pi[i](s)$

补充说明 对于标准式博弈$\Gamma=(I,S,\pi)$及其扩展博弈$\mathrm{H}=(I,\Delta,u)$，为简便起见，假定$I$是有序的。对于$\forall i \in I, \forall x \in \Delta$，$x[i]$可被认为是$i$在$S[i]$上的频率分布策略，即可定义混合策略为线性组合$x[i] \cdot S[i]$，而$\Delta[i] \subset [0{:}1]^{|S[i]|}$是$i$的所有可选的线性组合，如此可记$\Theta[i]$作为$S[i]$的凸包，即有

$\Theta[i] = \bigg\{\delta\cdot S[i]\bigg|\delta \in \Delta[i]\bigg\}=\mathrm{co}(S[i])$

，继而有$S$的凸包

$\Theta = \underset{i \in I}\times \Theta[i]=\mathrm{co}(S)$

。由此可见，$\Delta[i]$和$\Theta[i]$是同构的，$\Delta[i]$可以被视为在$\mathbb{R}^{|S[i]|}$上的一个标准的单位正交基的凸包，且当$|S[i]|<\infty$时，$\Delta[i]$是在$\mathbb{R}^{|S[i]|}$中的一个$|S[i]|-1$维单纯形。因而，$\Delta$和$\Theta$是同构的，如果$\Gamma$是有限的，那么$\Delta = \underset{i \in I}\times \Delta[i] \subset \underset{i \in I}\times [0{:}1]^{|S[i]|}$是$\mathbb{R}^{\prod_{i \in I} |S[i]|}$中的一个凸多面体。

占优策略

对于标准式博弈$\Gamma=(I,S,\pi)$，对于$i \in I$和$x \in S$，记$\mathscr{x}[-i]$是$x$去除$x[i]$后剩余的组合，可以定义下面这些概念：

1. 称$x[i] \in S[i]$弱占优于$y[i] \in S[i]$，记作$x[i] \succcurlyeq y[i]$，如果满足：

1. $\forall z \in S,\space \pi[i](x[i],*\mathscr{z}[-i])\ge\pi[i](y[i],*\mathscr{z}[-i])$
2. $\exists z \in S,\space\pi[i](x[i],*\mathscr{z}[-i])>\pi[i](y[i],*\mathscr{z}[-i])$

2. 称$x[i] \in S[i]$严格占优于$y[i] \in S[i]$，记作$x[i] \succ y[i]$，如果满足：

1. $\forall z \in S,\space x[i] \ne y[i] \implies \pi[i](x[i],*\mathscr{z}[-i])>\pi[i](y[i],*\mathscr{z}[-i])$

3. 称$x[i] \in S[i]$是$i$的弱占优策略，如果满足：

1. $\forall z \in S,\space \forall y[i] \in S[i],\space x[i] \ne y[i] \implies x[i] \succcurlyeq y[i]$

4. 称$x[i] \in S[i]$是$i$的严格占优策略，如果满足：

1. $\forall z \in S,\space \forall y[i] \in S[i],\space x[i] \ne y[i] \implies x[i] \succ y[i]$

未完待续。。。