CMSC 5728 Decision Analysis & Game Theory - Lecture 01

Lecture 01 Introduction

Two-person Zero-sum Games零和博弈

所有博弈方的利益之和为零或一个常数，即一方有所得，其他方必有所失。也可以说：自己的幸福是建立在他人的痛苦之上的，二者的大小完全相等，因而双方都想尽一切办法以实现“损人利己”。零和博弈的例子有赌博、期货和选举等。——维基百科

重点是如果P1赢，就意味着P2输，双方是一种对立关系。比如你和朋友吃一张披萨，你多吃一口，他就少吃一口。

我们拿围棋举例说明。为了简单起见，我们就假定X、Y两人下围棋，该X走下一步棋了，他有3种可选的下法，分别是x1、x2、x3，Y也有三种，分别是y1、y2和y3。

在围棋中，一方的所得必然是另一方所失，因此这是一个零和游戏，比如说X走了x1这步棋后，在盘面上的胜率所得是7点，那么Y的胜率损失也是7点。在这样的情形下，我们只要考虑X的胜率变化即可，因为X赢了多少就是Y输的。

我们知道当X采用了x1、x2、 x3之中的一种策略后，Y也有相应的三种策略y1、y2和y3,因此它们的组合就有9种结果，就构成了一个3x3的矩阵。在每一个组合中， X有一个胜率的变化，这些变化就构成了矩阵的值：(我们假设这9个结果对应了X能获得的9个分数。)

在这个矩阵中，你可以看到，当X采用x1策略时，他最好的情况是碰上Y采用y1，这时X的胜率就增加7点，但是如果Y是一个高手，他采用了y3策略应对，你可以看到X的胜率就小了10点。因此X如果考虑到Y可能的应对策略，他就应该知道，x1其实不能算是一步好棋。

相比之下，采用x2策略就稳健得多，因为无论Y如何应对，他至少可以让自己的胜率增加一点。至于x3，因为有胜率减少一点的可能性，也没有x2好。因此，在制定策略时，如果我们不考虑对方的应对，显然x1是最好的，x2是最差的，但是考虑到对方应对的情况，可能最好和最差的策略就反过来了。

具体到博弈这件事，特别是计算机博弈，最通用的策略是，“在对方给我们造成最糟糕的局面里，选择相对最好的”。也就是说，我们要把x1、x2和x3所有策略算出来后，在可能得到的最糟糕结果中进行比较，具体到这个问题，就是-10、 1和-1这三个结果，然后排序找到最大的，那就是1。在计算机算法中，这种策略被称为最小值中的最大值策略（min-max algorithm）。

接下来我们站在Y的角度来看看他的选择。我们假设他先行棋后，胜率变化的矩阵还是上面那个，当然负值表示他的胜率上升。如果他选择y3，虽然可能让胜率增加10点（对应-10那个值），但是，也冒着损失4点的风险。相比之下，y2的选择就比较好，因为最不济也不过让胜率损失1个点。类似的，可以分析出来y1也不如y2。

回到课件。对P1来说，数值越大得分越高，B的每一列都比C小，则称C ”dominates“ B；对P2来说，数值越大失分越多，B的每一列都比C小，则称B ”dominates“ C。

Saddle Points鞍点

然而这种分析方法并不是每次都有用，因为会出现如下的情况。

此时P2没有一列能够”dominates“另一列，因此需要另一种解决方法，鞍点。

Salle Point鞍点：非局部极值点的驻点。——维基百科

此时，对P1来说，鞍点是所有最小值（-1、2、-16）中的最大值；对P2来说，是所有最大值（12、2、3）中的最小值。

在两方的博弈中，大家其实就是在寻找马鞍点这样一个平衡点， 因为大家都知道，如果自己走出了这个平衡点，试图扩大自己的利益，对方就会有反制手段，让自己的利益受损。

当然并非所有的问题里这样的平衡点都在。比如前面那个对弈的胜率矩阵，如果里面的数字都是些很大的正值，也就是说X的实力可以秒杀Y，采用什么策略可能Y都无法应对，这种情况其实不用担心。但是当参与方的水平势均力敌，不相上下时，很多时候寻找最小值中的最大值才是最好的出路，或者说其实双方必然会被锁死在那个平衡点上。

这里需要补充一点的是，我们其实作了一个隐含的假定，就是双方的策略都是透明公开的，即双方都知道对方所有可能的选择，也就是说一切是阳谋，不是阴谋。双方所不知道的，无非是对方最终采取的策略。

其次，双方都足够理性（rantional），能够判断出该采用什么策略。