博弈论02——性别之战、纯和混合纳什均衡
纳什均衡第一部分
性别之战 The battle of the sexesPure Nash equilibrium 纯纳什均衡best response 最佳响应Pure Nash equilibrium 纯纳什均衡寻找纯纳什均衡的方法
The battle of the sexes, weakly dominated strategies and burning money 性别之战、弱势主导策略和烧钱Nash Theorem 纳什定理The poisoned drink game 毒饮游戏
Mixed strategy Nash equilibrium 混合策略纳什均衡基本概念Zero-Sum Mixed Strategy Game 零和混合策略博弈
性别之战 The battle of the sexes
背景： Alice 和 Bob 这两位玩家是朋友，他们想见面喝杯咖啡。Alice 喜欢去 Costa，Bob 更喜欢去星巴克，但最重要的是，对他们来说最重要的是去同一个地方，这样他们才能真正见面。
接上文，可以看出无论是迭代主导策略还是迭代消除弱主导策略都无法解决这个问题。由此我们知道并非每个游戏都能以这种方式完全解决。
Pure Nash equilibrium 纯纳什均衡
best response 最佳响应
Definition 2.3 Consider a game and suppose each player i chooses a strategy
s
i
∈
S
i
s_i ∈ S_i
si∈Si. Then for player
j
j
j, the strategy
s
j
s_j
sj is a best response to the strategies of the remaining players if no other strategy gives player
j
j
j a higher payoff, when the strategies of the other players are unchanged. That is, if 考虑一个博弈，假设每个玩家 i 选择一个策略
s
i
∈
S
i
s_i ∈ S_i
si∈Si。那么，对于玩家
j
j
j来说，当其他玩家的策略保持不变时，如果没有其他策略能给玩家
j
j
j带来更高的收益，那么策略
s
j
s_j
sj是对其余玩家策略的最佳回应。也就是说，如果
p
j
(
s
1
,
…
,
s
n
)
≥
max
x
∈
S
j
p
j
(
s
1
,
…
,
s
j
−
1
,
x
,
s
j
+
1
,
…
,
s
n
)
p_j(s_1, \ldots, s_n) \geq \max_{x \in S_j} p_j(s_1, \ldots, s_{j-1}, x, s_{j+1}, \ldots, s_n)
pj(s1,…,sn)≥x∈Sjmaxpj(s1,…,sj−1,x,sj+1,…,sn)
策略
s
j
s_j
sj是对其余玩家策略的最佳回应。
Pure Nash equilibrium 纯纳什均衡
Definition 2.4 A pure Nash equilibrium of a game is a strategy profile in which the strategy of each player is a best response to the strategies of all the other players. 游戏的纯纳什均衡是一种策略配置，其中每个玩家的策略都是对所有其他玩家的策略的最佳响应。
寻找纯纳什均衡的方法
Eg: 画框法
所有玩家都做出最佳反应的策略配置文件正是游戏的纯纳什均衡。 得到一个纯纳什均衡，就是4-6。
Eg: 上述的性别之战 得到两个纯纳什均衡。
The battle of the sexes, weakly dominated strategies and burning money 性别之战、弱势主导策略和烧钱
在性别之战中添加了烧钱的威胁，最后结果如下图 使用主导策略，无法缩写游戏尺寸； 使用弱主导策略，结果如下图： 使用best responses（画圈）法，结果如下图： 可以看到有四个纯纳什均衡，但在迭代消除弱主导策略之后，只保留了其中的一个。
结论： 迭代消除主导策略——虽然可能不会缩小游戏size，但可以保留全部的纯Nash equilibria 迭代消除弱主导策略——缩小size，但可能会漏结果 best response法——得到全部的纯Nash equilibria
窍门：迭代消除法，Player II 自己一列和自己的另一列对比大小。best response法，自己这一列找出这一列中最大的画框。
Nash Theorem 纳什定理
There must be at least one Nash equilibrium for all finite games. There are no equilibria in pure strategies, but there’s another type of equilibrium. 所有有限博弈至少存在一个纳什均衡。纯策略博弈中不存在均衡，但存在另一种均衡。 Finite game has a finite number of players and a finite number of strategies. 有限博弈指有限的玩家和策略
The poisoned drink game 毒饮游戏
这个游戏无法通过纯Nash equilibria 解决，如下。 If no equilibrium exists in pure strategies, one must exist in mixed strategies. 如果纯策略中不存在均衡，那么混合策略中一定存在均衡。
Mixed strategy Nash equilibrium 混合策略纳什均衡
基本概念
Mixed strategy : A mixed strategy is a probability distribution over two or more pure strategies. 混合策略：两个或多个纯策略的概率分布
the players choose randomly among their options in equilibrium. 玩家在均衡状态下随机选择他们的选项If mixtures are mutual best responses, the set of strategies is a mixed strategy Nash equilibrium. 如果混合策略是相互最优的响应，则该策略集为混合策略纳什均衡
Zero-Sum Mixed Strategy Game 零和混合策略博弈
A mixed strategy algorithm implies that allows us to find what sort of mixed strategies for each of these players makes the other guy indifferent. 混合策略算法意味着我们可以找到每个玩家采用哪种混合策略会让其他玩家无动于衷。
We need to find a mixed strategy that leaves player two indifferent between selecting left and right. If player two gets the same payoff for selecting left, on average, as she does for selecting right, then it doesn’t matter which strategy she chooses. So, she can choose a mixed strategy — a randomization between left and right. 我们需要找到一个混合策略，让二号玩家对选择左或右无差异。如果二号玩家选择左和选择右的平均收益相同，那么她选择哪种策略都无所谓。因此，她可以选择一个混合策略——在左和右之间随机化。
If that randomization leaves player one indifferent between choosing up or down, then that means he is perfectly satisfied also maintaining his original mixed strategy. And so, that means neither player is going to have incentive to change his or her strategy. 如果这种随机化让一号玩家对选择上或下无差异，那么这意味着他完全满意于维持原来的混合策略。也就是说，两个玩家都没有动机改变自己的策略。
Therefore, we end up in a mixed strategy Nash equilibrium, with those probabilities between the two strategies. 因此，我们最终得到了一个混合策略纳什均衡，即两种策略之间的概率。
玩家一的混合策略：
EU
L
=
EU
R
σ
U
(
−
3
)
+
(
1
−
σ
U
)
(
1
)
=
σ
U
(
2
)
+
(
1
−
σ
U
)
(
0
)
−
3
σ
U
+
1
−
σ
U
=
2
σ
U
1
−
4
σ
U
=
2
σ
U
1
=
6
σ
U
σ
U
=
1
6
\begin{aligned} \text{EU}_L &= \text{EU}_R \\ \sigma_U(-3) + (1 - \sigma_U)(1) &= \sigma_U(2) + (1 - \sigma_U)(0) \\ -3\sigma_U + 1 - \sigma_U &= 2\sigma_U \\ 1 - 4\sigma_U &= 2\sigma_U \\ 1 &= 6\sigma_U \\ \sigma_U &= \frac{1}{6} \end{aligned}
EULσU(−3)+(1−σU)(1)−3σU+1−σU1−4σU1σU=EUR=σU(2)+(1−σU)(0)=2σU=2σU=6σU=61
E
U
L
EU_L
EUL是玩家二选择Left时，玩家一的期望收益
E
U
R
EU_R
EUR是玩家二选择Right时，玩家一的期望收益我们的目的，就是希望玩家一的概率，可以使得玩家二选哪个对玩家一都没有影响，达到平衡
σ
U
\sigma_U
σU是玩家一选择Up的概率
我们利用让另一个玩家选择无效，求出自己的策略——自己的概率就是自己的混合策略
玩家二的混合策略： 同上理
EU
U
=
EU
D
EU
U
=
σ
L
(
3
)
+
(
1
−
σ
L
)
(
−
2
)
EU
D
=
σ
L
(
−
1
)
+
(
1
−
σ
L
)
(
0
)
σ
L
(
3
)
+
(
1
−
σ
L
)
(
−
2
)
=
σ
L
(
−
1
)
+
(
1
−
σ
L
)
(
0
)
3
σ
L
−
2
+
2
σ
L
=
−
σ
L
6
σ
L
=
2
σ
L
=
1
3
\begin{aligned} &\text{EU}_U = \text{EU}_D \\ &\text{EU}_U = \sigma_L(3) + (1 - \sigma_L)(-2) \\ &\text{EU}_D = \sigma_L(-1) + (1 - \sigma_L)(0) \\ \\ &\sigma_L(3) + (1 - \sigma_L)(-2) = \sigma_L(-1) + (1 - \sigma_L)(0) \\ &3\sigma_L - 2 + 2\sigma_L = -\sigma_L \\ &6\sigma_L = 2 \\ &\sigma_L = \frac{1}{3} \end{aligned}
EUU=EUDEUU=σL(3)+(1−σL)(−2)EUD=σL(−1)+(1−σL)(0)σL(3)+(1−σL)(−2)=σL(−1)+(1−σL)(0)3σL−2+2σL=−σL6σL=2σL=31