第3卷第4期 智能系统学报 Vol 3 Ng 4 2008年8月 CAA I Transactions on Intelligent Systems Aug 2008 量子博弈：新方法与新策略 王龙2，王靖2，武斌2 (1.北京大学工学院，北京100871；2北京大学机器感知与智能教育部重点实验室，北京100871) 摘要：论述了量子博弈的研究现状和最新进展.首先介绍了量子博弈中的一些基本概念和主要模型，即量子翻硬币 模型、Eisert量子博弈模型和量子Monty Hall模型：然后以这些模型为基础，讨论了当前量子博弈研究中的热点问题：多 人量子博弈状态纠缠、进化稳定策略和平衡态退相干性等：最后，对量子博弈的未来发展方向做了一些展望 关键词：博弈：量子博弈；量子信息；策略；平衡态 中图分类号：TP18文献标识码：A文章编号：1673-4785(2008)040294-11 Quan tum games:new methodologies and strategies WANG Long2,WANG Jing'2,WU Bin' (1 Center or Systems and Control,College of Engineering.Peking University,Beijing 100871,China;2 Key Laborapry ofMachine Perception (Ministry of Education),Peking University,Beijing 100871,China) Abstract:The current status of quantum games,including recent developments,is presented in this paper First, some basic concepts and models in quantum games are introduced,including the penny flpping model,the Eisert model and the Monty Hall model On the basis of these models,some current key problems in quantum games are discussed,including those involving multip layer games,state entanglement evolutionarily stable strategies,Nash equilibrium,decoherence,etc Finally,some future research directions in quantum games are pointed out Keywords:games quantum games quantum infomation;strategy,equilibrium 博弈论，又称对策论，是研究具有斗争或竞争博弈论的语言重新组织，故可认为量子博弈在量子 性现象的理论和方法.它既是现代数学的一个分支， 力学发展的初期就已经存在了.但“量子博弈这一 也是经济学的一个重要研究领域.博弈思想由来已概念被明确提出来是近20年的事.1999年，Esrt 久，但现代博弈论一般认为起源于数学家Von Neu~ 等人和Meyer分别对囚徒困境2和翻硬币问题I3进 mann和经济学家Morgenstem合著的《博弈理论和 行了量子化处理，成功地解决了经典博弈论所不能 经济行为》此后，经过许多学者的努力，特别是 解决的问题.此后，量子博弈作为独立的研究方向受 Nash在非合作博弈理论中的贡献，博弈论日渐成为 到了越来越多的关注，并被广泛应用于经济学4)、 重要的理论分析工具， 生物学7201、信息科学2121等诸多领域， 量子博弈是以量子信息论为工具研究博弈论的 经典博弈中有基于概率论的混合策略的概念， 一门交叉学科.由于大量的量子力学试验都可以用 而量子力学则是物理学家发明的一种基于概率论的 认识世界的方法，是量子世界强有力的描述工具.爱 收稿日期：200805-29 基金项目：因家自然科学基金资助项目(60674050,60528007). 因斯坦称量子力学是科学中真正的巫术.当物理学 通信作者：王龙.Email:longwang@pku edu cn 1994-2008 China Academic Journal Electronie Publishing House.All rights reserved.http://www.cnki.net
第 3卷第 4期 智 能 系 统 学 报 Vol. 3 №. 4 2008年 8月 CAA I Transactions on Intelligent System s Aug. 2008 量子博弈 :新方法与新策略 王 龙 1, 2 ,王 靖 1, 2 ,武 斌 1, 2 (1. 北京大学 工学院 ,北京 100871; 2. 北京大学 机器感知与智能教育部重点实验室 ,北京 100871) 摘 要 :论述了量子博弈的研究现状和最新进展. 首先介绍了量子博弈中的一些基本概念和主要模型 ,即量子翻硬币 模型、Eisert量子博弈模型和量子 Monty Hall模型;然后以这些模型为基础 ,讨论了当前量子博弈研究中的热点问题 :多 人量子博弈、状态纠缠、进化稳定策略和平衡态、退相干性等;最后 ,对量子博弈的未来发展方向做了一些展望. 关键词 :博弈 ;量子博弈 ;量子信息 ;策略 ;平衡态 中图分类号 : TP18 文献标识码 : A 文章编号 : 167324785 (2008) 0420294211 Quantum games : new methodologies and strategies WANG Long 1, 2 , WANG Jing 1, 2 , WU Bin 1, 2 (1. Center for System s and Control, College of Engineering, Peking University, Beijing 100871, China; 2. Key Laboratory ofMachine Percep tion (M inistry of Education) , Peking University, Beijing 100871, China) Abstract: The current status of quantum games, including recent developments, is p resented in this paper. First, some basic concep ts and models in quantum games are introduced, including the penny flipp ing model, the Eisert model and the Monty Hall model. On the basis of these models, some current key p roblem s in quantum games are discussed, including those involving multip layer games, state entanglement, evolutionarily stable strategies, Nash equilibrium, decoherence, etc. Finally, some future research directions in quantum games are pointed out. Keywords: games; quantum games; quantum information; strategy; equilibrium 收稿日期 : 2008205229. 基金项目 :国家自然科学基金资助项目 (60674050, 60528007). 通信作者 :王 龙. E2mail: longwang@pku. edu. cn. 博弈论 ,又称对策论 , 是研究具有斗争或竞争 性现象的理论和方法. 它既是现代数学的一个分支 , 也是经济学的一个重要研究领域. 博弈思想由来已 久 ,但现代博弈论一般认为起源于数学家 Von Neu2 mann和经济学家 Morgenstern合著的《博弈理论和 经济行为 》 [ 1 ] . 此后 ,经过许多学者的努力 ,特别是 Nash在非合作博弈理论中的贡献 ,博弈论日渐成为 重要的理论分析工具. 量子博弈是以量子信息论为工具研究博弈论的 一门交叉学科. 由于大量的量子力学试验都可以用 博弈论的语言重新组织 ,故可认为量子博弈在量子 力学发展的初期就已经存在了. 但“量子博弈 ”这一 概念被明确提出来是近 20年的事. 1999年 , Eisert 等人和 Meyer分别对囚徒困境 [ 2 ]和翻硬币问题 [ 3 ]进 行了量子化处理 ,成功地解决了经典博弈论所不能 解决的问题. 此后 ,量子博弈作为独立的研究方向受 到了越来越多的关注 ,并被广泛应用于经济学 [ 4243 ]、 生物学 [ 17220 ]、信息科学 [ 21223 ]等诸多领域. 经典博弈中有基于概率论的混合策略的概念 , 而量子力学则是物理学家发明的一种基于概率论的 认识世界的方法 ,是量子世界强有力的描述工具. 爱 因斯坦称量子力学是科学中真正的巫术. 当物理学
第4期 王龙等：量子博弈：新方法与新策略 ·295· 家将这个“巫术应用于博弈论时，发现它对于博弈 另一人背叛卿一人对警察抵赖，另一人坦白)，合 的描述要优于经典博弈.这种优越性主要基于量子 作的判5年，背叛的释放：如果双方都背叛即都对 化博弈扩大了原经典博弈的策略集以及纠缠态的引 警察坦白)，则各判4年.这个博弈的收益矩阵为 入.策略集的扩大使得寻找满足条件的策略更加容 C D 易实现；而纠缠态的引入从一定程度修正了“个体 C-2-5 都是理性的”这一基本经典假设，互相纠缠的状态 D0-4 成为博弈个体之间相互“关照程度的度量，正如人 在大多数文献中，为了讨论方便，不失一般性，将收 群中的亲友之间进行博弈时，会把对方的收益部分 益矩阵中的每一项加5，使收益矩阵成为非负矩阵： 当作自己收益一样21.事实上，博弈论作为研究理 C D 性策略主体如何解决冲突的理论，本身就蕴含着经 C30 典描述所无法满足的复杂性，如博弈个体的声誉，博 D51 弈个体之间的网络结构等对博弈结果的影响2).而 进一步地，称{，，…为纯策略集，其中的 在量子信息论框架下产生的量子博弈论，由于存在 每个元素称为纯策略.用表示个体使用纯策略号 量子态的相干叠加和纠缠，往往能够解决一些经典 的概率，称(p,,A)为一个混合策略.混合策 博弈论所不能解决的难题，如经典的囚徒困境博奔 略集可以表示为 在量子博弈的框架下就能摆脱困境.同时，量子力学 对现实世界的描述语言和相关概念，也为博弈论提 S=p=a,A,n)eR:n≥0A= 供了新的研究课题，如量子纠缠态对博弈结果的若A1ice选择混合策略q。,Bob选择混合策略q%,则 影响21，量子噪声对博奔的影响2s)等.量子博奔 Alice的收益可以表示为q.AqA 还为量子计算提供了良好的实现平台21，对量子计 A lice的占优策略q,是指对于Bob的任意策略 算机的研究起了巨大的推动作用 选择q.,Alice其他非q的策略选择获得的收益都 1预备知识 不会大于占优策略q的所得，即 11博弈论 qAqg≥qAqs,廿q,qb∈S 现对二人策略博弈进行定义：设有2个个体 类似地，可以定义Bob的占优策略， (p layer)Alice和Bob,且2个体有公共的备选策略 Nash均衡(Nash equilibrium),是指在博弈中其 集合f,,,s.当Alice选择策略s,Bob选择 他个体的策略给定时，任何个体都不能单方面改变 策略s时，Alicef的收益是a,一般地，设博弈是公平 自己的策略来增加自己收益的情形.即如果qAq≤ 的，即当Bob选择策略s,Alice:选择策略y时，Bob qAq,廿q∈S,则q∈S被称为Nash均衡.对于囚 的收益也是a:另一方面，设博弈个体是理性的，即 徒困境来说，双方互相背叛是一个Nash均衡.但如 个体总以达到自我利益最大化为目的.nX矩阵 果双方互相合作，则他们可以获得的收益之和最大 A=(a,称为收益矩阵(payoff matrix), 因此，在囚徒困境博弈中，对整体有利的策略并不是 一个经典的例子就是囚徒困境(prisoner'sdr 理性个体最终选择的策略.2个囚徒也因此陷入“为 lemma)博弈：2个嫌疑犯作案后被警察抓住，进行隔 大家考虑和为自己考虑的困境中 离审讯.警方的政策是坦白从宽，抗拒从严”策略 当博弈双方的策略组合是(q。,6时，如果增加 C表示与同伴合作，即对警察抵赖；策略D表示背 任一个体的收益就必须以降低另一个体的收益为代 叛同伴，即对警察坦白.如果2人互相合作即都对 价，则称(qa,s)是一个Paeo最优.在囚徒困境博 警察抵赖)，则因证据不足各判2年：如果一人合作 弈中，双方都合作是一个Paeo最优 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
家将这个“巫术 ”应用于博弈论时 ,发现它对于博弈 的描述要优于经典博弈. 这种优越性主要基于量子 化博弈扩大了原经典博弈的策略集以及纠缠态的引 入. 策略集的扩大使得寻找满足条件的策略更加容 易实现 ;而纠缠态的引入从一定程度修正了“个体 都是理性的 ”这一基本经典假设 ,互相纠缠的状态 成为博弈个体之间相互“关照 ”程度的度量 ,正如人 群中的亲友之间进行博弈时 ,会把对方的收益部分 当作自己收益一样 [ 24 ] . 事实上 ,博弈论作为研究理 性策略主体如何解决冲突的理论 ,本身就蕴含着经 典描述所无法满足的复杂性 ,如博弈个体的声誉 ,博 弈个体之间的网络结构等对博弈结果的影响 [ 24 ] . 而 在量子信息论框架下产生的量子博弈论 ,由于存在 量子态的相干叠加和纠缠 ,往往能够解决一些经典 博弈论所不能解决的难题 ,如经典的囚徒困境博弈 在量子博弈的框架下就能摆脱困境. 同时 ,量子力学 对现实世界的描述语言和相关概念 ,也为博弈论提 供了新的研究课题 ,如量子“纠缠态 ”对博弈结果的 影响 [ 25 ] ,量子噪声对博弈的影响 [ 26227 ]等. 量子博弈 还为量子计算提供了良好的实现平台 [ 28 ] ,对量子计 算机的研究起了巨大的推动作用. 1 预备知识 1. 1 博弈论 现对二人 n策略博弈进行定义 :设有 2个个体 (p layer) A lice和 Bob, 且 2个体有公共的备选策略 集合 { s1 , s2 , …, sn }. 当 A lice选择策略 si , Bob选择 策略 sj时 , A lice的收益是 aij . 一般地 ,设博弈是公平 的 ,即当 Bob选择策略 si , A lice选择策略 sj 时 , Bob 的收益也是 aij;另一方面 ,设博弈个体是理性的 ,即 个体总以达到自我利益最大化为目的. n ×n矩阵 A = ( aij )称为收益矩阵 (payoff matrix). 一个经典的例子就是囚徒困境 ( p risoner’s di2 lemma)博弈 : 2个嫌疑犯作案后被警察抓住 ,进行隔 离审讯. 警方的政策是“坦白从宽 ,抗拒从严 ”. 策略 C表示与同伴合作 ,即对警察抵赖;策略 D 表示背 叛同伴 ,即对警察坦白. 如果 2人互相合作 (即都对 警察抵赖 ) ,则因证据不足各判 2年;如果一人合作 另一人背叛 (即一人对警察抵赖 ,另一人坦白 ) ,合 作的判 5年 ,背叛的释放;如果双方都背叛 (即都对 警察坦白 ) ,则各判 4年. 这个博弈的收益矩阵为 C D C - 2 - 5 D 0 - 4 在大多数文献中 ,为了讨论方便 ,不失一般性 ,将收 益矩阵中的每一项加 5,使收益矩阵成为非负矩阵 : C D C 3 0 D 5 1 进一步地 ,称 { s1 , s2 , …, sn }为纯策略集 ,其中的 每个元素称为纯策略. 用 pi 表示个体使用纯策略 si 的概率 ,称 ( p1 , p2 , …, pn )为一个混合策略. 混合策 略集可以表示为 S = { p = (p1 , p2 , …, pn ) ∈R n : pi ≥0, ∑ n i =1 pi = 1}. 若 A lice选择混合策略 qa , Bob选择混合策略 qb ,则 A lice的收益可以表示为 qaAq T b . A lice的占优策略 qa ,是指对于 Bob的任意策略 选择 q′b , A lice其他非 qa 的策略选择获得的收益都 不会大于占优策略 qa 的所得 ,即 qaA q′ T b ≥ q′aA q′ T b , Π q′a , q′b ∈ S. 类似地 ,可以定义 Bob的占优策略. Nash均衡 (Nash equilibrium) ,是指在博弈中其 他个体的策略给定时 ,任何个体都不能单方面改变 自己的策略来增加自己收益的情形. 即如果 qAq T e ≤ qeA q T e , Π q∈S,则 qe ∈S 被称为 Nash均衡. 对于囚 徒困境来说 ,双方互相背叛是一个 Nash均衡. 但如 果双方互相合作 ,则他们可以获得的收益之和最大. 因此 ,在囚徒困境博弈中 ,对整体有利的策略并不是 理性个体最终选择的策略. 2个囚徒也因此陷入“为 大家考虑 ”和“为自己考虑 ”的困境中. 当博弈双方的策略组合是 ( qa , qb )时 ,如果增加 任一个体的收益就必须以降低另一个体的收益为代 价 ,则称 ( qa , qb )是一个 Pareto最优. 在囚徒困境博 弈中 ,双方都合作是一个 Pareto最优. 第 4期 王 龙 ,等 :量子博弈 :新方法与新策略 · 592 ·
·296· 智能系统学报 第3卷 12量子力学 量子力学的奇妙特性之一，是量子博弈优于经典博 121量子力学的基本假设 弈的一个重要原因 量子力学有2套相互等价的描述方法：状态空间 13量子信息论 法和密度算子法.这里的叙述采用密度算子法2) 比特是经典信息论的基本概念.类似地，量子信 假设1任意孤立的物理系统与称之为这个系 息和量子计算是建立在量子比特(quantum biti或qu 统的状态空间相关联，它是一个Hilbert?空间.系统 biV的基础上.经典比特有2个确定状态0和1，量子 由作用在状态空间上的密度算子完全描述，密度算 比特有2个可能状态0)和|1)，其中“|·）称为Di 子P是一个半正定、迹为1的线性算子.如果量子系 ac符号，在量子力学中表示状态这种用Dirac符号 统以概率p处于状态P,则系统的密度算子为 表示的方法就是上面提到的状态空间法人.一般地，量 ∑nP. 子比特的状态中)落在以10)和1)作为标准正交基 假设2封闭量子系统的演化由一个西变换来 所张成的复数域上的二维内积空间的单位球面上.即 描述，即系统在时刻4的状态P和在时刻5的状态 I中）=aI0〉+BI1),a,B∈C,aG+F=1事实上，1中) P由一个仅依赖于时间和飞的酉算子U联系， (仲就是一个密度算子，表示量子比特以概率1处于 P'=UPUT 状态中)，其中（仲表示中的对偶向量 式中：U表示U的伴随算子 经典计算机线路由连线和逻辑门构成，其中逻 假设3量子测量是由一组测量算子Mm描 辑门负责处理信息，把信息从一种形式转化为另一 述，这些算子作用在所测量的状态空间上，指标m 种形式.类似地，可以定义单量子比特门按照量子 指实验中可能出现的测量结果.如果量子系统在测 力学的假设2，单量子比特门作为状态之间变换的 量前的最后状态是P,则得到结果m的概率由 惟一限制是酉性，因此全体二维酉矩阵组成了所有 p(m)=tr(MM p) 的单量子比特门.如同经典比特门中有一些简单而 给出，其中r(·)是线性代数中的迹函数，且测量 重要的成员，如与非门、或非门，单量子比特门也有 后系统的状态为 “些重要的成员，它们可以作为一般单量子比特门 M.PMI 酉变换)分解的基本元素，如： tr(MIMP) 测量算子满足完备性方程： Hadamard门：H ∑MM。=1 「01 假设4复合物理系统的状态空间为各子物理 系统状态空间的张量积，如果有系统1到n其中系 auli-Y门：ox月，o 统i处于状态P,则复合物理系统的状态是P,回 P2⊙…⊙Pn 「1 01 此外，对于开放的物理系统，系统演化不再遵守 Paul-Z门：0z0 酉变换法则，但仍可用Kraus算子来描述系统的演 有了以上的准备知识，就可以二人双策略公平 化，即用一组满足完备性方程的算子来描述系统的 博弈为例来介绍量子博弈及其相关概念 演化 14量子博弈 122纠缠态 设S是一个单量子比特门的子集，Alice和Bob 如果一个复合物理系统的某个状态的密度矩阵 的策略都取自S类似于经典博弈，量子博弈中也有 不能表示成各个子系统的密度矩阵的张量积的线性 Nash均衡、A lice的占优策略和Pareto最优的概念. 和形式，则称这个复合系统处于纠缠态.量子纠缠是 这些概念与经典博弈中的直观意义是相同的，例如 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
1. 2 量子力学 1. 2. 1 量子力学的基本假设 量子力学有 2套相互等价的描述方法:状态空间 法和密度算子法. 这里的叙述采用密度算子法 [29 ] . 假设 1 任意孤立的物理系统与称之为这个系 统的状态空间相关联 ,它是一个 H ilbert空间. 系统 由作用在状态空间上的密度算子完全描述 ,密度算 子ρ是一个半正定、迹为 1的线性算子. 如果量子系 统以概率 pi 处于状态 ρi , 则系统的密度算子为 ∑i piρi . 假设 2 封闭量子系统的演化由一个酉变换来 描述 ,即系统在时刻 t1 的状态 ρ和在时刻 t2 的状态 ρ′由一个仅依赖于时间 t1 和 t2 的酉算子 U 联系 , ρ′= UρU , 式中 : U 表示 U 的伴随算子. 假设 3 量子测量是由一组测量算子 {Mm }描 述 ,这些算子作用在所测量的状态空间上 , 指标 m 指实验中可能出现的测量结果. 如果量子系统在测 量前的最后状态是 ρ,则得到结果 m 的概率由 p (m ) = tr(M mMmρ) 给出 ,其中 tr ( ·)是线性代数中的迹函数 ,且测量 后系统的状态为 MmρM m tr(M mMmρ) . 测量算子满足完备性方程 : ∑m M mMm = I. 假设 4 复合物理系统的状态空间为各子物理 系统状态空间的张量积 ,如果有系统 1到 n,其中系 统 i处于状态 ρi , 则复合物理系统的状态是 ρ1 á ρ2 á …á ρn . 此外 ,对于开放的物理系统 ,系统演化不再遵守 酉变换法则 ,但仍可用 Kraus算子来描述系统的演 化 ,即用一组满足完备性方程的算子来描述系统的 演化. 1. 2. 2 纠缠态 如果一个复合物理系统的某个状态的密度矩阵 不能表示成各个子系统的密度矩阵的张量积的线性 和形式 ,则称这个复合系统处于纠缠态. 量子纠缠是 量子力学的奇妙特性之一 ,是量子博弈优于经典博 弈的一个重要原因. 1. 3 量子信息论 比特是经典信息论的基本概念. 类似地,量子信 息和量子计算是建立在量子比特 ( quantum bit或 qu2 bit)的基础上. 经典比特有 2个确定状态 0和 1,量子 比特有 2个可能状态 |0〉和 | 1〉,其中“| ·〉”称为 D i2 rac符号 ,在量子力学中表示状态 (这种用 D irac符号 表示的方法就是上面提到的状态空间法 ). 一般地,量 子比特的状态 |ψ〉落在以 | 0〉和 | 1〉作为标准正交基 所张成的复数域上的二维内积空间的单位球面上. 即 |ψ〉=α|0〉+β|1〉,α,β∈C,αα +ββ = 1. 事实上, |ψ〉 〈ψ|就是一个密度算子,表示量子比特以概率 1处于 状态 |ψ〉,其中〈ψ|表示 |ψ〉的对偶向量. 经典计算机线路由连线和逻辑门构成 ,其中逻 辑门负责处理信息 ,把信息从一种形式转化为另一 种形式. 类似地 ,可以定义单量子比特门. 按照量子 力学的假设 2,单量子比特门作为状态之间变换的 惟一限制是酉性 ,因此全体二维酉矩阵组成了所有 的单量子比特门. 如同经典比特门中有一些简单而 重要的成员 ,如与非门、或非门 ,单量子比特门也有 一些重要的成员 ,它们可以作为一般单量子比特门 (酉变换 )分解的基本元素 ,如 : Hadamard门 : H = 1 2 1 1 1 - 1 , Pauli—X 门 :σX = 0 1 1 0 , Pauli—Y门 :σY = 0 - i i 0 , Pauli—Z 门 :σZ = 1 0 0 - 1 . 有了以上的准备知识 ,就可以二人双策略公平 博弈为例来介绍量子博弈及其相关概念. 1. 4 量子博弈 设 S是一个单量子比特门的子集 , A lice和 Bob 的策略都取自 S. 类似于经典博弈 ,量子博弈中也有 Nash均衡、A lice的占优策略和 Pareto最优的概念. 这些概念与经典博弈中的直观意义是相同的 ,例如 · 692 · 智 能 系 统 学 报 第 3卷
第4期 王龙等：量子博弈：新方法与新策略 ·297 ∈S称为A licef的占优策略，是指对于任意Bob的 为P。=I0〉(01经玩家Q作用之后的密度算子为 策略选择sg,A lice其他非的策略选择获得的收 P,=UPU,其中U是酉算子U的共轭转置，并且 益都不大于占优策略的所得，即：P4(s,s)≥ 满足UU=1玩家P作用之后，硬币的密度算子为 P(s,),s,∈S P2=pFP,Ft+(1-pNPN最后，硬币的密度算 廿s4,sB∈S,如果 子为P=UP2U=P.因此，不管玩家P以多大概 P4(s,)≥P4(,) 率翻硬币，使用策略U的玩家Q会以概率1赢， Pa(,)≥Pa(M,sB) 事实上，经典博弈论中的策略是量子策略的一 则量子策略(s,)∈SS称为一个Nash均衡，其 个子集0)，因此，量子策略相对于经典策略具有一 中P4(s,,Pa(,)分别表示Alice选用，Bob 定的优越性 选用s时，A lice和Bob的收益 22 Eisert量子博弈 2量子博弈的主要模型 Eisert量子博弈P是把量子力学的概念引入经 典的囚徒困境而产生的一个全新的博弈模型.在经 21量子翻硬币博弈 典的囚徒困境博弈中，理性假设必然导致策略主体 最简单的赌博形式就是翻硬币.在量子翻硬币 双方都选择不合作，从而互相背叛成为一个Nash均 博弈中B,假设有2个玩家P和Q,其中P使用的 衡.对任何理性博弈者来说，背叛就是最优选择.但 是经典策略，即翻硬币和不翻硬币，而Q使用量子 是如果双方都选择背叛，2个人的收益和比双方都 策略.游戏规则如下：首先由P准备一枚硬币，硬币 合作的收益和要小.这个困境深刻地反映了个人理 正面是头像，反面是字.P把这枚硬币放到一个盒子 性和集体理性之间的矛盾.在量子博弈意义下，囚徒 里，确保硬币头像一面向上，然后把盒子盖上(P和 困境有了一个新的Nash均衡.如果博弈双方都采用 Q只能把手伸到盒子里进行操作，但看不到盒子里 量子策略，那么他们可以逃出以上困境 硬币的状态人.接下来由Q进行操作，然后是P操 Eisert量子博弈模型包括以下3点： 作，最后Q再进行一次操作之后，把盒子打开.如果 1)2个量子比特的源，每个个体的状态对应一 硬币的头像一面仍然向上的话Q赢，否则P赢 个比特： 定义一个二维向量空间来表示硬币的状态，这 2)一个物理工具集对应于经典博弈的策略 个空间的2个基为10)和11).状态10)，1)分别表 集)，这些工具可以使策略主体在策略意义下控制 示以概率1硬币头像面向上，以概率1硬币头像面 自己的比特； 向下.定义二维矩阵来表示玩家的策略.对于玩家 3)一个物理测量设备，这个设备可以通过这2 P,经典策略翻F)和不翻N)分别表示为 个比特的状态来确定策略主体的收益 01 「10 F N 假设每个策略主体都知道以上3点要素.定义 L 1 0 比特|C)和D)表示经典策略C和D的状态.在静 玩家P以概率p使用策略F,以概率1-p使用 态博弈中，每个策略主体只进行一次动作卿使用 策略N,则P的混合策略可用矩阵表示为 一次策略人.那么这个博弈的初始策略组合可以写 1-p 成ICC)、ICD)、IDC)、IDD). 1- Eisert量子博弈的过程如图1所示.首先，令2 而玩家Q使用的量子策略为Hadamard算子： 个策略主体的策略都是|C〉，即该博弈的状态为 1CC).通过量子门使得状态ICC)纠缠在一起形成 初始状态1中。)=jCC),即2个策略主体的初始状 使用密度算子法21，定义硬币初始的密度算子 态通过量子信息的通道对对方的决策产生影响，形 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
sA ∈S称为 A lice的占优策略 ,是指对于任意 Bob的 策略选择 s′B , A lice其他非 sA 的策略选择获得的收 益都不大于占优策略的所得 , 即 : PA ( sA , s′B ) ≥ PA (sA′, sB′) , Π sA′, sB′∈S. Π s′A , s′B ∈S,如果 PA (sA , sB ) ≥ PA (sA′, sB ) , PB (sA , sB ) ≥ PB (sA , s′B ). 则量子策略 (sA , sB ) ∈S ×S称为一个 Nash均衡 ,其 中 PA (sA , sB ) , PB (sA , sB )分别表示 A lice选用 sA , Bob 选用 sB 时 , A lice和 Bob的收益. 2 量子博弈的主要模型 2. 1 量子翻硬币博弈 最简单的赌博形式就是翻硬币. 在量子翻硬币 博弈中 [ 3 ] ,假设有 2个玩家 P和 Q,其中 P使用的 是经典策略 ,即翻硬币和不翻硬币 ,而 Q 使用量子 策略. 游戏规则如下 :首先由 P准备一枚硬币 ,硬币 正面是头像 ,反面是字. P把这枚硬币放到一个盒子 里 ,确保硬币头像一面向上 ,然后把盒子盖上 ( P和 Q只能把手伸到盒子里进行操作 ,但看不到盒子里 硬币的状态 ). 接下来由 Q 进行操作 ,然后是 P操 作 ,最后 Q再进行一次操作之后 ,把盒子打开. 如果 硬币的头像一面仍然向上的话 Q赢 ,否则 P赢. 定义一个二维向量空间来表示硬币的状态 ,这 个空间的 2个基为 | 0〉和 | 1〉. 状态 | 0〉, | 1〉分别表 示以概率 1硬币头像面向上 ,以概率 1硬币头像面 向下. 定义二维矩阵来表示玩家的策略. 对于玩家 P,经典策略翻 ( F )和不翻 (N )分别表示为 F: 0 1 1 0 N : 1 0 0 1 玩家 P以概率 p使用策略 F,以概率 1 - p使用 策略 N ,则 P的混合策略可用矩阵表示为 1 - p p p 1 - p . 而玩家 Q使用的量子策略为 Hadamard算子 : U : 1 2 1 1 1 - 1 . 使用密度算子法 [ 29 ] ,定义硬币初始的密度算子 为 ρ0 = | 0〉〈0 |. 经玩家 Q 作用之后的密度算子为 ρ1 =Uρ0U ,其中 U 是酉算子 U 的共轭转置 ,并且 满足 UU = I. 玩家 P作用之后 ,硬币的密度算子为 ρ2 = pFρ1 F + ( 1 - p) Nρ1N . 最后 ,硬币的密度算 子为 ρ3 = Uρ2U =ρ0 . 因此 ,不管玩家 P以多大概 率翻硬币 ,使用策略 U 的玩家 Q会以概率 1赢. 事实上 ,经典博弈论中的策略是量子策略的一 个子集 [ 30 ] ,因此 ,量子策略相对于经典策略具有一 定的优越性. 2. 2 Eisert量子博弈 Eisert量子博弈 [ 2 ]是把量子力学的概念引入经 典的囚徒困境而产生的一个全新的博弈模型. 在经 典的囚徒困境博弈中 ,理性假设必然导致策略主体 双方都选择不合作 ,从而互相背叛成为一个 Nash均 衡. 对任何理性博弈者来说 ,背叛就是最优选择. 但 是如果双方都选择背叛 , 2个人的收益和比双方都 合作的收益和要小. 这个困境深刻地反映了个人理 性和集体理性之间的矛盾. 在量子博弈意义下 ,囚徒 困境有了一个新的 Nash均衡. 如果博弈双方都采用 量子策略 ,那么他们可以逃出以上困境. Eisert [ 2 ]量子博弈模型包括以下 3点 : 1) 2个量子比特的源 ,每个个体的状态对应一 个比特; 2) 一个物理工具集 (对应于经典博弈的策略 集 ) ,这些工具可以使策略主体在策略意义下控制 自己的比特; 3) 一个物理测量设备 ,这个设备可以通过这 2 个比特的状态来确定策略主体的收益. 假设每个策略主体都知道以上 3点要素. 定义 比特 |C〉和 |D 〉表示经典策略 C和 D 的状态. 在静 态博弈中 ,每个策略主体只进行一次动作 (即使用 一次策略 ). 那么这个博弈的初始策略组合可以写 成 |CC〉、|CD 〉、|DC〉、|DD 〉. Eisert量子博弈的过程如图 1所示. 首先 ,令 2 个策略主体的策略都是 | C 〉, 即该博弈的状态为 |CC〉. 通过量子门 J ^使得状态 |CC〉纠缠在一起形成 初始状态 |ψ0 〉= J ^ |CC〉,即 2个策略主体的初始状 态通过量子信息的通道对对方的决策产生影响 ,形 第 4期 王 龙 ,等 :量子博弈 :新方法与新策略 · 792 ·
·298· 智能系统学报 第3卷 成被影响后的纠缠状态.2个策略主体A和B的策 3)策略空间为一般的酉矩阵.在这种情况下， 略分别为酉算子，和心.当A和B进行一次博奔 对于任意给定的收益不大于Paeo最优时的收 之后，状态成为心，⊙心。1cc),然后通过量子门 益)，策略主体可以通过调整各自的量子策略达到 来解纠缠，得到最终状态： 一个Nash均衡，使得在这个Nash均衡下，2个策略 1中，》=⊙心ncc以】 主体的收益都为预先给定的收益 上述讨论只考虑了策略酉矩阵对收益的影响， 并没有考虑初始状态的纠缠所产生的影响.考虑初 始策略组合|CC经过酉算子纠缠在一起形成纠缠 态Ψ。〉=UCC的情形B1.定义的形式为 图1Eit量子博弈模型 f=exp(i D⊙D2,Y∈I0,r2] Fig I Eisert model of quantm game 式中：Y是该量子博弈中状态纠缠程度的度量.若 使用经典囚徒困境的收益矩阵 可以定 Y=0,说明该博弈中的2个策略主体没有纠缠，进行 博弈时完全不受对方的影响.这种情况下的量子博 义策略主体A的期望收益为 弈等价于使用混合策略的经典博弈.若Y≠0此时 =Pcc pPDD Ppc sPcD 的2个策略主体都不是完全理性，或者不是自私的 式中：P。'=|(ooI中，〉，它表示最终状态是1o0) 主体，他们在选择策略时还会考虑对方的因素，所以 的概率.策略空间为不同的形式时，可以得到不同的 博弈结果B 就会出现纠缠的现象， 1)策略空间为具有一个参数的2阶酉矩阵： 纠缠程度也是影响量子博弈的一个重要因素， cos(0/2) sin( 3 以收益矩阵为 的囚徒困境为例： -sin(02)cos02力 5 式中：0∈0，π1在这种情况下，互相背叛仍然是惟 1)当0≤y≤arcsin1/5时，D⊙D,即双方背 一的Nash均衡，但不是Pareto最优.即在这种最优 叛，仍是惟一的Nash均衡； 策略组合下，任何一个策略主体都不能以减少对方 2)当arcsin1/5<Y<arcsin2/5时，D⊙Q和 收益为代价来增加自己的收益.此时，量子博弈和经 典博弈没有区别； Q⊙D都是Nash均衡.此时Q仍然为UO,π2) 2)策略空间为具有2个参数的2阶西矩阵 3)当arcsin2/5≤Y≤r2时，Q⊙Q是惟一的 心，) e cos(02) sin(0/2) Nash均衡，并且是Paeo最优.此时囚徒困境被解决 sin(0/2) ecos(02 23其他量子博弈模型 式中：0∈0，π1，φ∈[0，π/21 量子翻硬币博弈和Eisert量子博弈是两类非常 在这种情况下，存在一个量子策略 重要的量子博弈模型.基于这2种基本模型，其他一 Q=00,r2) 0 些博弈的量子模型相继产生.例如，性别之战(battle L0. of sexes game)模型s1,猎鹿博弈(stag hunt game) 使得均衡Q,Q)是一个新的Nash均衡，并且是 模型、少数者博奔(m inority gae)模型m】、伪 一个Paeo最优.因此，困境在量子策略下消失了； 感应(pseudo telepathy game)模型I39-o1、Monty Hall 特别地，当策略集被限制在心（红，0），心(0， 博弈模型【12以及其他博奔模型3).其中量子 Monty Hallt博弈模型是比较典型的量子博弈模型 0)时，量子博奔还原为经典博弈，且（红，0） 所谓Monty Hall问题，就是在一个名为Monty 心0,0)分别表示背叛与合作，记为D和C 的大厅中，主人Alice和客人Bob进行一次博弈.主 1994-2008 China Academie Journal Electronic Publishing House.All rights reserved.http://www.cnki.ne
成被影响后的纠缠状态. 2个策略主体 A 和 B 的策 略分别为酉算子 U ^ A 和 U ^ B . 当 A 和 B 进行一次博弈 之后 ,状态成为 U ^ A á U ^ B J ^ | CC〉,然后通过量子门 J ^ 来解纠缠 ,得到最终状态 : |ψf 〉= J ^ U ^ A á U ^ B J ^ | CC〉. 图 1 Eisert量子博弈模型 Fig. 1 Eisert model of quantum game 使用经典囚徒困境的收益矩阵 r s t p ,可以定 义策略主体 A的期望收益为 ＄A = rPCC + pPDD + tPD C + sPCD , 式中 : Pσσ′= 〈| σσ′|ψf 〉| 2 ,它表示最终状态是 |σσ′〉 的概率. 策略空间为不同的形式时 ,可以得到不同的 博弈结果 [ 31 ] . 1)策略空间为具有一个参数的 2阶酉矩阵 : U ^ (θ) = co s(θ/2) sin (θ/2) - sin (θ/2) cos(θ/2) , 式中 :θ∈[ 0,π]. 在这种情况下 ,互相背叛仍然是惟 一的 Nash均衡 ,但不是 Pareto最优. 即在这种最优 策略组合下 ,任何一个策略主体都不能以减少对方 收益为代价来增加自己的收益. 此时 ,量子博弈和经 典博弈没有区别; 2)策略空间为具有 2个参数的 2阶酉矩阵 U ^ (θ, <) = e i< cos(θ/2) sin (θ/2) - sin (θ/2) e - i< cos(θ/2) , 式中 :θ∈[ 0,π], <∈[ 0,π/2 ]. 在这种情况下 ,存在一个量子策略 : Q ^ = U ^ (0,π/2) = i 0 0 - i , 使得均衡 (Q ^ , Q ^ )是一个新的 Nash均衡 ,并且是 一个 Pareto最优. 因此,困境在量子策略下消失了; 特别地 , 当策略集被限制在 { U ^ (π, 0 ) , U ^ ( 0, 0) }时 , 量子博弈还原为经典博弈 , 且 U ^ (π, 0 ) , U ^ (0, 0)分别表示背叛与合作 ,记为D ^和 C ^ . 3)策略空间为一般的酉矩阵. 在这种情况下 , 对于任意给定的收益 (不大于 Pareto最优时的收 益 ) ,策略主体可以通过调整各自的量子策略达到 一个 Nash均衡 ,使得在这个 Nash均衡下 , 2个策略 主体的收益都为预先给定的收益. 上述讨论只考虑了策略酉矩阵对收益的影响 , 并没有考虑初始状态的纠缠所产生的影响. 考虑初 始策略组合 |CC〉经过酉算子 J ^纠缠在一起形成纠缠 态 |Ψ0 〉=U ^ |CC〉的情形 [ 2, 28 ] . 定义 J ^的形式为 J ^ = exp{ γi D ^ á D ^ /2},γ∈ [ 0,π/2 ], 式中 :γ是该量子博弈中状态纠缠程度的度量. 若 γ= 0,说明该博弈中的 2个策略主体没有纠缠 ,进行 博弈时完全不受对方的影响. 这种情况下的量子博 弈等价于使用混合策略的经典博弈. 若 γ≠0,此时 的 2个策略主体都不是完全理性 ,或者不是自私的 主体 ,他们在选择策略时还会考虑对方的因素 ,所以 就会出现纠缠的现象. 纠缠程度也是影响量子博弈的一个重要因素. 以收益矩阵为 3 0 5 1 的囚徒困境为例 : 1)当 0≤γ≤arcsin 1 /5时 , D ^ á D ^ ,即双方背 叛 ,仍是惟一的 Nash均衡 ; 2)当 arcsin 1 /5 <γ < arcsin 2 /5时, D ^ á Q ^和 Q ^ á D ^都是 Nash均衡. 此时Q ^仍然为U ^ (0,π/2); 3)当 arcsin 2 /5≤γ≤π/2时, Q ^ á Q ^是惟一的 Nash均衡,并且是 Pareto最优.此时囚徒困境被解决. 2. 3 其他量子博弈模型 量子翻硬币博弈和 Eisert量子博弈是两类非常 重要的量子博弈模型. 基于这 2种基本模型 ,其他一 些博弈的量子模型相继产生. 例如 ,性别之战 ( battle of sexes game)模型 [ 32235 ]、猎鹿博弈 ( stag hunt game) 模型 [ 36 ]、少数者博弈 (m inority game)模型 [ 37238 ]、伪 感应 ( p seudo telepathy game)模型 [ 39240 ]、Monty Hall 博弈模型 [ 41242 ]以及其他博弈模型 [ 43259 ] . 其中量子 Monty Hall博弈模型是比较典型的量子博弈模型. 所谓 Monty Hall问题 ,就是在一个名为 Monty 的大厅中 ,主人 A lice和客人 Bob进行一次博弈. 主 · 892 · 智 能 系 统 学 报 第 3卷