|
|
博弈论笔记(一)：策略式博弈及其纳什均衡
lec8.pdf
两人游戏：剪刀石头布
规则：选择一种：石头、布、剪刀。选择相同是平局
获胜者选择：
• 石头赢剪刀
• 纸赢石头
• 剪刀赢布
收益矩阵(Payoff Matrix). 从行玩家到列玩家的收益：
\[A=\;\begin{array}r\\P \\ S \\ R\end{array}\lower1.1ex\left[\vphantom{\array{P\\P\\P}}\right.\begin{array}cP & S &R \\ 0 & 1 & -1 \\ -1 & 0 & 1 \\ 1 & -1 & 0\end{array}\lower1.1ex\left.\vphantom{\array{P\\P\\P}}\right]\]
注意：一玩家采用任何确定的(deterministic)策略都可被另一玩家击败
两人零和博弈
给定：$m × n$ 矩阵 $A$。
• 行玩家选择策略$i ∈ \{1, ..., m\}$。
• 列玩家选择策略$j ∈ \{1, ..., n\}$。
• 行玩家支付给列玩家钱$a_{ij}$。
注意：A 的行代表行玩家的确定性策略，而 A 的列代表列玩家的确定性策略。
假设列玩家采用策略 $x$
行玩家要最小化他付给的列玩家的钱, 他的最佳防御是使用最小化 $y^TAx$ 的 $y$：
$$\min _{y} y^{T} A x$$
因此，列玩家要最大化行玩家付给他的钱，他应该选择最大化这些可能性的 $x$：
$$\max _{x} \min _{y} y^{T} A x$$
以线性规划解决Min-Max问题
内部优化很容易：
\[
\min _y y^T A x=\min _i e_i^T A x
\]
（$e_i$ 表示除了第 $i$ 个位置上的 1 之外全为零的向量，即确定性策略 $i)$。
注意：将实数上的最小化约简到有限集上的最小化。
我们有：
\begin{gathered}
\max \left(\min _i e_i^T A x\right) \\
\sum_j x_j=1, \\
x_j \geq 0, \quad j=1,2, \ldots, n 。
\end{gathered}
引入一个标量变量 $v$ 表示内部最小化的值：
\begin{aligned} \max v & \\ v & \leq e_{i}^{T} A x, \quad i=1,2, \ldots, m \\ \sum_{j} x_{j} &=1 \\ x_{j} & \geq 0, \quad j=1,2, \ldots, n \end{aligned}用纯矩阵向量表示法写成：
\begin{array}{r}\max v \\ v e-A x \leq 0 \\ e^{T} x=1 \\ x \geq 0\end{array}($e$表示全1向量).
Min-Max Theorem
Let $x^*$ denote colgirl's solution to her max-min problem.
Let $y^*$ denote rowboy's solution to his min-max problem. Then
\[
\max _x y^{* T} A x=\min _y y^T A x^* .
\]
Proof.
From Strong Duality Theorem, we have
\[
u^*=v^* .
\]
Also,
\[
\begin{aligned}
&v^*=\min _i e_i^T A x^*=\min _y y^T A x^* \\
&u^*=\max _j y^{* T} A e_j=\max _x y^{* T} A x
\end{aligned}
\]
QED |
|
