标准式博弈

标准式博弈

对于$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 \piJ = \underset{j \in J}\times \pij \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]]$，则有

   $$ui=\sum_{s \in S} x(s)\cdot\pii$$

补充说明 对于标准式博弈$\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 \pii\ge\pii$
   2. $\exists z \in S,\space\pii>\pii$

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 \pii>\pii$

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]$

---

未完待续。。。