量子博弈论与人工智能

量子博弈论与人工智能 （一）量子博弈论——引言 量子博弈论应该算作是量子信息（或者说量子物理学）与博弈（对策）理论相结合 的产物。博弈论（在量子博弈出现之前，我们更愿意把它称为“经典”博弈论，即 非量子力学的，以示区别）或许应该看作是应用数学的一个分支，它研究的是相互 竞争和/或合作的博弈主体们的决策以及这些决策之间的相互作用的问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 。博弈论 已经在经济学、政治学、军事、外交、国际关系、公共选择、犯罪学还有生物学的 许多方面得到了广泛的应用，并成为了现代经济学不可或缺的基石之一。 或许有人会觉得奇怪，像经济学等这样一些看上去明显是“经典”的而非“量子” 的领域中，量子力学的基本规律（如量子叠加、量子相干性以及量子纠缠等等）会 起作用。然而，如果我们注意到所有博弈的一个共性以后，博弈论和量子物理之间 的联系就会变得明显而自然。实现这一联系的桥梁就是“信息”。一方面，在任何 一个博弈过程和现象中，当博弈的主体自己的决策“传递”给其它人、或者仲裁者 时，他们都是在交流信息，而且每一个博弈参与者都希望在给定的（物理）条件下 获取尽可能多的信息。另一方面，“信息”本身是“物理的”，这不仅仅是因为信 息的载体一定脱离不了具体的物理体系，而且更因为物理规律将极大的影响信息的 传递和处理方式；特别是如今量子信息理论的飞速发展和巨大成就使得人们越来越 清晰地认识到这一事实并对它加以利用，形成了众多的新的交叉研究方向：如量子 计算、量子密码通讯等等。量子博弈论也是这一交叉的产物之一，它使得量子叠加 、甚至是量子纠缠这样一些独特的量子现象在博弈中成为可能，并引发了一系列新 颖并有价值的结果，极大地丰富了博弈理论本身。除此以外，量子博弈论还给现有 的量子计算和量子通讯等研究领域提供了新的研究 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 和思维角度。许多量子过程 都可以看作是“博弈”：量子密码通信中，窃听过程也可以看成是窃听者和信息发 送、接收者之间的“博弈”；量子计算可以看作是两个分别拥有经典算法和量子算 法的计算者在计算速度上的一场“竞争”；量子态克隆甚至也可以理解为“博弈” 。 当然，过早的期待量子博弈进入现实生活或许不太现实；然而这并不意味着量子博 弈论是纯粹的纸上谈兵。除了在前面提到的应用以外，在不算太远的将来我们可以 期待的众多可能性之一是，随着量子通讯的完善和实用化，建立一个基于量子力学 规律的市场，在那里所有的信息将由量子物理体系来承载，从而使得量子博弈成为 不可避免的。 （二）量子博弈论——博弈、均衡 在介绍量子博弈论之前，我们有必要先回顾一下经典博弈论的基本概念。在量子博 弈论中这些基本的概念被保留，并且是我们分析问题的基础。 任何一个（经典）博弈可以通过如下几个要素来定义：（1）博弈的主体，或参与 者（Players）；（2）博弈中每个参与者可能采用的所有策略（Strategies），我 们称之为策略空间（Strategic Space）；在每一次博弈中，所有参与人的策略的 集合成为一个策略组（Strategic Profile）（3）博弈的结果，量化的博弈结果实 际上就是所谓的“收益”（Payoffs）。显然，在大多数有意义的博弈中，单个参 与人的收益不仅仅与自己的策略有关，而且和其他所有的参与人的策略都密切相关 ，可以看成是所有参与人策略的某个函数。在这里，我们假定每个参与者都是最大 理性的，也就是说他们总能够采用正确的策略而从不犯错误。当然，如今博弈论的 发展已经能够处理研究非最大理性行为，但是要稍微复杂一些，我们把这一部分放 到后面讨论。 严格来说，上面定义的策略应该叫做“纯策略”，也就是说在每个参与人都确定的 使用了其策略空间中的某个特定的策略。然而，在许多可重复多次的博弈中，参与 人也许会在某一轮选择一个策略，而在另一轮中选择另一个策略；在这种情况下， 我们称参与人采用了“混合策略”。用数学的语言描述，一个混合策略就是在策略 空间上的一个概率分布（即“纯策略”的概率混合），参与人在这多次重复的博弈 中所期望的平均收益显然将 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 达成为这些概率分布的函数而不再是某个特定的纯策 略的函数。 不论是经典的还是量子的博弈论中，最重要的概念莫过于“Nash均衡”。这里的 Nash便是在电影《美丽心灵》（A beautiful Mind）中的那个有点“神经兮兮”的 男主角^_^。由于Nash均衡的重要性以及对经济学产生的重要影响，他被授予 1994 年的Nobel经济学奖。Nash均衡这一概念的开创性在于它用方程刻画了“人类理性 ”这一原本让数学家们和经济学家们感到无从下手的东东，并在实际应用中获得了 巨大成功。 Nash均衡是一个具有如下性质的策略组：对于任何一个参与人而言，如果其他的 参 与人都选择这个策略组中对应于自己的那个策略，那么这个参与人也只能选择这个 策略组中应于自己的那个策略才能使得自己的收益（在其他人的策略给定的情况下 ）最大化；在这样一个均衡里，谁也不会做出其他选择，否则其收益就会减小。简 单的用一句话说就是：我知道其他人会选这个策略，其他人知道我知道其他人会选 这个策略，我知道其他人知道我知道其他人会选这个策略……只有Nash均衡才能够 具有这种性质。 （三）量子博弈论——量子博弈的开端 量子博弈的第一篇工作出现在1999年的《Physical Review Letters》上 [D.A. Meyer, Phys. Rev. Lett. 82, 1052 (1999)]。这篇文章通过一个十分简单的“翻 硬币”博弈，使人们第一次看到量子策略在对抗经典策略是所能发挥的巨大威力。 在这个我们称之为“PQ翻硬币”问题的博弈中，P首先将一枚硬币正面朝上放在一 个箱子里，然后P和Q轮流（先是Q，接着是P，再是Q）对硬币进行翻转（或不 翻转 ）的操作。在这个过程中不允许打开箱子看硬币的状态。轮流操作完成以后打开箱 子，如果硬币正面朝上，那么Q获胜；否则P获胜Ｕ飧霾?目梢杂檬找婢卣蟮男 问? 表示如下： ---------------------------------------- NN NF FN FF ---------------------------------------- N -1 +1 +1 -1 F +1 -1 -1 +1 ---------------------------------------- 其中行和列上的标号（N和F）分别代表P和Q的纯策略：F代表翻转（flip over）， N代表不翻转（no flip over）。表中的数字为P的收益：1意味着获胜，-1意味着 失败。比如，考虑第一行第二列表示Q的策略为第一次选择翻转而第二次选择不 翻 转，P的策略为不翻转。如果用H表示硬币正面朝上，T表示硬币背面朝上，那么 这 是硬币的状态依次为：H，T，T，T，所以P获胜，收益为1。 我们很容易确定P的最优策略：假如他选择不翻转，那么当Q翻转偶数次时，他 就会 输；假如他选择翻转，那么当Q翻转奇数次（一次）时，他也会输。因此“PQ翻硬 币”问题没有确定性解，也没有确定性Nash均衡：不存在这样的纯策略组合，使得 参与人无法通过单方面改变策略提高收益。然而，这个问题却存在概率性解。不难 验证，当P以1/2的概率选择翻转，Q以1/4的概率选择他的每一个纯策略时，可 以构 成一个混合策略Nash均衡，此时每一个人的期望收益都是0。 在经过了以上分析以后，P认为这个“游戏”是公平的，然而令他不解的是，在和 Q玩过几次以后，他发现自己每一次都输。导致这一结果的根本原因在于Q采用的是 量子策略而不是经典策略，下面我们来看看Q采用什么样的量子策略可以使得他 自 己每次有获胜。 这里为了分析问题我们不得不引入Diract记号来表示一些量子态：如果我们用|H> 表示硬币正面朝上的（量子）态，而|T>表示硬币正面朝下的（量子）态，那么一 般而言，这个（量子的）硬币将可以处于这两个态的任意线形叠加态上。在这个博 弈中，硬币的初识状态显然应该是|H>，然后紧接着Q对着硬币进行操作。在经典 博 弈中，Q（以及P）要么保持硬币的状态不变，要么将它翻转，使得硬币要么处于 |H>态要么处于|T>态。然而在量子版本的这个博弈中，Q可以使用量子策略；事实 上，Q只要通过一个特定的幺正操作将硬币的态改变到这样一个叠加态|H>+|T>上， 他就可以确定性的每次都获胜。因为P始终是一个经典的博弈者，他不会使用量 子 策略，不论P翻转或者不翻转这个硬币，这个硬币的态始终保持在|H>+|T>这一叠加 态上；等到P完成了他的那一步，Q只要实施另一个相应的幺正操作便可以把硬币 的 状态还原至|H>上，这也就是为什么P每一次都输的原因。 接下来，Meyer还证明了，上面的这种情况中策略组 {Q所采用的策略，P的任何策 略} 都能够构成一个Nash均衡，其博弈的结果始终是每次都是Q获胜。 最后，Meyer给出了一些量子博弈论的一些基本定理： 定理1：在二人零和博弈中，参与人采用最优量子（纯）策略所获得的收益不会少 于他采用最优（经典）混合策略所获得的收益。 定理2：二人零和博弈不一定存在（量子，量子）型的均衡。 定理3：二人零和博弈至少存在一组（混合量子，混合量子）型的均衡。 证明就不再这里写了，如果感兴趣可以去参考文献。 （四）量子博弈论——“囚徒困境” “囚徒困境”是经典博弈论中的一个极富代表性的一个著名例子。这个例子的创造 本身就奠定了非合作博弈论的理论基础，并且它可以作为实际生活中许多现象的一 个抽象概括。 囚徒困境讲的是两个嫌疑犯（Alice和Bob）作案后被警察抓住，被分别关在不同 的 屋子里审讯。他们每个人都有两种选择（策略）：坦白（Defect，策略D）和抵赖 （Cooperate，策略C）。警察告诉他们：如果两人都坦白，各判刑4年（收益均为 ）；如果两个都抵赖，因证据不足，各判刑2年（收益均为 ）。如果其中一人坦 白，另一人抵赖，坦白地放出去（收益为 ），抵赖的判刑5年（收益为 ）。 两个人的目的都是尽可能的是自己的收益最大化。在这个博弈中，坦白（D）是占 优策略（dominant strategy），也就是说，不论对方的选择是什么，个人的最优 选择是坦白。比如说，如果Bob抵赖，Alice坦白的话被放出来，抵赖的话被判2年 ；如果Bob坦白，Alice坦白的话被判4年，抵赖的话被判5年。所以，Alice的占优 策略是坦白，Bob的占优策略也是坦白。结果，理性的推理将迫使每个人选择坦白 ，而显然此时两人的收益要比他们都选择抵赖时差。用博弈论的术语讲，策略组合 （坦白，坦白）是一个Nash均衡：任何单方面的偏离该策略组合都不能使得偏离 者 的收益提高；当一个参与人选择坦白时，另一个参与人只有选择坦白才能使自己的 收益最大化。这也正是囚徒的“困惑”之所在。 在1999年的《Physical Review Letters》里的一篇文章中J. Eisert等人研究了“ 囚徒困境”的量子化的模型 [Phys. Rev. Lett. 83, 3077 (1999)]。这个模型由 以下三部分组成：（1）一个两比特产生源，每一个参与人拥有一个比特；（2）参 与人的操作装置，允许参与人操作属于他自己的那一个比特，这些操作实际上就是 参与人的策略；（3）一套测量装置，通过测量两个比特的最终状态已决定每一位 参与人的收益值。每一个参与人都十分清楚这三部分（比特源、每个人的操作装置 、最终的测量装置）。 他们仔细研究了这个量子化的“囚徒困境”，发现如果这个博弈中量子纠缠为零， 那么整个量子博弈将回到经典博弈；而当博弈处于最大纠缠时，出现了一个新的 Nash均衡，在这个均衡下，Alice和Bob的收益都是3，这样一来，在经典博弈中 困 扰着博弈者的“困境”便不复存在。此外，如果Bob只采用经典策略而Alice采用量 子策略，则Alice总是能获得比Bob更高的收益。 这个工作以后，量子博弈得到了更加广泛的重视，越来越多的工作涌现出来，并展 现出量子博弈在许多方面的奇特性质。 （五）量子博弈论——纠缠带来的奇特性质、量子博弈的实验 这一节没有按照时间顺序，呵呵，因为我想早一点介绍我们组自己的工作。 不论在量子信息论的理论还是各种应用中，量子纠缠（即复合体系各子系统之间的 非定 域关联）都处在核心的地位。Einstein、Podolsky和Rosen在1935年提出著名的EPR佯谬 第一次揭示了量子纠缠的“非定域”的特征。在复合体系中，如果体系的态不能分解 成 各个子系统的态的直积的形式，那么子系统间就存在纠缠，复合体系的态称为纠缠 态； 对于处于纠缠态的复合体系，施加于其某一个子系统的操作将通过由于纠缠引入的 非定 域关联而影响到其它子系统。这种非定域关联不存在经典对应，是一种纯粹的量子 效应 。正是这种非经典的非定域相关性，使得量子纠缠成为量子信息诸多应用的基础。 例如 量子密集编码、量子密码通讯、量子隐形传态和量子计算都用到的量子纠缠。 既然纠缠在量子信息中起了重要作用，而量子博弈论又和量子信息论有内在联系， 因此 很自然地我们会想到量子纠缠也应该在量子博弈中有重要意义。事实上，J. Eisert等人 的工作已经表明处于最大纠缠态的量子博弈将比相应的经典博弈更具有优越性。 但是，如果不是最大纠缠又会是怎样的结果呢？在2002年发表在《Physical Review Letters》上的一篇文章（PRL 88, 137902 (2002)），我们对于“囚徒困境”博弈研究 了这个问题，发现当纠缠度的取值大小不同的区间时，这个博弈过程将表现出完全 不同 的性质。具体说来，当纠缠度小于某个阈值的时候，博弈将表现为完全“经典”的：唯 一的Nash均衡以及博弈最终的结果和经典情形完全一样；当博弈的纠缠度超过这 个值但 是不是太大的时候，博弈出现了两个Nash均衡，然而令人惊讶的是，尽管博弈的物理模 型对于两个博弈者的交换是对称的，但是博弈在这两个Nash均衡上却是不对称 的：两个 博弈者的均衡策略不相同并且最终的收益也不一样。事实上，这时的博弈虽然仍然 可以 看作是量子的，但却表现为不同与经典博弈中的“困境”的、但却类似的另一种“困 境 ”；最后，如果博弈的纠缠度继续增加直至大于另一个阈值时（但是还没有达到最 大纠 缠），博弈是完全“量子”的：唯一的Nash均衡以及博弈最终的结果都和博弈处于最大 纠缠态时的情形完全一样。 在纠缠度“不大不小”时出现的不对称现象很像是某种“对称自发破缺”，在我们后来 的一篇工作中，我们仔细研究了这一现象，有兴趣的话可以参考文献：JPA 36, 6551 (2003)。 在同一篇PRL文章中，我们还给出了量子博弈论是实验研究结果。我们利用核子 共振技术 对一个分子中的两个原子核进行操控，成功地再现了这个博弈的全过程，并且以很 高的 精度证实前面提到的理论研究结果。因为我不是很懂实验，所以这里就不多说誓言 细节 了。 （六）量子博弈论——多人量子博弈 我们还是回到时间顺序上来，呵呵。 多体问题总是很复杂，比如说两体相互作用总是可解的，而仅仅增加到三体问题后 便统统不可解，更不用说多于三体的问题了。这一点在量子博弈论中也不例外。多 人量子博弈不仅具有经典博弈所部不备的种种特性，甚至表现出在两人量子博弈中 都不曾出现的奇特性质。 第一次认真的研究多人量子博弈的是几个英国人Simon C. Benjamin和Patrick M. Hayden。他们在2001年的一篇Physical Review A （Rapid Communication）上发 表了一篇多人量子博弈的论文 [PRA 64, 030301(R) (2001)]。 他们的工作中研究了两类博弈，一个是三人参与的一个类似于“囚徒困境”的经典 博弈的量子化，另一个是“少数者博弈”。在这里，我们只介绍后者，因为在我看 来前者并不是很吸引人，呵呵。 “少数者博弈”是一类非常有意思的博弈；其模型很简单，每个参与人要么选择在 A方，要么选择在B放，等所有的参与人独立的选择完毕后，统计A、B双方的人数， 人数少的一方的每个参与人获得1点的收益，而另一方的参与人则获得零收益；如 果双方人数相等则大家都将获得零收益。这个模型其实代表了很多现实中的情况， 比如在股票市场上，A、B双方就好像是买入方和卖出方，结果总是人数少的一方 获 得更多的收益。 在Benjamin和Hayden的这篇文章中，他们首先研究了一个3人少数者博弈，发现 量 子化的博弈和经典博弈想必没有任何优越性。 但是4人少数者博弈会完全不同。在经典情况下，4个参与人的最优策略是每次都 随 机的选择（实际上这是这个博弈的Nash均衡），这样一来总是有一半的情况是两 个 人在A方两个人在B方，并且每个人的期望（平均）收益值都是1/8。但是，当我们 将该博弈量子化后，情况就变得完全不同：每次博弈都是一个人在一方而另外三个 人在另一方。这样一来，两方人数对等的情况出现的概率为零，从而使得每个参与 人的期望收益提高位1/4，而显然这是在保持博弈的公平性的情况下能够获得的最 好情况了。可以认为，这一现象的出现完全因为在博弈者之间引入的量子纠缠。 （七）量子博弈论——连续变量博弈的量子化、信息的不对称 “连续变量”博弈和“不对称信息”这两个部分本来并不一定要放在一起写的，只 不过由于这两个部分恰好是我们组最近一段时间的工作，而且不对称信息对量子博 弈的影响是在一个连续变量博弈的框架内研究的，所以就放在这同一小节中了。 在我们前面所涉及到的博弈中，每个参与人的经典策略的个数都是有限的；而在实 际生活中我们很容易找到一些博弈，在其中参与人的策略有无穷多个（比如位置、 时间的选择等），或者由于数学上的方便我们更愿意把它当作是连续取值的（比如 Money的数量、大量物品的个数等）。有限策略经典博弈（或者称为“分立变量博 弈”）的量子化模型在处理这些情况的时候将不再适用，我们需要新的方法来研究 其量子化。 在我们给出具体的量子化方法的时候，我们可以先来看看已有的分立变量博弈在量 子化的时候有没有什么东东是可以借鉴到连续变量博弈的。我们首先需要明确一下 经典博弈中策略的“经典性”到底是个什么意思，虽然我们以前在谈这个问题的时 候把它当作了某种想当然的东东。在这里，策略的“经典性”的意思就是说，两个 不同的策略在原则上是完全可区分的；这就是为什么在前面提到的分立变量博弈的 量子化中，我们采用互相正交的量子态代表经典博弈中所有可能的不同结果。这一 原则应该在量子化连续变量博弈的时候被保持，这样一来，由于这里出现了无穷个 经典策略从而有无穷种可能的结局，我们不可避免地要采用无穷维的量子体系来负 载着所有可能的经典结局。 在Physics Letters A 306, 73 (2002)中，我们给出了第一个基于上述思想的连续 变量量子博弈模型。并且对一个叫做Cournot’s Duopoly的博弈研究了它的量子版 本的性质。毫不以外的，量子的Cournot’s Duopoly的性质随着博弈者之间的纠缠 程度的增加，表现出越来越明显的超越经典博弈的优越性；当达到最大纠缠时，它 可以给出最好的结果。在这一点上，这个特定的连续变量量子博弈和“囚徒困境” 是有些类似的。 我们在接下来的一个工作 [Phys. Rev. E 68, 016124 (2003)]中，我们考察了信 息的不对称性对这个连续变量量子博弈的影响。之所以要考虑信息的不对称的原因 是，在现实生活中，博弈参与者们可能并不对所有的相关信息都有完整和正确的理 解，尤其是当他们的完整性和正确性不等时，将极大的影响到博弈的结果和性质。 我们发现，对于这类情况，如果信息的不对称程度太大的话，量子纠缠将是有害的 ，它会降低收益，甚至会使得量子博弈比经典博弈更差。 （八）量子博弈论——非最大理性博弈 在前面说到的所有的博弈中，我们都假设了博弈参与者有最大的理性，但是在现实 生活中去并不总是这样。人总要犯错误，我们没有理由强制性的限定在所研究的问 题中所有人都具有最大理性。 在这方面，最初的突破也许来自1997和1998年Damien Challet和Yi-Cheng Zhang的 进化的Minority Game（少数者博弈）。他们研究了具有多个（数目可以很大，或 许成百上千）非最大理性参与人的一个多次重复博弈，每一轮开始时每个参与人选 择自己是站在A方或者站在B放，然后如果A方总人数少，则选择A方的每个人获得1 点的收益，反之，如果B方总人数少，则B方每个人获得1点的收益；在这个博 弈中 参与人并不能最优的决定自己的策略，只能根据以前的每一轮中总结出的经验来判 断下一轮中采用的策略。Damien Challet和Yi-Cheng Zhang发现，尽管每个参与人 独立的选择策略，但是在经过了多次博弈后，他们的总体行为却表现出了某种程度 上的“合作”。 这样一个Minority Game可以看作现实生活中的很多行为的一个简化的模型，因此 具有重要的现实意义。我们在前面已经看到，Benjamin等人研究了4人的少数者博 弈的量子化，但是他们完全在最大理性的假设进行研究的。我们组最近尝试着将非 最大理性引入到量子博弈中，并且作了一些计算（cyju同学的本科论文里，呵呵） 。我们发现，如果引入某种量子化机制，使得博弈者之间出现某种量子关联（如量 子纠缠），确实可以观察到其优于经典博弈的表现。但是目前为止，我们的这些结 果还很初步，需要进一步的深入研究。