完美信息博弈

Perfect information完美信息博弈：

对于一个有限个玩家n的完美信息博弈包含：

一棵树上所有的信息集合都只包含一个节点的博弈。

将非终端节点都列为一个被标记为0、1、2、…,n的集合。在集合中的一个节点i > 0的意思是i玩家的一个move()，也就是玩家i的移动（可以理解为策略的选择）。

对于集合0中的每个节点，它们所跟随的后续节点都是有个概率分布的，并且这个概率分布必须合理并且解释清楚。（每个节点的后续策略都是合理的）

对于终结点来说，在收益矩阵R中的一个向量，它都对应着该玩家i所采取策略的收益值。

如果这个是完美信息博弈的话，就是没有额外的信息出现。简单来说，当要给玩家选择自己的节点（策略）的任意一个节点，玩家都清楚自己做了一个什么样的决定。因此，玩家完全知道前面的节点所做的所有选择。没有秘密或同时行动的可能性。对于perfect information的博弈来说，就是信息集合都只包含一个节点的博弈。完全信息（complete information）的假设是所有玩家都知道关于游戏的信息（如规则等）。

在经济学中，完美的信息是完全竞争的特征。在市场上有了完善的信息，所有的消费者和生产者都会被认为，当建立自由市场体系和金融政策时，他们对产品的价格、效用、质量和生产方法都完全的了解。树上所有的信息集合都只包含一个节点的博弈。而其实，在日常生活中，不完全信息博弈才是最普遍的。

【出处：论文Games of Perfect Information, Predatory Pricing and the Chain-Store Paradox，URL：https://pdfs.semanticscholar.org/a755/2bd3302f6dee7c0b74dea6fc486f794db0b8.pdf】

Complete information完全信息博弈：

完美（perfect）信息讲的是当你玩的时候，你是否知道你对手他用了什么策略；完全（complete）信息讲的是游戏双方是否都知道整个游戏的规则，参数等。

完全（complete）信息是用来描述一种经济状况或游戏的术语，在这种情况下，所有参与者都可以了解其他市场参与者或参与者的信息。因此，玩家的效用函数、收益、策略和“类型”都是常识。

信息集合

infomation set (信息集合)：<策略与博弈>中以一个椭圆型来表示信息集合，这和数学上所用的表示法是一致的，且更易于理解，但为了作图的方便，后续会使用虚线。如上图的椭圆就是信息集合，

参与人2不能分辨处于信息集合中的两个节点的之前的选择（U还是M）。

信息集合定义：

参与人i的信息集合是一系列参与人i无法识别的参与人i的节点。对信息集合的规定：

集合中的每个节点都属于一个玩家。

当游戏到达信息集合时，移动的玩家不能区分信息集合中的节点，也就是说，如果信息集合包含多个节点，那么该集合所属的玩家不知道该集合中的哪个节点已经到达。

上图中，参与人2（红色虚线部分）可以通过观察选择的数量来判断他所处的节点（上部分有三个策略，下面有两个策略），参与人2就可以分辨出参与人1所选择的策略。上面的案列代表这不是一个信息集合。

如上图，黑色虚线代表一个信息集合，参与人2无法判别参与人1之前的选择，所以上图的虚线部分就是一个信息集合。

完美信息和完全信息：

其实综上所述，完美信息和完全信息的博弈是有区别的。下面举例希望能帮助理解：

Imperfect but complete information（非完美但是完全信息博弈），纸牌游戏就是一个典型的例子，首先玩家们不知道对手手上的牌有哪些，代表这个游戏是非完美的。而每个玩家都知道游戏规则，什么时候胜等，因此纸牌游戏又是一个完全信息博弈。

Incomplete but perfect information（非完全但是完美信息博弈），假设你在玩一个围棋的游戏，而你的对手会在一个特定的情况下会获得收益。此时每个玩家身上只有黑白棋子，并且棋谱上会显示所有棋子可能放落得位置和之前所有下得棋子你都是知晓的（所以这就是完美信息的博弈，对方的所有策略你都知晓）。但是你并不知道这个特定的规则，所以这个游戏是非完全的。

Perfect-information games例子包括tic-tac-toe, checkers, infinite chess, and Go

【出处：wiki，URL：https://en.wikipedia.org/wiki/Complete_information】

发展历史

描述

在1713，最早提到两个人之间游戏的是发生在Charles Waldegrave信中，是他和一位英国外交官James Waldegrave的叔叔的信。在这封信中，Waldegrave为一个双人版的纸牌游戏提供了一个minimax混合战略解决方案，现在这个问题被称为Waldegrave问题。在1838年的“研究财富理论的数学原理”Recherches sur les principes mathématiques de la théorie des richesses一书中对博弈理论进行了分析，Antoine Augustin Cournot提出了双头垄断理论，并提出了一个解决方案，即纳什均衡的最原始版本。

1838年，Antoine Augustin Cournot在他的寡头垄断理论中首次使用了纳什均衡概念。在Cournot的理论中，企业选择产出多少来实现利润最大化。然而，一个公司的最佳产出取决于其他公司的产出。当每一家公司的产出将其利润最大化，而其他公司的产出是纯策略纳什均衡时，就会出现一种库诺均衡。Cournot也引入了最佳反应动力学的概念。

纳什均衡是以美国数学家John Forbes Nash, Jr.的名字命名的。博弈论直到1928年约翰·冯·诺伊曼(John von Neumann)发表论文才真正成为一个独特的领域。

约翰·冯·诺伊曼和奥斯卡·摩根斯坦在1944年出版的《游戏与经济行为理论》中介绍了混合策略纳什均衡的概念。纳什均衡的现代博弈论概念是用混合策略来定义的，即玩家在可能的行为中选择一个概率分布。然而，他们的分析仅限于零和博弈的特例。他们证明了一种混合策略的纳什均衡将存在于任何一组有限的行为的零和博弈中。

纳什在1951年的文章《非合作游戏》中所做的贡献是，用有限的行动集定义了一种混合策略的纳什均衡，并证明在这种博弈中至少必须存在一种(混合策略)纳什均衡。纳什证明存在能力的关键在于他对平衡的定义。根据纳什的说法，“一个平衡点是一个n元组，这样每个参与者的混合策略都能最大化他的收益，如果其他人的策略是固定的。因此，每个玩家的策略都是针对其他玩家的最佳策略。

关于完美信息博弈的最早结果出现在1950年代，但确切出自何人之手却无从得知，这就是所谓的“佚名定理”（the Folk Theorem）。该定理认为，重复博弈的策略均衡结局与一次性博弈中的可行的个体理性结局恰好相一致，这个结局可被视为把多阶段非合作行为与一次性博弈的合作行为联系在一起。或者可以说，只要行为人有足够的耐心，任何满足个体理性的可行支付都可以通过一个特定的子博弈精炼均衡达到。然而，虽然所有可行的个体理性结局确实代表了合作博弈的解观点，但是它不能够提供相关信息，并且是相当模糊的。奥曼认为该理论本身没有多少新东西，他指出，完全信息的重复博弈论与人们之间相互作用的基本形式的演化是相关的。

完美信息是对于一个子游戏的一个条件，随后“子博弈精炼纳什均衡”的创立者是1994年诺贝尔经济学奖获奖者、莱茵哈德·泽尔腾(Reinhard Selten)。泽尔腾则在60年代中期将纳什均衡概念引入动态分析。

在1965年发表《需求减少条件下寡头垄断模型的对策论描述》一文，提出了“子博弈精炼纳什均衡”的概念，又称“子对策完美纳什均衡”。这一研究对纳什均衡进行了第一次改进，选择了更具说服力的均衡点。海萨尼在60年代末把不完全信息引入博弈分析。

尽管博弈论出自于经济领域，但是在别的行业也是得到了广泛的应用，博弈论在逻辑学和计算机科学中发挥着越来越重要的作用。一些逻辑理论在游戏语义学中有其基础。此外，计算机科学家还利用游戏来模拟交互计算。同时，博弈论也为multi-agent systems多主体系统的研究提供了理论依据。另外，博弈论也在在线算法中发挥了作用；特别是k-server问题，过去被称为移动成本和请求-应答游戏的游戏。Yao's principle种游戏理论的技术，用来证明随机算法的计算复杂性，特别是在线算法的下界。

互联网的出现，也快速引起了研究者将博弈论应用于计算机领域中,如：market市场, computational auctions可计算的拍卖, peer-to-peer systems点对点系统, and security and information markets安全和信息市场。Algorithmic game theory和算法机制设计algorithmic mechanism design结合计算算法设计与分析复杂系统与经济理论。

主要事件

发展分析

瓶颈

其实博弈论中的纳什均衡计算机领域中已经有一段历史了，然而求纳什均衡最直接的办法就是backward induction逆向归纳。这个在有限个玩家，有限个策略的情况下很快。但是可以发现这个计算量随着玩家和策略快速增长的，它随着玩家的数目的增长，计算量也指数型增长。

除此之外，这是个跨领域的知识。它需要有计算机领域以及经济领域的背景知识才能将两者有效的结合，这对研究者来说，是比较困难的。

在生活中，在特定的情况我们是知道哪些是完美博弈，哪些是非完美博弈，然而如何在计算机领域直接进行证明将游戏直接分类也限制着博弈论在实际生活中的应用。

未来发展方向

博弈论体现在生活中的方方面面，小到游戏，大到重要决策，每一个都是一个博弈的过程。如何将博弈论中的知识很好的融入计算机领域中，并且能将这些知识普遍运用到计算机领域中，还需要计算机领域和经济领域之间的研究人员的更有效的结合。

Contributor: Ruiying Cai