非完全信息博弈

非正式地，不完全信息的博弈是一种玩家对正在玩的游戏没有共同知识的博弈。在博弈中，玩家可能没有常识的是:

•支付 Payoffs--(玩家的收益)

•其他玩家是谁

•哪些策略或行动是可行的

•结果如何取决于行动。

•对手知道,他知道我知道....

举几个简单的例子:

(1)在价格或数量竞争中，企业可能知道自己的成本，但不知道竞争对手的成本;

(2)投资于研发的公司可能知道他们的项目进展如何，但不知道还有谁在处理同样的问题;

(3)政府可以设计税法，但不得设想人民为逃避纳税会想出什么办法;

(4)各国可就全球气候变化的成本和效益达成不同的气候变化协议;

(5)原告可以向被告提供和解，但不知道被告能够提起什么样的诉讼案件，或者被告认为原告能够带来什么样的案件。

举例：

例1：

一个市场竞争模型“Tough”，两个公司，公司2(进入者)必须决定是否进入一个市场，并且公司1(现任者)必须决定是战斗还是容纳公司2进入。让我们修改这个游戏通过假设概率1−p,是现任者选择强硬策略“tough”的概率,而概率p,现任者选择normal的概率。游戏的回报取决于现任者是强硬还是正常（tough or normal）:

例2：

经济学系的两名教师都想为他们的系招一名优秀的研究生。任何一名教员都可以通过打私人电话推广研究生项目来确保学生接受这个提议。然而，这需要付出一定的代价。通过私人电话抢夺学生需要承担一些道德的风险。

假定回报可以表示如下:

假设教师同时选择他们的策略，当然教师有私人信息成本的电话。也就是说，教师i知道c_i，并且认为c_j是从

上的一致分布随机抽取的。此时，对c_j的认知是大家都知晓的。

又或者理解为，我们可以假设玩家1是一个资深教员，他从长期经验中知道c1 = 1/2, c2 = 2/3。然而,玩家二是一个新手助理教授认为,c1,c2∼U[0,2]，并且独立。那么两个玩家在信息上的相差就代表这个博弈为非完全信息博弈.

定义

Definition 1： 一个非完全信息博弈 G = (Θ, S, P, u) 包括

1. 集合 Θ=Θ1 × ... × ΘI , Θi是玩家i的(有限的)集合.

2. 集合 S = S1 × ... × SI , Si是i玩家所有可能的策略集合.

3. 一个联合概率分布p(θ1,……θI)。对于有限的空间类型,假设所有θi p(θi)> 0∈Θi。每个策略的概率分布

4. 支付函数 ui : S × Θ → R.

根据这个例子，那么有：

1. Entry: Θ1 = {tough, normal}; Θ2 = {normal}.

2. Auction: Θ1 = Θ2 = [0, 1].

3. Public Good: Θ1 = Θ2 = [c, c].

Remark 1： 注意，收益（回报）不仅取决于你自己的类型，还取决于你对手的类型。如果ui依赖θi,但不是在θ-i,这时候会说博弈中有private values私有值。

为了分析这些类型的游戏,我们需要一个基本Harsanyi(1968)(诺贝尔奖获得者)的理念:

博弈的不完全的信息可以被认为是游戏完全（complete）但不完美的信息（imperfect information）。这使得第一步(选择θ1,…θI),但并不是每个人都观察的到（nature）亦或另一个玩家的移动(如，玩家i知道θI但不知道θ−i)。考虑以这种方式制定进入模型。

在分析这类游戏时，我们认为自然(nature)只是另一个玩家。唯一的区别是，nature没有最大化回报，而是采用了一种固定的混合策略。这一观察应该使以下定义看起来更明显。他们只是说，为了分析一个不完全信息的游戏，我们可以看到游戏的纳什均衡，nature是一个玩家。

Definition 2： 一个博弈G中， 贝叶斯的玩家i的纯策略函数 fi : Θi → Σi. 则 S^Θi 就是Bayesian pure strategies贝叶斯纯策略集合.

Definition 3： A Bayesian strategy profile (f1, ..., fI ) 是贝叶斯纳什均衡，对于所有的玩家i。

{f_i \in arg max_ f_i^' }\in S_i^{\Theta_i  }\sum {\theta \in \Theta } u_i({f_i^' (\theta_i)}, {f{-i} (\theta_{-i})},\theta_i, \theta_{-i},) p(\theta_i, \theta_{-i})

 或者对于所有的玩家来说：

\sum {\theta{-i} \in \Theta_{-i} }  u_i(f_i(\theta_i),f_{-i}(\theta_{-i}),\theta_i,\theta_{-i}) \geq \sum {\theta{-i} \in \Theta_{-i} }  u_i(s_i, f_{-i}(\theta_{-i}),\theta_i,\theta_{-i}) p(\theta_{-i}|\theta_i)

定义的第二部分只是说，在假设你知道你的类型时，最大化自己的预期回报，那么你为每种类型选择的策略应该在你拥有该类型的前提下最大化你的回报。

Remark 2 贝叶斯纳什均衡是一个简单的游戏,这里，Nature先采取行动的纳什均衡,选择θ∈Θ，它一个分布概率p(θ),揭示了玩家i选择θi的概率。

具体求解此非完全信息博弈的贝叶斯纳什均衡策略，请参照

【出处： https://web.stanford.edu/~jdlevin/Econ%20203/Bayesian.pdf】

2. 发展历史

描述

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

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

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

=======主要事件=======

3. 发展分析

瓶颈

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

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

未来发展方向

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

Contributor: Ruiying Cai