读书笔记: 博弈论导论 - 06 - 混合的策略

扑克投资家

2017-12-26

关注关注

读书笔记: 博弈论导论 - 06 - 混合的策略

混合的策略

本文是Game Theory An Introduction (by Steven Tadelis) 的学习笔记。

策略，信念和期望收益

混合策略
玩家i的有限纯策略集合$S_i = {s_{i1}, s_{i2}, \cdots, s_{im}}$。
将$\Delta S_i$定义为$S_i$的单纯形，是在$S_i$上所有概率分布的集合。
玩家i的一个混合策略(mixed strategy)是$\sigma_i \in \Delta S_i$，
\[\sigma_i = (\sigma_i(s_{i1}), \sigma_i(s_{i2}), \cdots, \sigma_i(s_{im})) \\where \\\sigma_i(s_{i}) \text{ : the probability that player i plays s_{i}}\]

两个明显的条件:
\[\sigma_i(s_{i}) \geq 0, \forall s_i \in S_i \\\sum_{s_i \in S_i} \sigma_i(s_{i}) = 1\]

$\Delta S_i$的例子：(rock-paper-scissor)
$\Delta S_i$ = {(\sigma_i(R), \sigma_i(P), \sigma_i(S)) : \sigma_i(R), \sigma_i(P), \sigma_i(S) \geq 0, \sigma_i(R) + \sigma_i(P) + \sigma_i(S) = 1}$
表示所有$(\sigma_i(R), \sigma_i(P), \sigma_i(S))$对，使得每个值都大于等于0，并且每个值的和为1。
$\sigma(\dot)$支持策略$s_i$($s_i$ is in the support of $\sigma(\dot)$)
给定一个玩家i的混合策略$\sigma(\dot)$，如果$\sigma(s_i) > 0$，则称$\sigma(\dot)$支持纯策略$s_i$。
连续策略集的混合策略
玩家i的纯策略集合$S_i$是一个值区间，则玩家i的一个混合策略是累积分布函数$F_i : S_i \to [0, 1], \ where \ F_i(x) = Pr{s_i < x>}$。
如果$F_i(\dot)$在密度$f_i(\dot)$上可微分，并且$f_i(\dot) > 0$，则称$F_i(\dot)$支持纯策略$s_i$。
信念(belief)
信念$\pi_i \in \Delta S_{-i}$代表玩家i认为对手采用$s_{-i} \in S_{-i}$的概率。
期望收益(Expected Payoffs)
玩家i选择策略$s_i \in S_i$，并且对手选择混合策略$\sigma_{-i} \ \Delta_{-i}$，的期望收益:
\[v_i(s_i, \sigma_{-i}) = \sum_{s_{-i} \in S_{-i}} \sigma_{-i}(s_{-i}) v_i(s_i, s_{-i})\]
玩家i选择混合策略$\sigma_i \in \Delta S_i$，并且对手选择混合策略$\sigma_{-i} \ \Delta_{-i}$，的期望收益:
\[v_i(\sigma_i, \sigma_{-i}) = \sum_{s_{i} \in S_{i}} \sigma_{i}(s_{i}) v_i(s_i, s_{-i}) = \sum_{s_i \in S_i} ( \sum_{s_{-i} \in S_{-i}} \sigma_{i}(s_{i}) \sigma_{-i}(s_{i-}) v_i(s_i, s_{-i}) )\]
混合策略的纳什均衡
混合策略组合$\sigma^* = (\sigma_1^*, \sigma_2^*, \cdots, \sigma_n^*)$是一个纳什策略，如果对于每个玩家$\sigma_i^*$都是最佳响应。
\[v_i(\sigma_i^*, \sigma_{-i}^*) \geq v_i(\sigma_i, \sigma_{-i}^*), \ \forall \sigma_i \in \Delta S_i\]

推论 6.1

如果$\sigma^*$是一个纳什博弈，并且$\sigma^*支持$s_i$和$s'_i$,则
$v_i(s_i, \sigma_{-i}^*) = v_i(s'_i, \sigma_{-i}^*) = v_i(\sigma^*, \sigma_{-i}^*)$

Rock-Paper-Scissor

断言 6.1:

如果一个玩家选择纯策略，另一个玩家选择混合策略，则不存在纳什均衡。

断言 6.2:

如果至少有一个玩家选择只有两个纯策略的混合策略，则不存在纳什均衡。

严格劣势策略的迭代消除和可合理化(IESDS and Rationalizability)

严格劣势
$s'_i \in S_i$严格劣势于$\sigma_i \in \Delta S_i$，如果满足条件：
\[v_i(\sigma_i, s_{-i}) > v_i(s'_i, s_{-i}), \ \forall s_{-i} \in S_{-i} \\\]
不可能是一个最佳响应
对于玩家i的混合策略$\sigma_i \in \Delta S_i$，这个混合策略作为最佳响应的对手混合策略$\sigma_i \in BR_i(\sigma_{-1})$，如果对手的任何混合策略$\sigma_{-1} \in \Delta S_{-i}$都不在玩家i的信念中，则$\sigma_i \in \Delta S_i$不可能是一个最佳响应。

断言

一个劣势混合策略$sigma_i$不可能是一个最佳响应。

推论 6.2

任何两人博弈中，策略$sigma_i$是一个严格劣势纯策略，当且仅当策略$sigma_i$不可能是一个最佳响应。

纳什存在定理

纳什存在定理(Nash's existence Theorem)

任何普通形式、具有限策略集合的博弈存在一个纳什均衡的混合策略。
纳什存在定理的证明用到了不动点定理。

布劳威尔不动点定理(Brouwer's Fixed-Point Theorem)

如果f(x)是一个连续函数从域[0, 1]到[0, 1]$f:[0, 1] \to [0, 1]$,则存在至少一个点$f(x^*) = x^*, x^* \in [0, 1]$。
证明过程简介：连续函数f(x)一定和函数$f_1(x) = x$至少有一个交点。

最佳响应对应(collection of best response correspondence)
最佳响应对应集合$BR \equiv BR_1 \times BR_2 \times \cdots \times BR_n$，映射$\Delta S \equiv \Delta S_1 \times \Delta S_2 \times \cdots \times \Delta S_n $ 到自身。
也就是说：$BR : \Delta S \rightrightarrows \Delta S$, $BR(\sigma) \subset \Delta S, \ for \ \sigma \in \Delta S$

角谷不动点定理(Kakutani Fixed-Point Theorem)

一个对应$C: X \rightrightarrows X$有一个不动点，如果以下四个条件都满足：

X是非空的，紧凑的，$\mathbb{R}^n$的凸子集
C(x)对于所有的x都非空。
C(x)对于所有的x都是凸的。
C有一个闭合图。

凸的(convex)
集合$X \subseteq \mathbb{R}^n$是凸的，如果集合X中任何两点的连线上的点都在集合X中。
闭合的(closed)
集合$X \subseteq \mathbb{R}^n$是闭合的，如果集合X边缘点在集合X中。(0, 1]是非闭合的，[0, 1]是闭合的。
紧凑的(compact)
集合$X \subseteq \mathbb{R}^n$是紧凑的，如果集合X是闭合并且有界。[0, 1]是紧凑的，$[0, ∞]$是非紧凑的。
闭合图(closed graph)
图$C: X \rightrightarrows X$是闭合图, 如果C是闭合的。