首页 博弈论

# 正则形式博弈

正则形式博弈 (normal-form game) 也称同时行动博弈 (simultaneous-move game) 或同时博弈 (simultaneous game), 可以用一个元组 (N,A,u)(N, A, u) 描述：

  • N={1,2,…,n}N=\{1,2,\dots,n\} 是玩家 (player) 集合；
  • A=∏i=1nAiA=\prod_{i=1}^nA_i 是所有玩家的动作向量集合，其中 AiA_i 是玩家 ii 的动作 (action) 集合；
  • u=(u1,u2,…,un)u=(u_1,u_2, \dots, u_n) 是所有玩家的效用函数 (utility function) 向量，其中 ui:A→Ru_i: A \to \mathbb{R} 是玩家 ii 的效用函数。

# 收益矩阵表示

收益矩阵 (payoff matrix) 是正则形式博弈的一种常用表示方法，用于表示两个玩家的情况。对于囚徒困境，其收益矩阵如下：

在收益矩阵中，若玩家的每一选择下的结果对应一行的所有情况，则称该玩家为一个行玩家，相应地对应列的玩家称为列玩家。在收益矩阵中，一般行玩家效用写在前，列玩家效用写在后。

“同时” 的含义不是物理上的时间相同，而是在玩家选择动作时不会获得额外信息（例如其他玩家的选择）。

# 基本假设

  1. 理性人假设：每个人都是理性的，即都希望最大化期望效用函数。
  2. 共同知识 (common knowledge) 假设：所有玩家都指导博弈的结构 (N,A,u)(N, A, u), 所有玩家都知道所有玩家都知道博弈的结构 (N,A,u)(N, A, u) ……

# 策略

策略 (strategy) 是选择动作的（随机）方式。若 si(ai)s_i(a_i) 是玩家 ii 选择动作 aia_i 的概率，则 si(ai)s_i(a_i) 满足：

∑ai∈Aisi(ai)=1.\sum_{a_i \in A_i} s_i(a_i) = 1.

若存在 aia_i 使得 si(ai)=1s_i(a_i)=1, 则称 sis_i 为纯策略 (pure strategy), 否则称为混合策略 (mixed strategy).

策略不同于动作，策略是动作的选择方式。

有关策略的一些常用符号包括：

  • s−i=(s1,…,si−1,si+1,…,sn)s_{-i} = (s_1, \dots, s_{i-1}, s_{i+1}, \dots, s_n): 除玩家 ii 以外的其他玩家的策略组合。
  • Δ(X)\Delta(X): 所有定义在集合 XX 上的概率分布的集合。
  • supp(si)={ai∣si(ai)>0}\mathrm{supp}(s_i) = \{a_i|s_i(a_i)>0\}: 支集，策略 sis_i 的非零概率动作集合。

# 解概念与均衡

博弈中的解是一种均衡 (equilibrium), 即没有玩家愿意改变策略。

# 纳什均衡

# 定义

若所有人都不能再提升效用，则称为均衡状态。其严谨定义如下：

若所有玩家的策略组合 (strategy profile, 也称策略剖面)

s∗=(s1∗,s2∗,…,sn∗)\bm{s}^* = (s_1^*, s_2^*, \dots, s_n^*)

满足

ui(si∗,s−i∗)≥ui(si,s−i∗)∀si∈Δ(Ai),∀u∈N,u_i(s_i^*, s_{-i}^*) \geq u_i(s_i, s_{-i}^*) \quad \forall s_i \in \Delta(A_i), \forall u \in N,

其中

ui(s)=ui(si,s−i)=∑a∈As(a)ui(a)=∑a∈Aui(a)∏i∈Nsi(ai).u_i(s) = u_i(s_i, s_{-i}) = \sum_{a \in A} s(a)u_i(a) = \sum_{a \in A}u_i(a)\prod_{i \in N}s_i(a_i).

则称 s∗\bm{s}^* 是博弈的纳什均衡 (Nash equilibrium).

纳什均衡可以简单分类如下：

  • 纯策略纳什均衡 (pure strategy Nash equilibrium): 在均衡 s∗s^* 中，每个 si∗s_i^* 都是纯策略；
  • 混合策略纳什均衡 (mixed strategy Nash equilibrium): 非纯策略的纳什均衡。

# 最优回应

玩家 ii 对其他所有玩家策略组合 s−is_{-i} 的最优回应 (best response) 是

BRi(s−i)=arg max⁡si∈Δ(Ai)ui(si,s−i)={si∣ui(si,s−i)≥ui(si′,s−i)∀si′∈Δ(Ai)}.\begin{aligned} \text{BR}_i(s_{-i}) & = \argmax_{s_i \in \Delta(A_i)}u_i(s_i, s_{-i}) \\ & = \left\{s_i\left| \begin{matrix} u_i(s_i, s_{-i}) \geq u_i(s_i', s_{-i}) \\ \forall s_i' \in \Delta(A_i) \end{matrix} \right.\right\}. \end{aligned}

# 优势策略

玩家 ii 的策略 sis_i 相较于 si′s_i' 是

  • 严格优势策略，若对于 ∀s−i\forall s_{-i}, 都有 ui(si,s−i)>ui(si′,s−i)u_i(s_i, s_{-i}) > u_i(s_i', s_{-i}).
  • 弱优势策略，若对于 ∀s−i\forall s_{-i}, 都有 ui(si,s−i)≥ui(si′,s−i)u_i(s_i, s_{-i}) \geq u_i(s_i', s_{-i}), 且存在 s−is_{-i} 使得 ui(si,s−i)>ui(si′,s−i)u_i(s_i, s_{-i}) > u_i(s_i', s_{-i}).

若对于 ∀si′∈Δ(Ai)\forall s_i' \in \Delta(A_i), sis_i 相较于 si′s_i' 而言都是严格（弱）优势策略，则称 sis_i 是一个严格（弱）优势策略。一般将弱优势策略简称为优势策略 (dominant strategy).

其实这个弱优势策略的定义挺鸡贼的，通过引入一个严格不等，使得弱优势策略具有唯一性，但是由于定义更加严格，其不一定存在。

性质 严格优势策略或弱优势策略是唯一的，且是纯策略。

优势策略并非一定存在。

# 优势策略纳什均衡

若在纳什均衡 s∗\bm{s}^* 中，对于所有玩家 ii, 都有 si∗s_i^* 是 ii 的严格（弱）优势策略，则称 s∗\bm{s}^* 是严格（弱）优势策略纳什均衡。

条件：

  • 有限博弈 (finite game)
    • ∣N∣|N| 有限，且 ∀i,Ai\forall i, A_i 有限

性质 若某有限博弈存在严格优势策略，则该策略是纯策略的纳什均衡，且是该博弈的唯一纳什均衡。

# 纳什均衡的存在性

借助布劳尔 (Brouwer) 不动点定理。

# 极小极大策略和极大极小策略

# 极小极大策略

极小极大策略 (minimax/minmax strategy) 是一种防御策略，即选择使对手效用函数最小化的策略：

arg min⁡simax⁡s−iui(si,s−i).\argmin_{s_i}\max_{s_{-i}}u_i(s_i, s_{-i}).

# 极大极小策略

极大极小策略 (maximin/maxmin strategy) 是一种进攻策略，即选择使自身效用函数最大化的策略：

arg max⁡simin⁡s−iui(si,s−i).\argmax_{s_i}\min_{s_{-i}}u_i(s_i, s_{-i}).

# 零和博弈