第1章有限非合作博弈
　　博弈论也称对策论，它研究参与者在对抗或合作中的*优策略。在人类社会的发展过程中，博弈论的思想源远流长。自古以来，人们自觉不自觉地在社会生活和生产斗争中使用博弈的思想做出自己的决策。在中国历史上典型的博弈例子包括战国时代的田忌赛马、三国时代的华容道等。古代犹太人的法典中规定在有争议的情况下财产的分割，是合作博弈很好的例子。19世纪描述双寡头垄断竞争的古诺模型，已经开始将严格的数学方法引入博弈的决策分析。真正用近代科学的方法研究它们，从而形成当代重要学科分支，则都大体始于第二次世界大战之后，以冯 诺伊曼等的《博弈论与经济行为》[121]为标志。
　　近代的博弈理论大体包含两个部分：非合作博弈与合作博弈。在非合作博弈中，玩家之间主要是竞争关系。这里寻找的解是各玩家利益的一种均衡。*著名的或者说应用*广的就是纳什均衡，它是美国数学家J.Nash（纳什）在1950年提出来的[101]，纳什因此在1994年获得诺贝尔经济学奖。其他的还有Pareto均衡等。粗略地说，非合作博弈的解就是寻找合适的均衡。
　　合作博弈则不同，它探讨因合作得到的利益应如何分配才是合理的。因此，合理的分配方案才是合作博弈的*优解。例如，由L.S.Shapley提出的一种分配方案，后来被称为Shapley值。Shapley是2012年诺贝尔经济学奖获得者。
　　本书以有限博弈为主。有限博弈指的是在一个博弈中，一共只有有限个玩家，而每个玩家可供选择的策略也是有限的。我们之所以选择有限博弈，除了有限博弈自身的重要性外，还因为矩阵半张量积是描述和分析有限博弈的方便而有效的工具。例如，两个人玩石头-剪刀-布，这时，每个人都有三个策略可选，不妨设石头对应、剪刀对应、布对应，那么，策略演化过程就可以用三值逻辑网络来刻画它了。于是，本丛书第二卷中发展起来的逻辑网络的分析与控制的方法就可以方便地用到这类博弈过程了。
　　关于博弈论的书非常多。我们对初学者推荐以下两本入门书：，它们提供的基本概念与结论足够本书的需要了。是对博弈论半张量积方法的一个较全面的综述，它有助于了解该方向的研究进展。
　　1.1有限博弈的数学模式
　　定义1.1.1一个有限非合作博弈G由一个三元组（N，S，C）决定，这里
　　（i）为玩家集合，即该游戏有n个玩家；
　　（ii）为局势（profile）集，这里
　　是玩家i的策略集，即第i个玩家有ki个可选策略。
　　（iii）
　　因为本章只讨论非合作博弈，所以把有限非合作博弈简称为有限博弈。
　　通常二人博弈可以用一个支付双矩阵表示。设G为一个二人博弈，玩家P1有m个策略，即，玩家P2有n个策略，即，那么，支付双矩阵见表1.1.1。
　　在表1.1.1中，不同的行代表玩家P1的不同策略，不同的列代表玩家P2的不同策略，在双矩阵中
　　例1.1.1考虑二人玩石头-剪刀-布，记石头为1，剪刀为2，布为3，且赢者得一分，输者失一分。那么，支付双矩阵可表示为表1.1.2。
　　一个局势可表示为，这里。设，则s可以用，表示，这里。因此，S是一个多指标集。下面我们构造一个矩阵，称为支付矩阵。支付矩阵可通过构造支付表而得到。
　　表1.1.2中第一行以字典顺序列出所有局势，以下每行对应一位玩家在对应局势下的支付。例如，当n=2时，表1.1.2可等价地表示表1.1.3的支付函数。
　　支付矩阵的一个优势是，它可以应用到n>2的情况，而支付双矩阵只能用于n=2的情况。
　　1.2伪逻辑函数
　　定义1.2.1设。称函数为一个伪逻辑函数。如果，则称伪逻辑函数为伪布尔函数。
　　利用向量表达式，我们有，并且，伪逻辑函数有一个矩阵表示形式，这在下面的命题中给出。
　　命题1.2.1设为一伪逻辑函数，则存在唯一的行向量，这里，称为f的结构向量，使在向量形式下有
　　（1.2.1）
　　证明　这跟逻辑函数的结构矩阵的道理是一样的，只是将每一列所对应的逻辑函数值改成对应的伪逻辑函数值。
　　给定一个有限博弈，这里。那么，每一个就是局势的伪逻辑函数。根据命题，对每个都存在一个它的结构向量，使得
　　这里
　　（1.2.2）
　　实际上，如果G的支付矩阵的第i行表示玩家i的收益信息，那么该行就是ci的结构向量。
　　下面举几个简单的例子。
　　例1.2.1以下是几个常见的简单博弈的例子。
　　（i）性别之战：一对情侣准备一次约会，男士（玩家1）喜欢去看足球赛，女士（玩家2）想去听音乐会。当然他们都希望能在一起。于是，这场博弈的支付双矩阵可表示为表1.2.1
　　如果表示成伪逻辑函数，则有
　　（ii）智猪博弈：猪圈里有个控制器，每按一下可提供10千克食物，控制器离食槽较远，去按控制器者必然后吃。设大猪先吃，则大、小猪各吃9千克与1千克，小猪先吃，各吃6千克与4千克，同时开始吃，则各吃7千克与3千克，又按一下要消耗2千克食物。那么，支付双矩阵如表1.2.2所示。
　　表示成伪逻辑函数，则有
　　（1.2.4）
　　（iii）猎鹿博弈：两猎人正围堵一只鹿时，突然出现一群兔子。如果二人合作，则可抓到鹿，卖鹿后每人可得10元。若两人都去抓兔子，则每人可得4元。若一人去抓兔子，一个去猎鹿，则抓兔子者可得4元，猎鹿者一无所获，得0元。那么，支付双矩阵如表1。2。3所示。
　　表示成伪逻辑函数，则有
　　（1.2.5）
　　（iv）田忌赛马：田忌与齐王赛马，各有上、中、下三种等级的马，分别记作t1，t2，t3和q1，q2，q3。已知q1>t1>q2>t2>q3>t3（这里“>”表示速度快），共赛三场，二人可分别选择出场顺序。每场千金，于是有支付双矩阵如表1。2。4（其中单位为千金）。
　　表示成伪逻辑函数，则有
　　（1.2.6）
　　考察有限博弈且，n。则所有这种博弈的集合记作。当时，这类集合简记为。
　　考察一个博弈。设其支付函数的结构向量为，将所有结构向量依顺序排成一行，定义为
　　（1.2.7）
　　那么，VG称为博弈G的结构向量。
　　因为每个博弈都是由其支付函数唯一确定的，所以每个博弈都由其博弈的支付函数的结构向量唯一确定。因此，我们可以给博弈集合一个向量空间结构，它同构于Rκ。
　　例1.2.2回忆例1.2.1：
　　（i）性别之战（G1）、智猪博弈（G2）和猎鹿博弈（G3）均属于G[2；2]，其结构向量分别为
　　（ii）田忌赛马（G4）属于，其结构向量为
　　1.3纳什均衡
　　纳什均衡是非合作博弈理论中*重要的一个概念，有的教科书直接将纳什均衡称为非合作博弈的解，如[9]。
　　先介绍纳什均衡的概念。
　　定义1.3.1考察一个有限博弈。一个局势称为G的一个纯纳什均衡点，如果
　　（1.3.1）
　　注意，这里。
　　与优化问题不同，非合作博弈中的每一个玩家都很难达到自己支付的*优值（为简单计，约定为*大值），因此，非合作博弈的目标并不是寻找每一个玩家的*优解，而是寻找大家都能接受的解。纳什均衡就是这样一种解。由定义不难看出，如果其他人的策略不变，则没有人能够通过单独改变自己的策略而获利。因此，它成为一种局势的平衡点，或者说，在某种“妥协”下的共同次优解。
　　我们给一个例子说明什么是纳什均衡。
　　例1.3.1（囚徒困境（Prisoner’s　Dilemma））两个共犯的囚徒，分别受审。各有两种策略：招供、拒供。其结果表示在支付双矩阵（表1.3.1）中。

目录　
前言　
第1章　有限非合作博弈　1　
1.1　有限博弈的数学模式　1　
1.2　伪逻辑函数　3　
1.3　纳什均衡　6　
1.4　混合策略与纳什定理　8　
1.5　纳什定理的证明　9　
第2章　矩阵博弈　14　
2.1　Rn中的凸集　14　
2.2　矩阵博弈及其纳什均衡点　17　
2.3　混合纳什均衡的存在　21　
2.4　矩阵博弈的等价性　22　
2.5　计算纳什均衡　23　
第3章　网络演化博弈　29　
3.1　演化博弈与受控演化博弈　29　
3.2　网络演化博弈的数学模型　34　
3.3　结点的基本演化方程　40　
3.4　依赖于状态的演化博弈　45　
3.4.1　确定型时变演化博弈　46　
3.4.2　混合型时变演化博弈　50　
3.5　策略演化与局势演化　53　
3.6　网络演化博弈的控制　58　
3.7　基于网络图的演化博弈　60　
3.7.1　网络的局势演化方程　61　
3.7.2　猜硬币的网络演化博弈　65　
3.8　网络演化博弈的拓扑结构　68　
3.8.1　不动点与极限环　69　
3.8.2　纯纳什均衡点　70
第4章　演化稳定策略　76　
4.1　生物系统中演化策略的稳定性　76　
4.2　有限博弈的演化稳定策略　78　
4.3　网络拓扑与策略演化　86　
4.3.1　非对称网络演化博弈　86　
4.3.2　齐次网络演化博弈　92　
4.4　策略的收敛性　96　
4.4.1　有限演化博弈策略的拓扑结构　96　
4.4.2　齐次网络的策略收敛性　99　
4.5　博弈的演化等价　106　
第5章　受限逻辑系统与智能系统的控制　109　
5.1　受限逻辑动态系统　110　
5.2　系统的能控性分析　111　
5.2.1　受限逻辑动态系统的能控性　113　
5.2.2　受限周期逻辑动态系统的能控性　114　
5.3　智能规划问题的控制　115　
5.3.1　农夫-狼-羊-白菜的渡河问题　115　
5.3.2　传教士与食人族的渡河问题　117　
第6章　势博弈　122　
6.1　势博弈及其基本性质　122　
6.2　势方程　124　
6.3　势方程的结构与解　128　
6.4　网络演化势博弈　135　
6.5　加权势博弈　141　
6.5.1　加权势博弈方程的双线性表示　141　
6.5.2　权重的计算　144　
6.6　余集加权势博弈　148　
6.6.1　余集加权势博弈的代数结构　148　
6.6.2　余集加权两个玩家布尔势博弈　151　
6.7　从布尔博弈到势博弈　152　
6.7.1　布尔博弈与对称博弈　153　
6.7.2　对称布尔博弈　154　
6.7.3　检验布尔博弈的对称性　156　
6.7.4　从对称博弈到势博弈　161　
6.7.5　加权布尔博弈　165
6.7.6　重置名布尔博弈　168　
6.7.7　翻转对称布尔博弈　170　
第7章　不完全信息博弈　173　
7.1　静态贝叶斯博弈　173　
7.2　贝叶斯-纳什均衡　178　
7.3　贝叶斯博弈的转换　180　
7.4　贝叶斯势博弈　183　
7.5　动态贝叶斯博弈　190　
第8章　有限博弈的向量空间　199　
8.1　势博弈的子空间结构　199　
8.2　非策略子空间　202　
8.3　纯势博弈子空间　207　
8.4　纯调和子空间　208　
8.5　有限博弈的结构分解　214　
8.5.1　子空间投影　214　
8.5.2　正交分解　215　
8.6　演化与博弈空间分解　220　
8.6.1　空间分解与演化等价　220　
8.6.2　网络演化博弈的子空间分解　222　
8.7　近似势博弈　225　
第9章　对称与反对称博弈　229　
9.1　反对称博弈和非对称博弈　229　
9.1.1　线性表示　230　
9.1.2　反对称博弈的存在性　236　
9.2　基于对称性的有限博弈空间分解　238　
9.2.1　一个低维博弈空间的例　238　
9.2.2　两人博弈空间　240　
9.2.3　子空间基底　242　
9.2.4　子空间正交性　245　
9.2.5　有限博弈分解公式　247　
第10章　基于学习的博弈演化　249　
10.1　博弈学习的一般框架　249　
10.2　常见的博弈学习规则　251　
10.2.1　短视*优响应学习　252　
10.2.2　逻辑响应学习　252
10.2.3　虚拟学习　254　
10.3　状态演化博弈　255　
10.3.1　状态演化博弈的数学模型　255　
10.3.2　状态势博弈及其学习规则　258　
10.4　基于状态势博弈设计的多个体系统优化　259　
10.4.1　局部信息依赖的收益函数设计　260　
10.4.2　状态演化过程设计　261　
10.5　一般状态演化博弈的学习规则　265　
10.5.1　基于两步记忆的较优响应学习规则　266　
10.5.2　收敛性分析　268　
10.5.3　应用举例　275　
第11章　基于博弈的优化与控制　281　
11.1　博弈系统的优化控制问题描述　281　
11.1.1　人机博弈　281　
11.1.2　常见的性能指标函数　282　
11.2　纯策略模型的拓扑结构　282　
11.3　平均支付的*优策略　287　
11.4　混合演化策略模型　293　
11.5　有限次混合策略*优控制　294　
11.6　无限次混合策略*优控制　300　
第12章　零行列式策略　304　
12.1　矩阵博弈中的零行列式策略　304　
12.2　从个体策略到局势转移矩阵　306　
12.3　有限博弈中的零行列式策略　309　
12.4　在网络演化博弈中的应用　313　
12.4.1　虚拟对手玩家　314　
12.4.2　网络演化博弈的零行列式策略　315　
第13章　连续策略势博弈的量化方法　318　
13.1　连续博弈　318　
13.2　有限势子博弈　320　
13.3　n元线性插值算法　320　
13.4　合并插值算法　323　
13.5　*势博弈　327　
第14章　合作博弈的矩阵方法　331　
14.1　特征函数　331
14.2　常和博弈的特征函数　336　
14.3　两种特殊的合作博弈　339　
14.3.1　无异议博弈　339　
14.3.2　规范博弈　343　
14.4　分配　345　
14.5　核心　349　
14.6　核心的存在性　353　
14.6.1　简单博弈　353　
14.6.2　凸合作博弈　355　
14.6.3　对称合作博弈　356　
14.7　稳定集　357　
14.8　Shapley值　362　
14.9　Shapley值与核心的关系　372　
参考文献　374　
索引　382