[有意思的数学]极小极大问题与博弈论入门
为啥要提到这个问题呢，是因为最近一直在做生成对抗网络（GAN）的工作，GAN的灵感来源于博弈论（也叫对策论，竞赛论）中的零和博弈，而原始GAN的优化目标又是一个极小化极大问题，所以我觉得有必要深入了解一下这个问题。另外，我觉得博弈论这个东西挺有意思的，而且挺实用的（坏笑脸），所以就查了一些资料，在这里做个总结，拿出来和大家分享。
博弈的意思其实比较简单，就是两个人，或者多个人之间的竞争，比赛。通过采取不同措施，达到不同的目的，使得自己的利益最大化。古老的故事“田忌赛马”就是博弈思想的体现，我就在想为啥田忌没有开创“博弈论”。。。囧（因为那时候数学还没有发展到博弈论需要的程度）。现代博弈论诞生的标志是1944年冯.诺依曼和摩根斯特恩出版的《博弈论与经济行为》这本书。20 世纪50 年代, 纳什( Nash)建立了非合作博弈的“纳什均衡”理论, 标志着博弈的新时代开始, 是纳什在经济博弈论领域划时代的贡献, 是继冯·诺依曼之后最伟大的博弈论大师之一。1994 年纳什获得了诺贝尔经济学奖。他提出的著名的纳什均衡概念在非合作博弈理论中起着核心作用。
# 先解几个博弈论中基本概念：
局中人：在一场竞赛或博弈中，每一个有决策权的参与者成为一个局中人。
只有两个局中人的博弈现象称为“两人博弈”,而多于两个局中人的博弈称为“多人博弈”。 。通常用I 表示局中人的集合。如果有n 个局中人, 则I = {1 , 2, ⋯ , n}。
策略集：一局对策中, 可供局中人选择的一个实际可行的完整的行动方案称为一个策略。参加对策的每一局中人i, i 属于I, 都有自己的策略集Si 。一般, 每一位局中人的策略集中至少应包括两个策略。通俗理解就是你能赢得对方的所有可能的解决措施，所以一般来说，你的措施肯定不止一个。
赢得函数( 支付函数（矩阵）)：在一局对策中, 各局中人选定的策略形成的策略组称为一个局势, 即若Si 是第i个局中人的一个策略, 则n 个局中人的策略组
就是一个局势。如果只有两个局中人，那么S就只有两个元素。全体局势的集合S 可用各局中人策略集的笛卡儿积表示, 即
当一个局势出现后, 博弈的结果也就确定了。也就是说, 对任一局势小s属于大S。局中人i可以得到一个赢得值Hi(s).显然, Hi(s)是局势s的函数, 称为第i 个局中人的赢得函数。当每个局中人的策略确定以后，那么整个博弈的局势也就确定了，这时候局中人有了赢得值，所以赢得值是局势的函数，当然也是策略的函数。
完全信息博弈：是指每一参与者都拥有所有其他参与者的特征、策略集及赢得函数等方面的准确信息的博弈。
纯策略和混合策略：在完全信息博弈中，如果在每个给定信息下，只能选择一种特定策略，这个策略为纯策略（pure strategy）。纯策略对应的局势叫做纯局势集合；如果在每个给定信息下只以某种概率选择不同策略，称为混合策略（mixed strategy）。混合策略是纯策略在空间上的概率分布，纯策略是混合策略的特例。
非合作博弈： 指一种参与者不可能达成具有约束力的协议的博弈类型，这是一种具有互不相容味道的情形。
零和博弈： 即所有局中人的赢得值之和为0的博弈。零和博弈属于非合作博弈，指参与博弈的双方，在严格竞争下，一方的收益必然意味着另一方的损失，博弈各方的收益和损失相加的总和永远为“零”。双方不存在合作的可能。零和博弈的结果是一方吃掉另一方，一方的所得正是另一方的所失，整个社会的利益并不会因此而增加一分。
然后我们复习一下数学中的几个概念：
半正定矩阵：一个n×n的埃尔米特矩阵M是正定的当且仅当对于每个非零的复向量z，都有z’Mz > 0，则称M为正定矩阵，其中z’表示z的转置矩阵
判断方法：一个矩阵是半正定的是指该矩阵对应的实二次型f（x1,x2,...,xn）对任意的一组不全为零的实数c1,c2,...,cn都有f(c1,c2,...,cn)>=0。反之，如果f(c1,c2,...,cn)<0，则就是半负定矩阵。
不定矩阵：若设A是实对称矩阵。如果A既不是半正定的，也不是半负定的，就称A为不定矩阵。
鞍点：鞍点（Saddle point）在微分方程中，沿着某一方向是稳定的，另一条方向是不稳定的奇点，叫做鞍点。在泛函中，既不是极大值点也不是极小值点的临界点，叫做鞍点。在矩阵中，一个数在所在行中是最小值，在所在列中是最大值，则被称为鞍点。
判断鞍点的充分条件：对于一个二元实值函数F(x,y)的驻点，计算在该点的 Hessian 矩阵，如果其是不定的，则该驻点为鞍点。其中驻点的意思就是一阶导数为0的点，Hessian矩阵就是函数对每个自变量求偏导数得到的矩阵，不清楚可以去查一下。
下面用二元函数z=f(x,y)来说明鞍点的含义。
（公式不好贴，还是直接截图吧）
鞍点具有特殊的性质，到现在发展起来对应的数学规划叫做鞍点规划，鞍点规划主要就是用来解决“极大值的极小化”或者“极小值的极大化”问题。
极小极大值理论的核心思想是：在某一博弈中，如果一个局中人根据极小极大理论的标准来选择他可以采取的策略，那么就是说对他的每一种策略，他首先考虑他采取该策略后能收到的最低支付，然后他在所有最低支付中选择能得到最大支付值的那个策略。极小极大值理论表明二人零和有限纯策略（或连续纯策略和连续纯凸支付函数）的博弈是确定的（即有解）。对于每个两人零和博弈，每个局中人都存在一个混合策略使得当局中人使用这些策略时，双方有相同的支付期望。而且这个期望值也是每个局中人能指望从博弈的一局中得到的最优支付。因此，这些混合策略时两个局中人所用的最优策略。
极小极大值理论在冯.诺依曼证明极小极大值之前，有多位数学家做出贡献。有兴趣的读者可以去看参考文献3。在冯.诺依曼证明之前，极小极大的解和思想，是在1921年被法国数学家波莱尔发现。1928年冯.诺依曼发表《关于伙伴游戏理论》，其中冠以极小极大问题解的存在性证明用到了概率和拓扑的知识，了解就好，这里不去深究了。第一个初等的（非拓扑）的极小极大值原理的证明，是波莱尔的学生威莱于1938年给出，证明用到了凸性和支撑超平面的概念。此后，又有多位数学家给出证明，证明手段主要分为两类，一类是以不动点理论或者迭代程序为基础，另一类是以凸集理论为基础。若把一局博弈的支付z视为局中人，x和y为各自所做选择的函数值，则平衡点（x，y）就是：
它被称为纯策略博弈的一个解（不论博弈对局多少次，每个对局人的最佳选择都是其鞍点相对应的博弈策略，否则就是混合策略）。鞍点的重要性在于：任何一个局中人都不能由单方面背离它而做出改进！换句话说，任何一个局中人都能先于另一个人局中人宣称他的选择，而且不会因为这样做而造成任何的损失。
假设局中人A的纯策略的集合
冯.诺依曼证明的困难部分是要证明：没有一个局中人能偏离由极小极大策略规定的概率以得到较好的支付期望，换句话说，每一个局中人要得到满意的支付期望，必须在极小极大理论的框架下。
到这里，今天的主要内容就结束了，下面是关于极小极大定理的证明的一些介绍以及博弈论在极小极大定理发现以后的发展。上面废了半天口舌，主要就是想说明一个问题，极小极大问题解的存在性以及解的性质，冯.诺依曼证明了解的存在，以及它的解就是零和博弈的均衡点，局中人必须在极小极大问题的解中选择策略。
冯.诺依曼引理：
极小极大定理通过混合策略概念确保了平衡点的存在性，重建了任何两个零和博弈的可能性。这个定理意味着存在合理的选择：每个局中人都能事先宣布其策略而不给对手丝毫好处。
1994年J.Nash纳什和J.Harsanyi与R.Selten分享了诺贝尔经济学纪念奖。他们在博弈论中的开创性工作就是证明了一条定理，该定理把极大极小定理推广到有两个或者多个直接竞争的局中人的非零和博弈，即非合作博弈的情形。
回顾一下策略的平衡对的概念，一个博弈策略：使得局中人单方面背离他或她的平衡对中的平衡策略，比不背离该策略所得到的期望支付要差。极小极大定理的一个重要推理就是策略的这两个相当不同的概念在零和博弈的情形中是一致的：
平衡对就是极大极小对，反之亦然。
纳什定理讨论了这种局势。
纳什定理：在每个局中人有有限个纯策略的任一n人非合作博弈中，至少有一个混合策略平衡组。
纳什分别应用下述的Brouwer不动点定理和角谷静夫不动点定理证明了n人有限非合作博弈平衡点的存在性。
关于不动点定理的证明，需要的数学知识挺多的，我只是想说，这里了解一下即可。如果有时间，后面我在翻翻泛函分析的课本。。。
因此，无论是冯.诺依曼还是纳什，他们对博弈论研究的奠基之作都与凸分析，集值映射，不动点定理等理论有着紧密的联系。
冯.诺依曼和纳什工作的两个假设是：
1）每个局中人的所有信息都是公开的，完全的，对称的；
2）每个局中人都是完全理性的，都能够在各自策略集中选择对自己最为有利的策略。
Harsanyi和Selten的工作分别针对这两个假设提出新的思想，大大扩展了博弈论的应用。Harsanyi在非对称信息条件下，提出了“类型”的概念，应用贝叶斯方法对博弈论模型进行分析，为信息经济学奠定了基础；而Selten讲完全理性看做有限理性的极限，提出纳什平衡点精炼的概念。正因为如此，他们才与纳什一起，共同获得1994年的诺贝尔经济奖，也是这次获奖，才确认了博弈论对经济理论的核心重要性。
参考文献
[1] 胡运权. 运筹学. 第三版. 清华大学出版社.
[2] 运筹学基础. http://www.doc88.com/p-206185909674.html.
[3] 尚于洪. 极小极大值理论的历史发展. 西北大学学报.2003.
[4] 部分百度百科和智库百科内容在此一并说明。
============end============