博弈论 | GameTheory ¶

约 2819 个字预计阅读时间 11 分钟

分类 ¶

局中人是否允许合作：非合作博弈、合作博弈
策略的数目：有限策略博弈 - 无限策略博弈
策略选择是否具有概率随机性：纯策略博弈、混合策略博弈
策略与时间的关系：静态博弈、动态博弈
参与人对问题信息结构的了解程度：完全信息博弈、不完全信息博弈
数学模型：矩阵博弈、连续博弈、微分博弈、阵地博弈、凸博弈、随机博弈

问题与基本概念 ¶

局中人 (Players)

策略集（Strategies）: 完整性、多样性、不可观察性

赢得函数 / 支付函数 (Payoff function)

信息 (infomation)

action:variable

outcome equilibrium: 均衡 , 所有参与者最优策略组合 rules:players,action&outcome

矩阵博弈：研究有限零和博弈的最优策略。
理性博弈原则：决策主体追求自身利益最大化。
最优策略对极大极小值和极小极大值：通过求解极大极小值和极小极大值来找到最优策略。
纳什均衡解的意义：研究解的可能性，包括单个解、多个解或无纯策略解等情况

在众多对策模型中，占有重要地位的是二人有限零和对策，即在对策只有两个局中人，各自的策略集只含有限个策略，每局中两个局中人的得失总和为零（即一个局中人的赢得恰为另一个局中人所输掉的值），这类对策又称为矩阵对策。

矩阵——纯策略博弈 ¶

博弈模型 $G = {I, I I, S_{1}, S_{2}, A}$

局中人 $I 、 I I$
策略集 $S_{1} = {a_{1}, a_{2}, \dots, a_{m}}$ $S_{2} = {b_{1}, b_{2}, \dots, b_{n}}$
局中人 $I$ 的赢得矩阵： $A$

A = [\begin{array}{cccc} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋮ \\ a_{m 1} & a_{m 2} & \dots & a_{m n} \end{array}]

局中人 $I I$ 的赢得矩阵： $- A^{T}$

共许原则 ¶

双方均无改变策略的意愿

自身利益最大化原则 ¶

自身的赢得值尽可能大

问题：不确定对方决策情况下的最优决策
准则：从最坏的预期中选则最好的（悲观准则）一种保守而贪心的准则 “做最坏的打算，争取最好的结果”

局中人 $I$ 最大预期赢得（赢得指自身最小收益）

极大极小值： $max_{i} min_{j} a_{i j}$

局中人 $I I$ 最小预期损失（损失指对手最大收益）

极小极大值： $min_{j} max_{i} a_{i j}$

极大极小值与极小极大值

$max_{i} min_{j} a_{i j} \leq min_{j} max_{i} a_{i j}$
证明：对于 $\forall j$ ，有

min_{j} a_{i j} \leq a_{i j}

max_{i} \underset{第 i 行 最 小 值}{min_{j} a_{i j}} \leq \underset{第 j 列 最 大 值}{max_{i} a_{i j}}

故

max_{i} min_{j} a_{i j} \leq min_{j} max_{i} a_{i j}

均衡解 ¶

矩阵鞍点

鞍点指的是矩阵中的一个元素，它是所在行的最大值，并且是所在列的最小值
判断鞍点的一个充分条件是：函数在一阶导数为零处（驻点）的黑塞矩阵为不定矩阵。

如果存在

max_{i} min_{j} a_{i j} = min_{j} max_{i} a_{i j} = a_{i^{*} j^{*}} ≜ V_{G}

则 $(a_{i^{*}}, b_{j^{*}})$ 为矩阵博弈的最优纯策略对，也称为最优局势。 $V_{G}$ 称为博弈值。

矩阵博弈最优纯策略对存在的充要条件是存在鞍点

非常强的条件证明：

1、必要性

\begin{aligned} max_{i} min_{j} a_{i j} = min_{j} max_{i} a_{i j} \\ \Rightarrow & i^{*}, j^{*}, min_{j} a_{i j *} = max_{i} min_{j} a_{i j} = min_{j} max_{i} a_{i j} = max_{i} a_{i j *} \\ \Rightarrow & a_{i j *} \geq min_{j} a_{i j *} = max_{i} min_{j} a_{i j} = min_{j} max_{i} a_{i j} = max_{i} a_{i j *} \\ \Rightarrow & max_{i} a_{i j *} = a_{i * j *} = min_{j} a_{i j *} \\ a_{i j *} \leq a_{i * j *} \leq a_{i * j} \end{aligned}

2、充分性

\Rightarrow max_{i} a_{i j *} \leq a_{i * j *} \leq min_{j} a_{i * j} \Rightarrow min_{j} max_{i} a_{i j} \leq a_{i * j *} \leq max_{i} min_{j} a_{i j} max_{i} min_{j} a_{i j} \leq min_{j} max_{i} a_{i j} max_{i} min_{j} a_{i j} = min_{j} max_{i} a_{i j}

鞍点解的博弈解释：没有一方愿意单方面改变策略，因为单方面改变策略均无法改善自身的赢得值，更多情况下反有损害。（共许原则）

性质 ¶

1、无差别性

若 $(a_{1 i}, b_{j 1})$ 和 $(a_{2 i}, b_{j 2})$ 是对策的两个解，

则

a_{1 i j} = a_{2 i j}

A = [\begin{array}{cccc} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋮ \\ a_{m 1} & a_{m 2} & \dots & a_{m n} \end{array}]

2、可交换性

若 $(a_{1 i}, b_{j 1})$ 和 $(a_{1 i}, b_{j 2})$ 是对策的两个解，则 $(a_{1 i}, b_{j 2})$ 和 $(a_{2 i}, b_{j 1})$ 也是对策的解。

A = [\begin{array}{cccc} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋮ \\ a_{m 1} & a_{m 2} & \dots & a_{m n} \end{array}]

矩阵——混合策略博弈 ¶

模型 ¶

$G^{*} = {S_{1}^{*}, S_{2}^{*}; E}$

混合策略集

$S_{1}^{*} = {x \in R^{m} ∣ x_{i} \geq 0, i = 1, 2, \dots, m; \sum_{i = 1}^{m} x_{i} = 1}$

$x_{i}$ 为局中人 $I$ 执行纯策略 $a_{i}$ 的概率

$S_{2}^{*} = {y \in R^{n} ∣ y_{j} \geq 0, j = 1, 2, \dots, n; \sum_{i = 1}^{n} y_{j} = 1}$

$y_{j}$ 为居中人 $I I$ 执行纯策略 $b_{j}$ 的概率

局中人 $I$ 的赢得函数： $E (x, y) = x^{T} A y = \sum_{i = 1}^{m} \sum_{j = 1}^{n} a_{i j} x_{i} y_{j}$

局中人 $I I$ 的赢得函数： $- E (x, y)$

混合策略的取值在多次博弈中可看作概率，一次博弈中可看作偏好。
混合策略集是无穷集合，纯策略是混合策略的特例。
分析问题时，首先考虑纯策略博弈，当纯策略解不存在时，就考虑混合策略博弈。因此混合策略博弈也可以用 $G = {S_{1}, S_{2}; A}$ 表示。

理性决策

局中人 $I$ 的最大预期赢得： $max_{x \in S_{1}^{*}} min_{y \in S_{2}^{*}} E (x, y)$
局中人 $I I$ 的最小预期损失： $min_{y \in S_{2}^{*}} max_{x \in S_{1}^{*}} E (x, y)$

两者关系： $max_{x \in S_{1}^{*}} min_{y \in S_{2}^{*}} E (x, y) \leq min_{y \in S_{2}^{*}} max_{x \in S_{1}^{*}} E (x, y)$

混合策略 $x = {[x_{1}, x_{2}, \dots, x_{m}]}^{T} y = {[y_{1}, y_{2}, \dots, y_{n}]}^{T}$
混合局势 $(x, y)$

均衡解 ¶

最优混合策略对

max_{x \in S_{1}^{*}} min_{y \in S_{2}^{*}} E (x, y) = min_{y \in S_{2}^{*}} max_{x \in S_{1}^{*}} E (x, y) = E (x^{*}, y^{*}) ≜ V_{G}

最优混合策略存在的充要条件：存在鞍点

E (x, y^{*}) \leq E (x^{*}, y^{*}) \leq E (x^{*}, y)

平衡局势 $(x^{*}, y^{*})$

定理：一定存在混合策略意义下的矩阵博弈均衡解

证明思路：鞍点条件一定有解。

均衡解的性质 ¶

对称博弈性质 ¶

如果博弈问题具有如下对称性：

A = - A^{T} 自身角度的赢得矩阵相同

\Rightarrow T_{1} (G) = T_{Π} (G) a_{i j} = {\begin{cases} - a_{i j} & i \neq j \\ 0 & i = j \end{cases}

\Rightarrow V_{G} = E (x^{*}, y^{*}) = \sum_{j = 1}^{n} \sum_{i = 1}^{m} a_{i j} x_{i}^{*} y_{j}^{*} = - V_{G} = 0 最优策略时无赢家

石头剪刀布问题

解集不变性 ¶

赢得矩阵严格单调变换下的解集不变性

博弈 : $G_{1} = {S_{1}, S_{2}; A_{1}} G_{2} = {S_{1}, S_{2}; A_{2}}$

A_{2} = A_{1} + L^{*} 1_{m \times n} \Rightarrow T (G_{1}) = T (G_{2}) V_{G_{1}} = V_{G_{2}} + L

A_{2} = a A_{1}, a > 0 \Rightarrow T (G_{1}) = T (G_{2}) V_{G_{1}} = a V_{G_{2}}

解集 $T (G)$ : 博弈 $G$ 的均衡解集合。

证明：上述变换只改变了赢得矩阵元素的数值，不改变相对大小关系。

互补松弛性 ¶

x_{i}^{*} > 0 \Rightarrow \sum_{j = 1}^{n} a_{i j}^{*} y_{j}^{*} = v^{*} = E (x^{*}, y^{*}) y_{j}^{*} > 0 \Rightarrow \sum_{i = 1}^{m} a_{i j}^{*} x_{i}^{*} = w^{*} = E (x^{*}, y^{*})

如果某条纯策略可能被选择，则该纯策略下对手的最优混合策略下的赢得值必为 $V_{G}$ 。

\sum_{i = 1}^{n} a_{i j} y_{j} < v^{*} = E (x^{*}, y^{*}) \Rightarrow x_{i}^{*} = 0 \sum_{i = 1}^{m} a_{i j} x_{i}^{*} > w^{*} = E (x^{*}, y^{*}) \Rightarrow y_{j}^{*} = 0

如果某条纯策略下对手的最优混合策略的赢得值比 $V_{G}$ 更好，则该纯策略无被选择可能。

矩阵——均衡解的求解 ¶

互补松弛性定理 ¶

对偶理论 ¶

线性规划解 ¶

双矩阵 ¶

（二人有限非零和博弈）

模型 ¶

G = {S_{1}, S_{2}; A, B}

局中人 I、II

策略集

S_{1} = {α_{1}, α_{2}, \dots, α_{m}}

S_{2} = {β_{1}, β_{2}, \dots, β_{n}}

局中人 I 的赢得矩阵 $A$

局中人 II 的赢得矩阵 $B$

纯策略 Nash 均衡 ¶

满足以下条件的策略对 $(α_{i^{*}}, β_{j^{*}})$

\begin{aligned} a_{i^{*}, j^{*}} \geq a_{i, j^{*}} i = 1, 2, \dots, m \\ b_{i^{*}, j^{*}} \geq b_{i^{*}, j} j = 1, 2, \dots, n \end{aligned}

没有一个局中人愿意单方面改变策略

A = [\begin{array}{cc} - 9 & 0 \\ - 15 & - 1 \end{array}] B = [\begin{array}{cc} - 9 & - 15 \\ 0 & - 1 \end{array}]

例子：囚徒困境——占优策略 Nash 均衡

混合策略 Nash 均衡 ¶

赢得函数

E_{1} (x, y) = x^{T} A y = \sum_{i = 1}^{m} \sum_{j = 1}^{n} a_{i j} x_{i} y_{j} E_{2} (x, y) = x^{T} B y = \sum_{i = 1}^{m} \sum_{j = 1}^{n} b_{i j} x_{i} y_{j}

Nash 混合策略均衡点

满足以下条件的策略对 $(x *, y *)$

\begin{aligned} E_{1} (x^{*}, y^{*}) \geq E_{1} (x, y^{*}) x \in S_{1}^{*} \\ E_{2} (x^{*}, y^{*}) \geq E_{2} (x^{*}, y) y \in S_{2}^{*} \end{aligned}

如果纯策略均衡解存在，也是混合策略的均衡解。

$n$ 人有限策略博弈至少存在一个 Nash 均衡点（包括纯策略和混合策略）（Nash, 1950）

Pareto 最优 ¶

允许合作下的博弈问题为多目标优化问题 :

目标 1: $max_{x_{i} \in S_{1}^{*}, y_{j} \in S_{2}^{*}} E_{1} (x, y)$
目标 2: $max_{x_{i} \in S_{1}^{*}, y_{j} \in S_{2}^{*}} E_{2} (x, y)$

Pareto 最优解 $(x^{*}, y^{*})$ : 不存在超优 $(x^{*}, y^{*})$ 的策略对。

$(x_{1}, y_{1})$ 超优 $(dominate) (x_{2}, y_{2})$ :

\begin{array}{r} E_{1} (x_{1}, y_{1}) \geq E_{1} (x_{2}, y_{2}) \\ E_{2} (x_{1}, y_{1}) \geq E_{2} (x_{2}, y_{2}) \end{array}

且至少有一个不等式严格成立。

纯策略 Nash 均衡解

III	坦白	抗拒
坦白	(-9,-9) Nash 均衡	(0,-15)
抗拒	(-15,0)	(-1,-1)Pareto 最优解

严格意义下的解：满足可交换性和无差别性的 Pareto 最优均衡解

Nash 均衡解的充要条件

定理 : $(x^{*}, y^{*})$ 是 $G = {S_{1}, S_{2}; A, B}$ 的 Nash 均衡解的充要条件为 :

\begin{aligned} \sum_{j = 1}^{n} a_{i j} y_{j}^{*} \leq E_{1} (x^{*}, y^{*}) i = 1, 2, \dots, m \Rightarrow A y^{*} \leq E_{1} (x^{*}, y^{*}) 1_{m} \\ \sum_{i = 1}^{m} b_{i j} x_{i}^{*} \leq E_{2} (x^{*}, y^{*}) j = 1, 2, \dots, n \Rightarrow B^{T} x^{*} \leq E_{2} (x^{*}, y^{*}) 1_{n} \\ x \in S_{1}^{*} y \in S_{2}^{*} \end{aligned}