[ 博弈论  ]

运筹学:博弈论笔记

博弈论 (Game Theory) 也叫对策论。在典型的对策问题中,每个局中人都有选择自己策略的能力,并且任何一方的赢得不仅仅取决于自己的策略,还取决于竞争对手的策略。

一、基本概念

具有竞争或对抗性质的行为称为对策行为,刻画对策行为过程的模型称为对策模型对策

对策的三要素

  1. 局中人:一个对策行为中的参加者。一般用 $I$ 表示局中人的集合,如果有 $n(n>2)$ 个局中人,则 $I={1,\dots,n}$
  2. 策略与策略集:可供局中人选择的一个行为称为一个策略 $s_i​$,每个局中人都有一组策略,称为策略集。记第 $i​$ 个局中人的策略集为 $S_i(i\in I)​$
  3. 赢得函数(支付函数):在一句对策中,每个局中人都选定一个策略形成一个策略组,称为一个局势 $s=(s_1,\dots,s_n)$。全体局势组成的集合 $S=S_1\times S_2\times\dots\times S_n$。对任意局势 $s\in S$,每个局中人都可获得一个赢得,如第 $i$ 个局中人的赢得记为 $H_i(s)$,则称为第 $i$ 个局中人的赢得函数。$H_i(s)$ 可正可负。

对策问题的分类

对策问题分类

二、矩阵对策

二人有限零和对策也叫矩阵对策

2.1 模型

若两个局中人 Ⅰ、Ⅱ 的策略集分别为 $S_1={\alpha_1,\dots,\alpha_m}$ 和 $S_2={\beta_1,\dots,\beta_n}$,对任一局势 $(\alpha_i,\beta_j)\in S$,记局中人 Ⅰ 的赢得为 $a_{ij}$,则局中人 Ⅰ 的赢得矩阵 $A$ 为

易知局中人 Ⅱ 的赢得矩阵为 $-A​$ 。

此模型记为 $G={S_1,S_2;A}$。

对于一个模型 $G={S_1,S_2;A}$,易知局中人 Ⅰ 至少有把握的赢得为 $v_1=\max_i\min_ja_{ij}$,局中人 ⁡Ⅱ 至多有把握的支出为 $v_2=\min_j\max_ia_{ij}$,容易证明 $v_1\le v_2$. (后面附录证明部分的证明 1)

2.2 最优纯策略

定义 1:设 $G={S_1,S_2;A}​$ 为矩阵对策,$S_1={\alpha_1,\dots,\alpha_m}​$,$S_2={\beta_1,\dots,\beta_n}​$,如果等式

成立,记 $V_G=a_{i^\ast j^\ast}$,则称

定理 1($G$ 有解的充要条件):矩阵策略 $G={S_1,S_2;A}$ 在纯策略意义下有解的充要条件是:存在 $(i^\ast,j^\ast)$ 使得对任意 $i(1\le i\le m)$ 和 $j(1\le j\le n)$ 有

并且称 $(i^\ast,j^\ast)​$ 是矩阵 $A​$ 的一个鞍点(或称为对策 $G​$ 的一个鞍点)。

简单地说,就是“有鞍点”等价与“有解”。而鞍点简单地说,就是“行中最小(下界),列中最大(上界)”。

最优纯策略的意义

纯局势 $(\alpha_{i^\ast}, \beta_{j^\ast})​$ 使得双方达到一个平衡状态,也被称为纳什均衡点。在这种情况下,不仅仅是双方各自的最优选择,而且无一参与者可以通过独自改变策略来增加收益,也就是说局势将稳定在这里。

先说最优。由于这个局势是由局中人 Ⅰ 按照 max-min 方法选择的,也是局中人 Ⅱ 按照 min-max 方法选择的,因此这是双方在不知对方如何选择的情况下的最优策略。

再说平衡。最初我不懂这里的平衡是什么意思,后来我举了个简单的例子,帮助自己理解了。假设有个对策的赢得矩阵 $A$ 为

这个赢得矩阵没有鞍点,也就无法平衡。原因是这样:局中人 Ⅰ 按照 max-min 方法应该选择 $\alpha_1$ ,最差也能获得1;它选择后,局中人 Ⅱ 为了最小化 Ⅰ 的赢得,当然应该选 $\beta_1$;这样以后局中人 Ⅰ 发现自己选择 $\alpha_2$ 更好:能获得 3!于是他改为策略 $\alpha_2$;局中人 Ⅱ 一看,你选 $\alpha_2$ 我就选 $\beta_2$,让你只能获得 0;局中人 Ⅰ 说,你选 $\beta_2$ 我就选 $\alpha_2$……双方根本无法达成一个稳定的局势,每个局中人都能在对方选择一个策略后改变自己的策略来获得更多,最后这个局势无法稳定。不管一方选择什么策略,另一方总能克制他,反之亦然。

相反,看下面这个赢得矩阵 $A’​$:

这里存在一个鞍点 $(2,1)$。局中人 Ⅰ 按照 max-min 方法应该选择 $\alpha_2$,它选择后,局中人 Ⅱ 为了最小化 Ⅰ 的赢得,当然应该选 $\beta_1$;此时局中人 Ⅰ 还是保持原来的策略,因为如果他改变策略,将获得更少;同样局中人 Ⅱ 也保持原来的策略。此时局势达到平衡。也就是说无一参与者可以通过独自改变策略来增加收益,局势将稳定在这里。

矩阵对策解的性质

一个矩阵对策中可能出现多个鞍点,这些鞍点之间有以下两条性质:

2.3 矩阵对策的混合策略

如之前讨论的,如果一个矩阵对策无解,那么此时一旦一方知道对方会选什么,则他有能力克制对方。比如猜拳游戏,你只要知道对方选什么,你总能赢。所以最好的策略就是带有某种随机性地来选择策略,这就是混合策略

定义 2:设 $G={S_1,S_2;A}​$ 为矩阵对策,$S_1={\alpha_1,\dots,\alpha_m}​$,$S_2={\beta_1,\dots,\beta_n}​$,记

则称 $S_1^\ast​$ 和 $S_2^\ast​$ 分别为局中人 Ⅰ 和 Ⅱ 的混合策略集。每一个 $\boldsymbol{x}\in S_1^\ast​$ 和 $\boldsymbol{y}\in S_2^\ast​$ 被称为局中人 Ⅰ 和 Ⅱ 的混合策略。$(\boldsymbol{x},\boldsymbol{y})​$ 被称为一个混合局势,并称

为局中人的赢得函数。于是,构成一个新的对策 $G^\ast={S_1^\ast,S_2^\ast;E}$,称为 $G$ 的混合扩充。

从上面公式可以看出,混合策略实际上是局中人 Ⅰ 将以概率 $x_i$ 选中策略 $\alpha_i$,局中人 Ⅱ 将以概率 $y_j$ 选中策略 $\beta_j$。

最优混合策略

同样地可以定义最优混合策略。定义方式同纯策略一致,在此不再赘述。

实际上纯策略只是混合策略的一种特例,相当于以 1 的概率选择某个策略。

混合策略有解的充要条件同样是存在鞍点

定理:对任一矩阵,对策 $G={S_1,S_2;A}$ 一定存在混合意义下的解。

2.4 矩阵对策的解法

主要有两种:

三、双矩阵对策

二人有限非零和对策也叫双矩阵对策。此时两个局中人的赢得矩阵不再是相反数,而是两个矩阵。即模型为 $G={S_1,S_2;A,B}$ .

在双矩阵对策中,双方可以合作,也可以不合作。例如著名的囚徒困境就是非合作的双矩阵对策。

附录:证明

命题 1:局中人 Ⅰ 至少有把握的赢得为 $v_1=\max_i\min_ja_{ij}$,局中人 ⁡Ⅱ 至多有把握的支出为 $v_2=\min_j\max_ia_{ij}$,则 $v_1\le v_2​$.

证明:这其实是一个很常用的知识:“一个二元函数的 max-min 小于等于它的 min-max”,即

由定义知对定义域中任意的 $x,y​$ 有

所以

由于上式对任意 $x,y$ 都成立,那让 $x$ 取 argmax 的左式,$y$ 取 argmax 的右式,不等式仍然成立,即

这就是原始命题。$Q.E.D.$

参考