博弈论讲义

博弈论–均衡与优化

胡晓东

中国科学院数学与系统科学研究院

应用数学研究所Institute of Applied Mathematics

1

2. 博弈论-引子

“To be literate in the modern age, you need to have a general you need to have a general

understanding of game theory.”

--Nobel Laureate Paul Samuelson (1991)

经济学家、1991年诺贝尔经济学奖得主保罗?萨默尔森说：“如果你想要在现代社会做一个有文化的人，那么你就要对博弈论有一个大致的了解。”

xdhu 22014-04-11

2. 博弈论-二战实例

Kenney 有两种选择-轰炸日军的舰船

1.侦察机搜索北线

2.侦察机搜索南线

1943年初新几内亚岛

日本

盟国日军有两种选择-护卫舰增援岛上部队

1.沿北线航行

22.

沿南线航行xdhu 2014-04-113

2. 博弈论-二战实例（续一）

北线

南线北线

北线南线南线当然，双方实际上并不按照图上建议的顺序来做出决定。2312

相反，双方都是在不知道对方将会怎样做决定的情况下分别独立采取行动的。

不过双方所关注/期望的截然相反：对Kenney 是好事的，对日军就是坏事；反之亦然。因此当我们用轰炸天数来衡量盟国的支付，而把这个数的负值作为日军的回报，就有一方xdhu 4赢当且仅当一方输。这就是零和局势-双方的支付和是零。2014-04-11

2. 博弈论-二战实例（续二）俾斯麦海战 支付矩阵 搜索北线 盟国Kenney 搜索南线 日军 航行北线 航行南线2 12 32 1如果Kenney y搜索北线：无论日军走哪，保证有2天轰炸。 如果Kenney搜索南线：若日军走北线，才有1天轰炸； 若日军走南线，可有3天轰炸。 所以，为避免一旦查明日军的决定而感遗憾，Kenney应该选 择能轰炸最少天数中的最大值。这意味着他应该选择北线！2014-04-11 xdhu 5

2. 博弈论-二战实例（续三）俾斯麦海战 支付矩阵 搜索北线 盟国Kenney 搜索南线 日军 航行北线 航行南线2 1 22 3 3如果日军走北线：最多有2天被炸； 如果日军走南线：最多有3天被炸。 所以，为避免一旦查明盟国的决定而觉得遗憾， 日军应该选择被炸最多天数中的最小值。这意味着日军应 该也选择北线！2014-04-11 xdhu 6

2. 博弈论-二战实例（续四）合理的一个决策是：寻找能在最坏处境下给他/她最好可能 支付的行动方向。显然这导致每个局中人都采取不愿冒风险 的决策：为了避免导致不必要的输而舍弃可能的赢的决策。 俾斯麦海战 支付矩阵 搜索北线 盟国Kenney 搜索南线 日军 航行北线 2 1 航行南线 2 3这样的决策组合导致了一个博弈平衡点(或称为鞍点)： 行极小中的极大值(极小极大)等于列极大中的极小值(极大极 小)。有趣的是：海战中双方确实是采取了这些策略！2014-04-11 xdhu 7

2. 博弈论-零和博弈

若把一局博弈的支付z 视为局中人，x (盟军)和y (日军)，各自所做选择的函数值，则平衡点(x,y) 就是：

)

min max z(x,y)= max min z(x,y)。

x y y

x

它被称为纯策略博弈的一个解（不论博弈对局多少次，每个对局人的最佳选择都是其鞍点相对应的博弈策略，否则就是混合策略）。

鞍点的重要性在于：任何一个局中人都不能由单方面背离它而做出改进！换句话说：任何一个局中人都能先于另一个局中人宣称他/她的选择，而且不会因为这样做而造成任何的损失。

2014-04-11

xdhu8

2. 博弈论-零和博弈（续一）假想海战 支付矩阵 盟国(x) Kenney 北线 南线 日军(y) 北线 南线4 2 2*1 3 14 3*然而，很容易给出一个不存在鞍点的支付矩阵。在这种情 况下，对于一个局中人来说，没有容易理解的方法可以用来 避免对手(有意/碰巧)事先获悉他/她将要做什么而获利这种情 况发生。此时，有关局中人应该如何选择、决策呢？ 在不存在鞍点的情况下，我们仿佛不再能有什么期望， 因为，我们不知道什么是合理的决策了。 9

2. 博弈论-零和博弈（续二）

一个通常的做法就是碰运气(掷硬币)。其实这是一个合理的方案：通过随机选择来使得你对手不知道你的决策(否则对手会利用这个信息而获利)！当然我们有时会用不对称的硬币来表示某种选择对自己更有吸引力。石头－剪子－布

Min 博弈

布剪子石头布011Max －剪子

10－1石头－110

这是一个零和博弈问题：Max 赢得的就是Min 输掉的，xdhu 10反之亦然。它没有鞍点。注意：任何一方偷看了(慢出招)，

都能得到好处(胜利)。

2. 博弈论-零和博弈（续三）

如果两人都诚实地对局：都以相等的概率1/3 从三个选项中选择一个，结果是有9 个可能的结果(每一个出现的概

9

率是1/9 )。显然，两人的支付期望分别都是0。

现在我们假设Min 继续以等概率来三选一，但是Max 却改变了他的选择，布=1/3，剪子=1/2，石头=1/6。可以算出（练习），两人的支付期望还都是0！事实上，不论Max 怎么改变，两人的期望还是不变。

这意味着：就Min 的等可能混合策略而言，Max 不可能改善其支付期望。因此，具有等可能性的选择的混合策略是这个博弈的一个平衡点：使用随机化其选择，两人都可以宣布各自的选择而不必顾忌对手能利用此信息来获利。

2014-04-11

xdhu11

2. 博弈论-极小极大定理

现在我们要考虑的问题是：

1.两人零和博弈，

对于任何

如何判断最优混合策略是存在的？

2.如果最优混合策略存在，

那么又如何确定呢？

策梅洛（E. F.Zermelo，1871－1953）

猜测对于每个局中人而言，应存在能给

双方以同样支付期望的混合策略，而且

这与每个局中人能利用的数目无关。

2014-04-11

xdhu12

2. 博弈论-极小极大定理（续一）

极小极大定理(1928；约翰·冯·诺依曼－1903-57) 对于每个两人零和博弈，每个局中人都存在一个混合策略使得当局中人使用这些策略时，双方有相同的支付期望。而且，这个期望值也是每个局中人能指望从博弈的一局中得到的最优支付。因此，这些混合策略是两个局中人所用的最优策略。

1944年冯·诺依曼与奥斯卡·摩根斯特恩13

2. 博弈论-极小极大定理（续二）

冯·诺依曼证明的困难部分是证明：没有一个局中人能偏离由极小极大策略规定的概率以得到较好的支付期望。

极小极大定理通过混合策略概念确保了平衡点的存在性，重建了任何两人零和博弈的可解性（但是，这是在混合策略空间，而不是纯策略空间）。这个定理意味着存在合理的选择：每个局中人都能事先宣布其策略而不给对手丝毫好处。

冯·诺依曼曾经说：“就我所知道的，没有那个定理……就不可能有博弈论……我认为直到‘极小极大定理’被证明之前没有什么东西是值得发表的。”

2014-04-11

xdhu14

2. 博弈论-极小极大定理（续三）

1994年J. Nash (美国数学家，1928－)和J.Harsanyi 与

R. Selten分享了诺贝尔经济学纪念奖(The Sveriges Riksbank R.Selten(The Sveriges Riksbank

Prize in Economic Sciences in Memory of Alfred Nobel)。他们在

博弈论中的开创性工作就是证明了一条定理，该定理把极大极小定理推广到有两个或多个直接竞争的局中人的非零和博弈，即非合作博弈的情形。

15 John C. Harsanyi John F. Nash Jr.Reinhard Selten

2. 博弈论-极小极大定理（续四）

回顾一下策略的平衡对的概念。一个博弈策略：使得局中人单方面背离他或她的平衡对中的平衡策略，比不背离该策略所得到的期望支付要差。极小极大定理的一个重要推理就是策略的这两个相当不同的概念在零和博弈的情形中是一致的：

平衡对就是极大极小对，反之亦然。

纳什定理讨论了这种局势。

纳什定理（非正式的陈述）：在每个局中人有有限个纯策略的任一n人非合作博弈（零和或非零和）中，至少有一个混合策略平衡组（Nash Equilibrium）。

2014-04-11

xdhu16

2. 博弈论-极小极大定理（续五）

冯·诺伊曼和纳什工作的两个假设是：

（1）每个局中人的所有信息都是公开的，完全的，对称的；（2）每个局中人都是完全理性的，都能够在各自策略集中选择对自己最为有利的策略。

和Selten 的工作分别针对这两个假设提出了新的Harsanyi Selten

思想，大大扩展了博弈论的应用。Harsanyi在非对称信息条

件下，提出了“类型”的概念，用贝叶斯方法对博弈论模型进行分析，为信息经济学奠定了基础；而Selten将完全理性看作

有限理性的极限，提出了纳什平衡点精练的概念。正因为如此，他们才与纳什一起，共同获得了1994年的诺贝尔经济奖，也正

.

是这次获奖，才确认了博弈论对经济理论的核心重要性。

2014-04-11

xdhu17

2. 博弈论-非零和博弈

我们考虑非零和博弈：允许博弈中一个局中人赢得的不必等于另一个局中人输掉的支付结构。这种情况更接近实际生活，也更难处理。这种支付矩阵简单的改变将揭示了有时候通过合作而不是竞争的而获得更好的受益的可能性。

2014-04-11

18

2. 博弈论-非零和博弈（续一）

领先者博弈：两个司机驾车并行试图通过交叉路口。当绿灯亮起时，每个司机必须做出决策

把过路权让给另外一个司机(C)

驾车开过路口(D)

A?…如果双方都选择(C)，

B?…他们两个就都被耽误了。

如果双方都选择A

B (D)，

他们就可能相撞。

A

A 如果一个选择(C)，而另外一个选择(D)，

那么领先者将能够继续旅行，而落后者仍能

19

B B挤进领先者留下的空间，在绿灯变成红灯前

进入交通流。

2014-04-11

本文来源：https://www.bwwdw.com/article/s6gi.html