第19卷第4期 广西师范大学学报(自然科学版) Vo1.19 No.4 2001年l 2月 JOURNAL OF GUANGXI NORMAL UNIVERSITY December 2001 量子“囚徒困境’’ 杜江峰,李卉,许晓栋,范杨梅,石名俊,叶邦角,翁惠民,周先意,韩荣典 (中国科学技术大学量子通信和量子计算实验室,近代物理系,安徽合肥230027) 摘 要:J.Eisert,M.Wilkens和M.Lewenstein量子化了经典博弈论中的一个著名的倒子——囚徒困境 (Prisoners’Dilemma).在他们提出的物理模型中,如果两名博弈参与者采用纯量子策略,就能避免“困境”的 出现,并且在该量子模型中,两名参与者的收益值都高于经典模型中的收益值. 关键词:量子纠缠;量子对策;量子博弈;Nash均衡 分类号:O41 3 文献标识码:A 文章编号:1001—6600(2001)04—0001—06 博弈论是应用数学中具有重要意义和应用价值的分支,在经济学、社会科学以及进化生物学中有着 广泛的应用….在John.Von.Neumann发表了关于“二人零和”博弈的基本定理(1 928)和其著作{Theo— ry of Games and Economic Behavior》 之后,博弈论得到了蓬勃的发展并已成为现代经济学的基础之 一.如今,博弈论已经被推广到量子领域 ~ ,其原因主要有如下几点:①由于经典博弈论的基础是概率 论,因此将“量子概率”引人博弈论具有基础意义;②在生物学中.博弈论被应用于分子水平上,而在分子 水平上的物理规律是量子的,因此有必要将博弈论推广到量子领域;③博弈论和信息论有着内在的联 系.事实上,博弈参与者是依据自己所拥有的信息做出决策的,并且决策的传递和博弈结果的仲裁在本 质上是信息传递的过程,而信息本身是量子的.因此博弈论的量子化不可避免. 量子博弈论的研究目前已取得了一些成果,D.A.Meyer研究了“PQ问题”(PQ Game) 5l——一个 和传统的翻硬币游戏类似的博弈过程——并发现博弈的一方可以通过采用量子策略战胜他的“经典”对 手.J.Eisert,M.Wilkens和M.Lewenstein量子化了“囚徒困境 (Prisoner’s Dilemma) ],通过量子化 找到了一个不同于经典博弈的均衡点并解决了经典模型中存在的 困境 .L.Marinatto和T.Weber研 究了 性别对抗博弈”(Battle of the Sexes Game/ 并给出了这个博弈的量子化模型的唯一的均衡.s. C.Benjamin和P.M.Hayden对多人量子博弈的研究 表明在这类博弈中可以存在“相干”的平衡策略. 1经典博弈论 任何博弈在数学上都可以表示成以下三个要素 ]: ①参与人(Players),以i=1,2,…表示. ②策略(Strategies),每一个参与人一般有若干策略可供选择,它们构成了该参与人的纯策略空间 (Strategic Space).参与人i的纯策略空间可以用S.表示,倘若S 由 个纯策略构成,则有S 一( ,0 , … ).纯策略空间有时也可以是连续的. ⑨每个参与人的收益(Payoff)函数.即参与人i的收益函数为¥ ( ),其中 =( …, )是参与 收稿日期:200l—Og—Ol 基金项目:国家自然科学基金资助项目(10075041,10075044);中国科太青年科学基金 作者简介:杜江峰(1969),男,江苏无锝人,中国科学技术大学副教授. 维普资讯 http://www.cqvip.com
广西师范大学学报(自然科学版) 第l9卷 人的策略组合(Strategy Profile),s,表示参与人 所选的策略.显然,收益函数¥ 0)与s有密切关系. 策略空间、收益函数以及参与人的与博弈有关的特征等知识构成博弈的信息,从信息的角度,博弈 可以分为完全信息与不完全信息两类、完全信息是指每一个参与人对自己以及其他局中人的策略空间、 收益函数等知识有完全地了解,否则,博弈就是不完全信息的.博弈的分类还可以从参与人行动的先后 次序着手.如果参与人同时选择行动 则称博弈为静态的 要求 同时”不一定等于规定大家在同一时刻 一起行动、通常在时间上虽有行动的先后,但是参与人彼此不知道其他人在采取什么具体行动(直到博 奔结束),其效果仍等价于他们在同时行动,此时我们仍称它是静态博弈.倘若参与人的行动有先后顺 序,后行动者可以观察到前行动者的行动,并在这基础上采取自己最有利的策略,博弈就是动态的.上述 两种划分如果两两交叉,就可以得到完全信息静态博弈(static games of complete information)、完全信 息动态博弈(dynamic games of complete information)、不完全信息静态博弈(static games of incom- plete information)、不完全信息动态博弈(dynamic games of incomplete information)4种情况. 完全信息静态博弈属非合作博弈范畴.非合作博弈的基础是Nash在1950年和1951年所发表的 两篇论文.这两篇论文在非常一般的意义上定义了非合作博弈及其均衡解,并证明了均衡解的存在性. Nash本人也因在这两篇文章中所做出的突出贡献获得了1994年的诺贝尔经济学奖.他所定义的均衡 称为Nash均衡(Nash Equilibrium). Nash均衡是什么意思呢?假设有 个人参与博弈,给定其他人的策略的条件下,每个人选择自己的 晟优策略t所有参与人选择的策略构成一个策略组合.Nash均衡指的是这样一种策略组合,这种策略组 合由所有参与人的晟优策略组成,也就是说,给定别人的策略的情况下,没有任何单个参与人有积极性 选择其他策略,从而没有人愿意打破这种均衡. 用数学语言对上述Nash均衡的想法进行概括、我们有如下定义 一: 纯策略的Nash均衡 完全信息静态博弈问题中 参与人以i=1,2 …, 表示 为参与人的个数, 设第i个参与人的策略空间为s 他的纯策略为 ∈S ,收益函数为¥。( ),s为所有参与人的纯策略组 合.s--(s ,s .'' );如果对所有的参与人i( :1,2,…, )均成立¥。( ,…,s二 ,5 ,5 (5 .… …5 sA “,s:),V ∈S。,那么,S称为该博弈的纯策略的Nash均衡. 下面我们用Nash均衡这个概念分析博弈论中的一个著名例子“囚徒困境”+ .-,s )≥¥。 2经典“囚徒困境” “囚徒困境 是经典博弈论中的一个极富代表性的著名例子.这个例子的创造本身就奠定了非合 作博弈论的理论基础,并且它可以作为实际生活中许多现象的一个抽象概括、 囚徒困境讲的是两个嫌疑犯(Alice和Bob)作案后被抓住,被分别关在不同的屋子里审讯、他 们每个人都有两种选择(策略):坦白(Defect,策略,))和抵赖(Cooperate,策略c).告诉他们:如果 两人都坦白,各判刑4年(收益均为P一1);如果两个都抵赖,因证据不足,各判刑2年(收益均为r一3)、 如果其中~人坦白,另一人抵赖,坦白地放出去(收益为f一5),抵赖的判刑5年(收益为 —O)、表格1给 出“囚徒困境”的策略式表述.表中每一个的两个数字代表对应策略组合下两个囚徒的收益. 表1“囚徒困境”的收益矩阵 两个人的目的都是尽可能的是自己的收益最大化.在这 个博弃中,坦白(D)是占优策略(dominant strategy),也就 是说,不论对方的选择是什么,个人的最优选择是坦白.比如 说,如果Bob抵赖,Alice坦白的话被放出来,抵赖的话被判 2年;如果Bob坦白,Alice坦白的话被判4年,抵赖的话被 括号中的第一1、数是Alice的收益值,第二个数 是Bob的收益值. 判5年.所以,Alice的占优策略是坦白,Bob的占优策略也 是坦白.结果,理性的推理将迫使每个人选择坦白,而显然此 维普资讯 http://www.cqvip.com
第4期 杜江峰等:量子“囚徒困境” 时两人的收益要比他们都选择抵赖时差.用博弈论的术语讲,策略组合(坦白,坦白)是一个Nash均衡: 任何单方面的偏离该策略组合都不能使得偏离者的收益提高;当一个参与人选择坦白时,另一个参与人 只有选择坦白才能使自己的收益最大化.这也正是囚徒的“困惑”之所在. 3量子“囚徒困境” 在J.I: ̄isert,M.Wilkens和M.Lewenstein最近的一篇文章中+研究了“囚徒困境”的量子化的模 型 .“囚徒困境”的量子化物理模型如图l所示. G) G) 圈1 “囚徒困境 的量子化物理模型 图2可分离博弈中Alice的收益图 这个模型由以下三部分组成:①一个两比特产生源,每一个参与人拥有一个比特;②参与人的操作 装置.允许参与人操作属于他自己的那一个比特,这些操作实际上就是参与人的策略;③一套测量装置, 通过测量两个比特的最终状态已决定每一位参与人的收益值.每一个参与人都十分清楚这三部分(比特 源、每个人的操作装置、最终的测量装置).因此这个模型所构成的博奔属于完全信息静态博弈. 量子化的过程如下:将经典策略D(坦白,De[cot)和c(抵赖,Cooperate)的可能结果对应为一个两 态系统(即一个量子比特)的Hilbert空间的基矢,分别用ID)和Ic)表示.在任何一个时刻,博弈的状态 可以用这两个量子比特(分别属于两个参与人)的直积空间中的态表示.这个直积空间的基矢显然是 ICC)+CD),DC)和lDD),其中第一项代表Alice的量子比特,第二项代表Bob的量子比特. 博弈的初态用l 一 lCC)表示。 是两个人都知道的酉算符.Alice和Bob策略行为分别用酉算 符0 和『1T (属于策略空间S)表示.由于参与人的策略行为相互,c0和 应分别作用在他们各自 的量子比特上.因此策略空间s可以等同于2×2酉群的某个子集.在Alice和Bob实施了策略行动之 后,博弈的状态变为( @7 j lCC).然后Alice和Bob将这个态交给测量装置已决定他们各自的收 益.测量装置有两部分组成:一个可逆的两位量子门。以及紧跟其后的一对SternGerlaeh型探测器.每 个探测器有两个通道,分别记为 =C和口一D.记在到达探测器之前博奔的状态为l, >一l , (驴 .0 ”,则有 r)一 一( ⑧ ) CC) (1) 对Pr)的探测会导致某一个结果。比如说一 --CD,并根据表格l中的收益矩阵给出相应的收益.由于 量子力学在本质上是概率性理论,因此参与人的收益也应该是“期望 收益.例如,Alice的期望收益应由 式(2)给出 ¥』一rPcc4-pPDD4-tPr ̄'4-sPeD. (2) (2)式中P 一I( I奶) 是测量结果为 的联合概率.Bob的期望收益可以通过将(2)式后两项中 维普资讯 http://www.cqvip.com
4 广西师范大学学报(自然科学版) 第19卷 的t和 互换得到(表格1中给出了r,p, , 的具体数值).显然Alice的期望收益¥ 不仅依赖于她自己 的策略驴 而且和Bob的策略驴 有关;同样,Bob的期望收益¥ 不仅依赖于他自己的策略口 ,而且 和Alice的策略驴 有关. 在Eisert等人的文章中.他们将策略空间为2×2酉阵的一两参数集台. 。 昙 驴( , ) 一sin 其中O≤ ≤ ,0≤《 l,2.特别的.策略C(Cooperate)可以表示为 e 驴(0,0)-- . ㈨ 策略D(Defect)可以表示为 西一驴c ,。 一 . cs 为了保证这个博弈的经典形式能够被包含于这个量子模型中,我们需要附加条件 [ ,西 D]一0;[ ,D e]=0{[ .e⑧D]一0 (6) 由这些条件可以得出对于任何从子集S。一{ ( ,Oj ∈[0, ])取出的一组策略,联合概率P 总可以分 解成P = 声 的形式,其中声∽--COS ( /2),声 一1一声 .很明显,声 可以解释为单个参与人选 择C策略(Cooperate)的概率,那么(6)式便保证了这个量子化模型包含了最一般情况下的经典囚徒困 境.即参与人采用混台策略时的经典囚徒困境.显然量子策略集S要比S。大得多,并且正是其中的量子 部分S 。提供了策略的附加自由度.根据经典对应原理(见(6)式),这个量子化方案可以应用于任何两 个参与人、两种选择的对称博弈中,而且是“正则”扩展. (6)式的解可以写作 =exp{irD圆D/2), (7) 其中 ∈[0, /2]是实参数.事实上, 是博弈的纠缠的度量.对于可分离的博弈有7--0,这时对于任何 一组策略E, 和 ,联合概率P 总是可以分解的.图2中给出了y一0时Alice的期望收益. 在该图以及图3中选择了一个特殊的参数化 表述,使得策略驴 和u一只依赖于一个参数z∈ [一1,1].当z∈[0,1]时, 一驴(杯,0);当t∈ [1,0)时,u =口(。.--tu/2)(对Bob也一样).策 、 略D对应于 一1,策略c对应于 一0,而策略Q对 ’、 应于 一1- 口 可以看出.不论Bob选择什么策略( ),Alice 只有当选择策略D时才能使自己的收益最大化. 由于博弈是对称的,Bob也只有当选择策略D时 才能使自己的收益最大化.因此,西@D是占优策 略,可分离的量子博弈不能体现出优于经典博弈的 特性. 圈3最大纠缠博弈中Alice的收益圈 当博弈是最大纠缠的,即y= /2时,情况发生 了根本性的变化.这时任何一组策略都不存在经典对应,不过当两个参与人都选择 一0,博奔仍然表现 为经典的.例如,在5。圆S。上(即 =伽一0时)只 —ICOS( + ̄B)cos( /2)cos( /2)I。是可以分解 的,并不体现出非定域的关联.图3为Alice的收益与策略驴 , 的关系图.这里采用和图2中一样的 维普资讯 http://www.cqvip.com
第4期 杜江峰等:量子。囚徒困境” 5 参数化表述. 设Bob的策略为D,则Alice的最佳对策为 盆;m z =( ㈣ 而当Bob选择e时,Alice的最佳对策是D,所以Alice没有占优策略 由于博弈是对称的,这样的分析 对Bob也成立.因此,D@D不再是占优策略意义下的均衡 事实上,西@西甚至不再是Nash均衡,因为每个参与人都可以通过单方面改变自己的策略提高收 益.这时博弈出现了新的Nash均衡龟@盆.事实上,对任何 ∈[O, ]和 ∈[0, /2],有¥ U(8, ,Q) 一cos z(0/2)(3sinz COS z ≤3,类似的有¥ (盆,0 J≤¥ (固,盆),V ∈S;因此任何参与人都不能 通过单方面偏离龟@自提高收益.容易证明,砬@Q是唯一的均衡,也就是说,理智的分析使得两个参与 人都选择砬作为自己的最优策略.在这个新的Nash均衡上,博弈的最终状态是}CC>,参与人的收益是 ¥ (砬,盆)一S (盆,砬)一3.很明显,Alice和Bob可以通过选取量子策略(驴 一 一Q)使得博奔的结果 对双方都更加有利;这时,博弈的结果为(抵赖,抵赖),而Alice和Bob的收益均为3,这显然是在保证博 弈公平性的前提下Alice和Bob所能获得的最大收益值,经典博弈中“困境”将不再存在.并且这个结果 是“稳定的”(Nash均衡):任何人单方面偏离这个结果都将使得自己的收益减少,因此没有人愿意(有积 极性)选取其他的策略. 4结论 在Eisert等人的文章“ 中,他们给出了将经典博弈推广到量子博弈时的正则条件,这个条件保证了 经典博弈能够被包含在量子模型中,从而使得经典和量子博弈有可比性.而且他们发现当把经典“囚徒 困境”扩展为量子博弈时,经典博弈中的“困境”将不复存在.这一点和量子密码通讯和量子计算中的情 形非常相似:引入纠缠后的量子博弈中,量子策略要比经典策略更具有优越性. 在我们最近的工作中,我们研究了量子“囚徒困境”的性质与其纠缠度之间的关系,Eisert等人的结 果实际上是包含在我们的结果当中的;这个工作已经即将在PLA上发表.另外,我们利用核磁共振技术 实验实现了这个博奔的全过程,到目前为止,这是首次在实验上实现量子博奔(已投稿至Phys Rev Lett) 我们发现:当博弈的纠缠度发生变化时,博弈的性质也会随之发生变化,并且这种变化在某些点 上是不连续的;具体地说,博奔的纠缠度(用y表示)在区间ro, /2]上有两个阈值 , 。( < ).当 o4y< 时,博弈将表现为完全“经典”的:唯一的Nash均衡以及博奔最终的结果和经典情形完全一 样}当 <y≤ /2时,博弈是完全“量子”的:唯一的Nash均衡以及博弈最终的结果都和博弈处于最大 纠缠态时的情形完全~样;而当 ≤y≤ 时,博奔出现了两个Nash均衡,然而令人惊讶的是,尽管博 弈的物理模型对于两个博奔者的交换是对称的,但是博奔在这两个Nash均衡上却是不对称的:两个博 弈者的均衡策略不相同并且最终的收益也不一样.事实上,这时的博弈虽然仍然可以看作是量子的,但 却表现为不同于经典博奔中的“困境”的、但却类似的另一种“困境” 参考文献 :1]Nowak M A,Sigmund K.Nature[J].1999,398:367. [0]Neumann J von,Morgenstern0.Thetheory of games and economic behavior[M].Princeton:PrincetonUniversity Ptess.1 947. [ Ball P Everyone wins in quantum games EJ].NaturetScience Update,1999,18. [4]Peterson I、Quantura gamesLJ]、Science News 1999,156:334. 维普资讯 http://www.cqvip.com
广西师范大学学报(自然科学版) 第1 9卷 二5]Meyer D A.Quantum strategies口].Phys Rev Lett,l999,82:1 052. [6]Eisert J,Wilkens M.Lewenstein M.Quantum games and quantum strategies[J].Phys Rev Lett,1999,83:3 077. [7]Marinatto I .Weber T.A quantum aptroach to static games of complete information[J].Phys Lett A,2000.272 29I. [8]Benjamin S c,Hayden P M.Multi player quantum games[J].Phys Rev A,2001,64:30 301. THE QUANTUM PRIS0NERS’DILEMMA DU Jiang—feng,LI Hui,XU Xiao—dong,FAN Yang—mei,SHI Ming-jun YE Bang—jiao,WENG Hui-rain,ZHOU Xian-yi,HAN Rong—dian (I aboratory of Quanturrl Communication and Quantum Computation,Department of Modern Physics,230027一 University 0f Science and Technology 0f China Hefoi 230026,China) Abstract:J.Eisert,M.Wilkens&M.Lewenstein quantizedthe Prisoners’Dilemma,whichis afamous instant of the classical game theory.They found that this garrm ceases to pose a dilemma if the two players adapt quantum strategies.And the payoffs for the players are better than that in the classical game・ Key words:quantum elltanglement;quantum strategies;quantum games;Nash equilibrium (责任编辑李小玲) 广西师范大学学报(自然科学版)入选“中国期刊方阵” 根据科技鄣“若干公布科技期刊方阵名单的通知”(国科发财字[2OO1]340号),广西壮旗自治区科 学技术厅转印发了“羌干《广西水利水电》等9种科技期刊入选科技期刊方阵的通知”(桂科成字[2001] jS号),我刊榜上有名. “中国期刊方阵”的建设是现阶段我国期刊出版事业发展的需要,是推进新世纪我国期刊发展的战 略性举措,它将促进我国期刊“精品战略”的实施.“中国期刊方阵”实行动态管理,定期调整,优胜劣汰的 制度.科技期刊方阵的建立,目的是促进我国科技期刊的发展,促使我们不断优化提高科技期刊的水平, 早日与国际期刊接轨.入选中国科技期刊方阵是对我刊多年来始终坚持上档次、高品位的办刊方针和强 化创造文化精品的躺辑意识,发扬严谨周密的编辑作风,严格执行有关国家标准和编排规范等办刊方向 的肯定;同时也肯定了我刊已迈入中国先进期刊的行列.这一成绩的取得,是在我校、行政的直接领 导下的成果并与匮新闻出版管理部门的正确指导密不可分. (撰稿马殷华)
因篇幅问题不能全部显示,请点此查看更多更全内容
Copyright © 2019- huatuo9.cn 版权所有 赣ICP备2023008801号-1
违法及侵权请联系:TEL:199 18 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务