【博弈论 学习】Chapter1. 策略式博弈与Nash均衡

前言

电子书链接
可能需要科学上网。

在博弈论和概率论中，支撑集（support set）是指在混合策略中被赋予正概率的纯策略的集合。换句话说，支撑集包含了所有在混合策略中实际可能被选择的纯策略。

混合策略是指玩家在决策时不选择单一的纯策略，而是根据某种概率分布在多个纯策略之间进行选择。混合策略引入了随机性，使得玩家的选择不再是确定的。

符号标记

• 混合策略${\sigma }_i$，混合策略空间${\Sigma }_i$
• 纯策略$s_i$，纯策略空间$S_i$
  紧集的性质

1. 闭性：在$R^n$中紧集是闭集。
2. 有界性：在$R^n$中，紧集是有界的。
3. 连续函数上的性质：在紧集上，连续函数达到其最大值和最小值（极值定理）。
4. 有限交性质：在拓扑空间中，紧集的任意有限个闭集的交集是非空的。

1.1策略式博弈和重复严格优势

1.1.1 策略式博弈

定义：一个策略式博弈由三种元素构成$\{[N],({\mathcal{S}}_i{)}_{i\in [N]},(u_i{)}_{i\in [N]}\}$，其中$N$表示参与人集合，纯策略空间(pure strategy space)$({\mathcal{S}}_i{)}_{i\in [N]}$和收益函数$(u_i{)}_{i\in [N]}$。对于每一个策略组合$s$，每个参与人都可以给出其对应的效用。我们通常标记$i$的所有竞争对手为$-i$。

双人零和博弈：效用总和为常数，常数设为0只是为了标准化。

混合策略是纯策略的一种概率分布。

一种混合策略下，参与人的收益是参与人$i$的混合概率${\sigma }_i$的线性函数。

1.1.2 劣势策略

在某一个博弈过程中，当玩家$i$采取某一策略获得的收益严格小于采取另一策略获得的收益，则称该策略为劣势策略。可以不断剔除劣势策略，该过程称为重复优势。

在以上博弈过程中，策略M不劣于U和D，但是混合策略 { 0.5 , 0 , 0.5 } \{0.5, 0, 0.5\} {0.5,0,0.5}优于只选择M的纯策略。一个纯策略可能劣于一个混合策略，即使该策略不劣于任何其他的纯策略

劣势策略的定义1.1：

$$\begin{gathered} \exists {\sigma }_i^{\prime }\in {\Sigma }_i \\ {u}_i({\sigma }_i^{\prime },s_{-i})>u_i(s_i,s_{-i}),s_{-i}\in S_{-i} \end{gathered}$$
则称纯策略$s_i$对玩家$i$是严格劣势的。
若上述的不等式是弱不等式，且对至少一个$s_{-i}$成立，则称纯策略是弱劣势的。

注：即只要存在一个混合策略在某一条件下大于一个纯策略，则该纯策略就是劣势策略。

注意：对手采取混合策略实际上是对手采取纯策略的凸组合。因此

1.1.3剔除劣势策略的应用

囚徒困境

二级价格拍卖

1.2 纳什均衡

1.2.1 定义

每个人的混合策略都弱强于某一纯策略。纯策略的Nash均衡是上式的纯策略组合版本。

需要说明的是，严格均衡并不一定存在，在某些博弈问题中，仅存在混合策略均衡。同时纯策略均衡也不一定是严格的。

如果某个单个策略组合在重复剔除严格劣势策略后遗留下来，则该策略一定是该博弈中唯一的Nash均衡。

1.2.2纯策略均衡的例子

古诺垄断竞争模型

霍特林竞争模型

多数投票

1.2.3 纯策略均衡不存在的例子

硬币配对

观察博弈

1.2.4 多重nash均衡/聚点/帕累托最优

性别战争和过桥（斗鸡）问题的博弈：

以上问题均存在两个纯策略Nash均衡和一个混合策略Nash均衡，其中混合策略的概率求解通过求解参与者两种策略无差别的条件来确定。

聚点

帕累托优势

帕累托优势（Pareto Improvement）
帕累托优势指的是一种资源配置的改变，使得至少有一个人变得更好，而没有任何人变得更差。在这种情况下，资源的重新分配提高了整体福利。

帕累托均衡/帕累托均衡/帕累托有效性

帕累托均衡（或帕累托最优）是一种资源配置状态，在这种状态下，不可能通过重新分配资源来使任何一个人变得更好而不使其他人变得更差。换句话说，任何进一步的帕累托改进都是不可能的。

1.2.5 作为学习和进化结果的Nash均衡

古诺-nash均衡调整

该过程只有一个Nash均衡点，因此其收敛是稳定的。

有BCD三个均衡点，但是C的不稳定的。

1.3 Nash均衡的存在性和性质

1.3.1混合均衡策略的存在性

定理1.1. 每个有限策略式博弈存在混合策略均衡

1.3.3具有连续收益的无限博弈的Nash均衡的存在性