（计算机应用技术专业论文）基于博弈论的秘密共享理论及应用研究.pdf

山东大学硕士学位论文 摘要 随着信息技术的发展以及计算机和通信系统的普及，人们对网络的依赖程度 越来越高，如网上银行、电子拍卖、电子招标和电子现金交易等。因此，对如何 保证信息在产生和传输过程中的安全性也受到了越来越多的关注，并成为了现代 密码学的重要研究领域。现代密码体制的设计和研究都是在k e r c k h o f f 假设前提 下进行的，在这样的假设前提下密码算法的安全性完全依赖于密钥的安全性，所 以，对密钥的管理或共享控制问题在密码体制的安全性研究和设计中占有十分重 要的地位。 秘密共享是在一组参与者中共享秘密的技术i 它主要是用于保护重要的信 息，以防止信息的丢失，被破坏，被篡改。秘密共享是密钥分配的基础，秘密共 享是密码学研究的一个重要方向和内容。秘密共享也是密码学中的一个重要工 具，是保护信息和数据的重要手段，在信息安全中起着重要的作用。典型的秘密 共享方案有：传统秘密共享、可验证秘密共享、多重秘密共享。 本文主要研究理性参与者秘密共享方案的构造和应用。本文对以往秘密共享 理论进行了较为深入的研究和分析，结合博弈论模型，给出理性秘密共享的概念， 并提出一个新的理性秘密共享方案，在应用方面，设计了一个基于特殊权限的理 性秘密共享方案，并给出了其正确性证明，分析了其应用性。 首先，本文详细介绍了博弈论的概念、典型方案及发展状况，阐述了纳什均 衡的定义以及混合策略下的纳什均衡，讨论了纳什均衡的存在性和多重性问题。 给出了秘密共享的研究综述，研究分析了典型的秘密共享方案。 其次，本文给出了一个新的理性秘密共享方案。以往秘密共享中的参与者是 “诚实的一或者“恶意的，在博弈论模型中的参与者均是理性的，也就是自私 的，为了构建更趋近于现实的交互式模型，我们将这两种模型结合起来。我们对 h t 2 0 0 4 理性秘密共享方案进行了分析，该方案是在( 3 ，3 ) 理性秘密共享方案 的基础上进行推广到多个理性参与者的秘密共享，并证明只有两个理性参与者无 法成功恢复秘密。我们在此基础上给出了理性秘密共享的定义，分析了只有两个 理性参与者秘密共享的可行性，并构造出一个新的理性秘密共享方案。该方案解 决了只有两个理性参与者的秘密共享问题，我们并将其推广到多个理性参与者的 山东大学硕士学位论文 秘密共享，且给出了正确性证明。 最后，我们在对基于特殊权限的秘密共享方案深入研究的基础上，提出了一 个与现实模型更为相近的基于特殊权限的理性秘密共享方案。以往的秘密共享只 能满足最普通的需要，如果参与成员中有一些身份特殊者，不同身份的人掌握的 秘密多少不同，或者说，参与者的访问权限不同，那么需要修改原有方案使其满 足这些特殊需要。我们在研究分析了李滨的基于特殊权限的秘密共享后，结合理 性秘密共享方案，提出了一个新的基于特殊权限的理性秘密共享方案，该方案的 参与者访问权限不同，且均是理性参与者。对方案的正确性我们予以证明，且对 方案的应用性进行了探讨，并给出一些应用领域。 关键词：密码学；博弈论；纳什均衡；秘密共享：较差策略集；特殊权限； 理性参与者 山东大学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ei n f o r m a t i o nt e c h n o l o g ya n dt h ep o l u l a r i z a t i o no f c o m p u t e ra p p l i c a t i o n s ，t h eh u m a ns o c i e t y 。sr e l i a n c eo nt h en e t w o r kg r a d u a l l y i n c r e a s e d , s u c ha st h ei n t e m e tb a n k i n g 、e - a u c t i o n 、e - b i d d i n ga n dt h et r a n s a c t i o no f e c a s h t h e r e f o r e ，h o wt oe n s l l r et h a ti n f o r m a t i o ni nt h eg e n e r a t i o na n dt r a n s m i s s i o n i nt h ep r o c e s so fs e c u r i t yh a sb e e nm o r ea n dm o r ea t t e n t i o na n db e c o m eam o d e m c r y p t o g r a p h yi m p o r t a n tr e s e a r c hr i d & c r y p t o s y s t e ms c h e m ei sc o m p r i s e do f a l g o r i t h ma n dk e y a c c o r d i n gt ok e r c k h o f fp r i n c i p l e ，t h ea l g o r i t h mi sp u b l i s h e dt o p u b l i c s ot h es e c u r i t yo fc r y p t o s y s t e ms c h e m ef h l l yd e p e n d so nt h es e c u r i t yo ft h e k e y t h e r e f o r e ，t h er e s e a r c ho fk e ym a n a g e m e n ta n ds e c r e ts h a r i n go c c u p i e sav e r y i m p o r t a n tp o s i t i o na tc r y p t o s y s t e ms e c u r i t yr e s e a r c ha n dd e s i g n s e c r e ts h a r i n gi sat e c h n o l o g yo fs h a r i n gs e c r e ta m o n gag r o u po fp a r t i c i p a n t s t h e i rm a jo rf u n c t i o ni st o p r o t e c ti m p o r t a n t i n f o r m a t i o nf r o mm i s s i n g , b e i n g d e s t r o y e da n db e i n gc h a n g e d t h e r e f o r e ，s e c r e ts h a r i n gi sa ni m p o r t a n tr e s e a r c hf i e l d a n da ne f f e c t i v et o o li nc r y p t o p h y t i ct h e o r y s e c r e ts h a r i n gp l a y sa ni m p o r t a n tr o l ei n i n f o r m a t i o ns e c u r i t y t y p i c a ls e c r e ts h a r i n gs c h e m eh a s ：t r a d i t i o n a ls e c r e ts h a r i n g ， v e r i f i a b l es e c r e ts h a r i n g ，m u l t i s e c r e ts h 撕i 玛 i nt h i sp a p e rw em 缸山s t u d yr a t i o n a ls e c r e ts h a r i n gs c h e m ep a r t i c i p a n t si nt h e c o n s t r u c t i o na n da p p l i c a t i o n i l lt h i sp a p e r , t h ep r e v i o u st h e o r yo fs e c r e ts h 撕n gm o r e i nd e p t hr e s e a r c ha n da n a l y s i s ，c o m b i n e dw i t ht h eg a m et h e o r ym o d e l ，g i v et h e c o n c e p to fr a t i o n a ls e c r e ts h a r i n ga n dp r o p o s e an e wr a t i o n a ls e c r e ts h a r i n gs c h e m e ，i n t h ea p p l i c a t i o n s ，w ed e s i g nar a t i o n a ls e c r e ts h a r i n gs c h e m eb a s e do ns p e c i a la c c e s s r i g h t ，a n dg i v ep r o o fo fi t sc o r r e c t n e s s ，a n a l y z ei t sa p p l i c a t i o n f i r s to fa l l ，t h i sp a p e ri n t r o d u c e si nd e t a i lt h ec o n c e p to fg a m et h e o r y , t h et y p i c a l p r o g r a ma n dd e v e l o p m e n t ，e x p l a i n e dt h ed e f i n i t i o no fn a s he q u i l i b r i u ma n d t h e m i x e ds t r a t e g yn a s he q u i l i b r i u m , w ed i s c u s st h ee x i s t e n c ea n dm u l t i p l i c i t yo fn a s h e q u i l i b r i u m w ea l s os t u d yt h ea n a l y s i so fat y p i c a ls e c r e ts h a r i n gs c h e m e i i i 山东大学硕士学位论文 s e c o n d l y , t h i sp a p e rg i v e san e w r a t i o n a ls e c r e ts h a r i n gs c h e m e s e c r e ts h a r i n gi n t h ep a s t , p a r t i c i p a n t sa r e h o n e s t ”o r ”m a l i c i o u s ”，b u ti nt h eg a m et h e o r ym o d e lo ft h e p a r t i c i p a n t sa r er a t i o n a l ，w h i c hi ss e l f i s h i no r d e rt ob u i l dar e a l i t yi n t e r a c t i v em o d e l ， w ec o m b i n et h e s et w om o d e l s w ea n a l y z et h eh t 2 0 0 4r a t i o n a ls e c r e ts h a r i n gs c h e m e ， t h i ss c h e m ei sa ( 3 ，3 ) r a t i o n a ls e c r e ts h a r i n gs c h e m e ，a n dt h e ye x t e n d e di tt oan u m b e r o fr a t i o n a lp a r t i c i p a n t si nt h es e c r e ts h a r i n g ，a n dt h e ys h o wt h a tt h et w op a r t i c i p a n t s r a t i o n a ls e c r e ts h a r i n gc a nn o tb es u c c e s s f u l l yr e s u m e d w eg i v ear a t i o n a ld e f i n i t i o n o fs e c r e ts h a r i n g ，a n a l y s i so ft h eo n l yt w or a t i o n a ls e c r e ts h a r i n gp a r t i c i p a n t si nt h e f e a s i b i l i t yo f , a n dc o n s t r u c tan e w r a t i o n a ls e c r e ts h a r i n gs c h e m e t h es o l u t i o nt ot h e o n l yt w op a r t i c i p a n t si nar a t i o n a ls e c r e ts h a r i n gp r o b l e m _ , w ew i l le x t e n di tt om o r e t h a nr a t i o n a ls e c r e ts h a r i n gp a r t i c i p a n t s ，a n dg i v eac o r r e c t n e s sp r o o f f i n a l l y , w eh a v es p e c i a lp r i v i l e g e sb a s e do ns e c r e ts h a r i n gs c h e m ei n - d e p t hs t u d y o nt h eb a s i so fam o d e la n dr e a l i t yi sm o r es i m i l a rt os p e c i a lp r i v i l e g e sb a s e do i l r a t i o n a ls e c r e ts h a r i n gs c h e m e i nt h ep a s t ，s e c r e ts h a r i n gc a no i l l ys a t i s f ys o m en e e d s ， i ft h ep a r t i c i p a t i o no ft h em e m b e r sh a v es o m es p e c i a li d e n t i t y , t h ei d e n t i t yo fd i f f e r e n t p e o p l eh a v ed i f f e r e n ts e c r e t ，o ra c c e s st od i f f e r e n tp a r t i c i p a n t s ，t h e nt h en e e d t o m o d i f yt h eo r i g i n a lp r o g r a ms ot h a ti t st om e e tt h e s es p e c i a ln e e d s w ea n a l y z e si nt h e s t u d y , l ib i n ，s p e c i a lp r i v i l e g e sb a s e d 0 ns e c r e ts h a r i n g ，t h ec o m b i n a t i o no fr a t i o n a l s e c r e ts h a r i n gs c h e m e ，p r o p o s e dan e w s p e c i a lp r i v i l e g e sb a s e do nr a t i o n a ls e c r e t s h a r i n gs c h e m e ，t h ep r o g r a mp a r t i c i p a n t sa c c e s st od i f f e r e n t , a n da r ep a r t i c i p a n t sa r e r a t i o n a l t h ec o r r e c t n e s so f t h ep r o g r a mw eh a v ep r o v e d , a n dt h ea p p l i c a t i o no f t h e p r o g r a ma r ed i s c u s s e d ，a n dw ea l s og i v es o m ea p p l i c a t i o n s k e y w o r d s ：c r y p t o l o g y ；g a m et h e o r y ；n a s he q u i l i b r i u m ；s e c r e ts h a r i n g ； w e a k l yd o m i n a t e ds t r a t e g i e s ；s p e c i a la c c e s sr i g h t ；r a t i o n a l p l a y e r ； i v 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：差辛 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：盟导师签 山东大学硕士学位论文 皇曼曼曼曼皇曼曼量曼量量量曼曼曼量曼曼曼曼皇量鼍曼詈曼曼鼍曼曼曼量曼曼曼曼皇曼量曼曼曼曼曼量鼍曼曼曼舅曼皇量曼量葛ij l i 皇量鼍量量曼 1 1 研究背景 第1 章引言 信息科学和技术的发展以及计算机和通信系统的普及，带动了社会和个人对 于数字信息保护及各种安全服务的需求。信息化发展的程度越高，信息安全所面 临的风险和挑战也就越大。对于主要以电子形式存储和传输信息的现代社会来 说，需要某种手段，以确保信息的安全性独立于记录和传输的物理介质。信息安 全的目标是只依靠数字信息本身来实现认证和机密性等安全性需求。在当前电子 社会，要做到信息安全，仅仅依靠物理载体或者法律上的保障是远远不够的，信 息安全对于消息的机密性、数据完整性、认证和不可抵赖性等提出了越来越高的 要求。 密码学的研究为人们提供了实现信息安全的关键技术。它有着悠久而奇妙的 历史，从大约4 0 0 0 年前埃及人对密码的原始的、有限的使用，到2 0 世纪两次世 界大战中它所扮演的重要角色，再到1 9 7 6 年公钥密码学概念的提出。随着各种 先进科学技术的引入和应用，密码学逐渐发展成为一种综合性的科学技术，它和 数学、计算机科学、电子学和信息论等学科有着广泛而密切的联系。现代密码学 的研究领域涉及流密码、分组密码、公钥密码、数字签名、散列函数、认证协议 及密钥管理等方面；密码学的应用也从最初的保护国家机密及决策的工具，扩展 到电子投票、电子现金、网上拍卖、网上购物和付费电视等商业和日常生活领域。 古典密码系统的安全性依赖于算法的保密，但是在1 8 8 3 年荷兰人a u g u s t e k e r c k h o f f 就对密码系统做了如下假设：一个密码系统的安全性必须仅依赖于密 钥，即在一个密码系统中，除密钥外，其余的算法( 包括加解密) 均应假设为破译 者完全知道。因为，如果密码体制的安全性基于算法的保密，则大量的、经常变 换的用户群是无法使用它的。例如，一个用户离去，其它用户就得改变算法，而 实现一个算法的成本是很高的。所以，现代密码体制的设计是使得密码体制的安 全性取决于密钥，而密码算法是公开的。密钥起着控制算法的参数的作用，密钥 的改变就容易多了。进而，可选择的密钥空间或者说密钥量是很大的，可达到天 文数字。算法公开后，在很大的密钥空间中随机选择一个密钥( 即参数值) 来控 山东大学硕士学位论文 制算法是保证安全性的有效办法。当然，这里边还有密钥的选取、传输等一系列 问题。在实际中虽然有些算法是不公开的，但是其安全性必须在算法公开的条件 下来论证。因此，密钥的泄露意味着体制失去了安全性。于是产生了如何生成、 存储、发放和传输密钥等问题，即密钥的管理或共享控制问题。显然，它在密码 体制的安全性研究和设计中占有十分重要的地位。 针对上述问题，b l a l d e y 和s h a m i r 于1 9 7 9 年独立地提出了秘密共享( s e c r e t s h a r i n g ) 的概念，并分别设计了具体的实现体制，他们提出的两种门限方案是比 较简单的门限方案，只能满足最普通的需要。从此以后，秘密共享的研究受到的 广泛的关注，并取得了一系列的成果。为了满足应用的多样性，根据参与成员访 问权限的不同，提出了基于特殊权限的秘密共享方案，这种方案在银行业中有着 很大的应用价值。 博弈论模型和密码协议设计都是针对一组相互不信任的参与者直接的交互 进行研究，以往，它们研究机构不同，感兴趣的方向也不相同，从而发展成为两 个独立的学科。近年来，为了构建更为趋近于现实的交互模型，这两门学科的融 合越来越多。针对这方面的研究可以分为两类：应用密码协议去解决博弈理论问 题和应用博弈论模型定义去构建新的密码协议。在博弈论模型中当存在仲裁人时 才能获得确定的博弈论均衡，第一类的研究主要就是利用密码协议去模拟仲裁人 的行为，从而将仲裁人去掉，对这方面的研究可以参考【4 3 5 0 】。我们研究的重点 为第二类，也就是应用博弈论模型定义去构建新的密码协议。在传统的秘密学模 型中，参与者有诚实的参与者( 按照协议执行) ，与其相对的还有恶意的参与者 ( 其行为是任意的不按照协议执行) 。在博弈论中考虑的参与者均是自私的( 理 性的) ，从而引出：如何在这样的设置下设计协议以及参与者的变换对原有协议 的影响。【3 0 1 这篇论文考虑了当所有参与者都是理性的情况，并给出了一个可行 的理性秘密共享协议。 1 2本文的工作 本文对博弈论与密码学结合的最新研究进展进行了关注，介绍了博弈论的概 念，并给出典型博弈模型，对秘密共享方案的理论和应用进行了深入而广泛的研 究，并与博弈论模型进行结合，提出了一个理性秘密共享方案和一个基于特殊权 限的理性秘密共享方案。 2 山东大学硕士学位论文 | 曼皇曼曼i 一一一 - - i_i i 曼量皇鼍皇鲁量鼍皇曼量曼曼曼量曼曼曼曼曼 本文的主要工作及创新之处： 一、本文首先对博弈论模型进行了深入的研究，给出了博弈论的基本概念和 发展状况，对纳什均衡的定义以及混合策略下的纳什均衡问题进行了研究，并讨 论了纳什均衡的存在性、多重性问题。对秘密共享从理论和应用两个方面进行了 广泛研究，并分析了理性秘密共享方案的最新研究进展和典型成果，以及下一步 研究需要解决的问题和在应用方面的展望。 二、本文提出了一个新的理性秘密共享方案，相比以前的秘密共享方案，该 方案具有以下特点： 1 、参与者均是理性参与者，与现实模型更为相似，实用性更强。 2 、在f i t 方案p 0 1 的基础上构造了一个只有两个理性参与者的秘密共享协议， 并推广为多个理性参与者的秘密共享方案，方案更为简单，成功的解决 了两个参与者的理性秘密共享问题。并在此方案的基础上给出了多个理 性参与者的秘密共享方案。 3 、给出了方案的正确性证明，指出方案中的策略集是经过对较差策略反复 删除后保留下来的纳什均衡。 三、本文提出了一个新的基于特殊权限理性秘密共享的方案，该方案相比以 前的方案具有以下特点： 1 、指出了传统的基于特殊权限秘密共享方案当参与者为理性时所面临的问 题和挑战，并予以分析。 2 、在研究以往基于特殊权限秘密共享方案的基础上，构造一个新的基于特 殊权限的理性秘密共享方案，并给出正确性证明。 3 、对方案的应用性进行了探讨，并给出了一些应用领域。 1 3本文的组织 本文第二部分对博弈论的发展研究情况和典型的博弈问题进行了介绍，并给 出了博弈论的分类，介绍了纳什均衡的定义，对纳什均衡的存在性和多重性问题 也做了探讨性研究。 第三部分给出了秘密共享的综述，回顾和分析了几个典型的秘密共享方案， 并介绍了理性秘密共享的发展。 第四部分给出了理性秘密共享的概念，研究分析了h t 2 0 0 4 方案，并在此基 山东大学硕士学位论文 础上构造了一个新的理性秘密共享方案，且给出了安全性证明。 第五部分介绍了基于特殊权限的秘密共享方案，在此基础上给出了基于特殊 权限的理性秘密共享方案，并给出了应用背景。 第六部分作为全文的总结，对博弈论在密码学中的应用下一步的研究方向进 行了展望。 4 山东大学硕士学位论文 第2 章博弈论与纳什均衡 2 1 博弈论的基本知识 博弈论是微观信息经济学的重要理论之一。博弈论源于奕者的战略思考，其 思想源远流长，能作为现代博弈论研究对象和研究内容的博弈思想与实践活动， 从世界范围来看，最早可追溯到中国古代。早在公元前5 1 2 年的我国春秋战国 时代孙武所著的孙子兵法书中的军事思想，以及“田忌赛马 事例就是 最早的博弈论思想和博弈论应用案例。 大多数学者认为，博弈理论开始于1 9 4 4 年冯诺依曼( j o h nv o nn e m n a n n ) 和经济学摩根斯坦( o s k a rm o r g e n s t e m ) 合作的博弈论与经济行为( t h et h e o r y o f g a m e sa n de c o n o m i cb e h a v i 0 0 - - 书，经过几十年的发展，到了2 0 世纪8 0 年代 后期，博弈论进入繁荣时期，众多博弈论专家产生了许多研究成果，博弈论的应 用范围也不在只是经济学的一个分支，而成为一种方法论，在政治学、军事、外 交、国际关系、公共政策、犯罪学等领域都得到了广泛应用。 2 1 1 博弈论的概念和基本要素 博弈论【1 ，2 ，3 ，4 1 的英文是g a m et h e o r y 或t h e o r yo fg a m e s ，又译为对策论、游 戏理论、竞赛理论。g a m et h e o r y 被视为数学的一个分支时，般译为对策论。 它主要是研究在利益相互影响的局势中，理性的局中人为了最大化自己的利益如 何选择各自的策略以及这种策略的均衡问题，即研究当一个局中人的选择受到其 他局中人的影响，而且反过来又影响其他局中人的选择时的决策问题和均衡问 题。严格地说，博弈论并不是经济学的一个分支。它是一种方法论，应用范围也 不限于经济学，政治学、军事、外交、国际关系、公共选择、犯罪学都涉及到博 弈论。但由于它在经济领域的应用最为成功、最为广泛，经济学家对博弈论的贡 献也越来越大，因此一般把博弈论列为经济学范围。 人们在研究现实博弈局势时发现，构成一种博弈最基本的要素有三：首先是 参与人，也就是利益主体，显然没有人参与就不能构成博弈；其次是每个人都可 以在一定的策略中进行选择，否则就没有决策可言；最后是每个人都可从结局中 山东大学硕士学位论文 得到一定的收益。将这三者抽象出来就形成策略型博弈。下面详细介绍博弈的基 本要素。 ( 1 ) 局中人( p l a y e r s ) ，即博弈的参与者，他们是博弈的决策主体，根据自 己的利益要求来决定各自的行为。也就是指一个对策中有权决定自己行动方案的 对策参与者或参加对策的每一方称为局中人，常用记号i = 1 ，2 来表示。对策中 关于局中人的概念是具有广义性的，局中人可以是自然人，也可以是各种社会组 织，如企业、政府、团体等等。一般要求一个对策中，至少有两个局中人。通常 用n - 1 ，2 ，n ) 来表示局中人集合。 ( 2 ) 策略( s t r a t e g i e s ) ，指每个局中人在博弈中可以选择采用的行动方案， 每个局中人均有可供其选择的多种策略。记局中人i 的策略为墨墨，s ，为局中 人f 所有可供选择的策略组成的策略集，又被称为局中人i 的策略空间。f 个局中 人各选择一个策略形成的向量s = ( s 。，s 2 ，了。) 被称为策略组合( s t r a t e g y p r o f i l e ) ，策略组合的集合为s = ，s t ，常被称为该博弈的策略空间。为了方便讨 论，我们把局中人f 之外的其他局中人( 即f 的对手一f ) 所采取的策略组合记为 s t s f ，因而策略组合8 = ( s l ”，s ，墨，s ，5 。) 就可简记为s = ( 岛，s j ) 。 策略型博弈中有两种策略概念，最基本的称为纯策略，另一种策略概念为在 纯策略基础上形成的混合策略( m i x e ds t r a t e g y ) 。同样的，策略集可以分为纯策 略集和混合策略集。下面我们分别给出纯策略集和混合策略集的概念。 纯策略集：每个局中人一般有若干个策略可供选择，它们构成了该局中人的 纯策略集。局中人的纯策略集可用s ，来表示，倘若墨由k i 个纯策略构成，则有 s ；= 1 , 2 ，k i 。 混合策略集：局中人f 的一个混合策略是指该局中人的纯策略集 上 墨= 1 ，2 ，k ， 上的概率分布；如以q 来表示，则吼= ( 毛。，毛：，) ，嘞= l 可见纯策略为混合策略的一中特殊情况。 一般每一局中人的策略集中至少应包含两个策略，局中人的所有策略组成了 该局中人的策略集合。策略集合可以是有限的，也可以是无限的。当每个局中人 6 山东大学硕士学位论文 在自己的集合中选定一个策略后，这局策略的结果就被决定了。 ( 3 ) 支付函数( p a y o f ff u n c t i o n s ) ，支付是指每个局中人从各种策略组合中 获得的收益，其中收益往往采用局中人的效用概念，由于它是策略组合的函数， 所以也被称为支付函数，记局中人i 的支付函数为”。( s ) 。对应于混合策略，局中 人的支付为得到的期望效用，关于矩阵人i 对应于混合策略组合仃的支付我们会 在下面有所介绍。 以上三种基本要素构成了策略型博弈，因此策略型博弈可记为 g = s l ，s 。；”1 ，甜。 。 ( 4 ) 对策的次序( o r d e r s ) ，在现实的各种策略活动中，当存在多个独立决 策方案进行决策时，有时候为了保证公平合理需要这些局中人进行同时决策。而 很多时候各参与方的决策有前后之分，并且有时候一个局中人还要做不止一次的 决策。这就免不了一个次序问题。因此，一个决策必须规定其中的次序，次序不 同一般认为就是不同的对策，即使对策的其他方面都相同。这一要素是扩展型博 弈的主要组成部分，也是策略型博弈和扩展型博弈的不同之处。 此外，在博弈模型中一般还存在均衡问题。所谓均衡，就是博弈时局中人所 达到的一种平衡的状态。在经济学中，均衡意味着相关量处于稳定值，在供求关 系中，某一商品市场如果在某一价格下，想以此价格买此商品的人均能买到，而 想卖的人均能卖出，此时我们就认为，该商品的供求达到了均衡。 2 1 2 博弈论的历史背景 一般认为，博弈理论开始于1 9 4 4 年由y o nn e u m a n n 和m o r g e n s t e m 合作的t h e t h e o r yo fc r d m e sa n de c o n o m i cb e h a v i o r 。到5 0 年代，合作博弈发展到鼎盛期， 包括纳什( n a s h ，1 9 5 0 ) 和s h a p l e y ( 1 9 5 3 ) 的“讨价还价模型，g i l l i e s 和s h a p l e y ( 1 9 5 3 ) 关于合作博弈中的“核( c o r e ) 一的概念，以及其他一些的贡献。 5 0 年代可以说是博弈论的巨人出现的年代。合作博弈论在5 0 年代达到顶峰， 同时非合作博弈论也开始创立。纳什在1 9 5 0 和1 9 5 1 年发表了两篇关于非合作博 弈的重要文章；t u c k e r 在1 9 5 0 年定义了“囚徒困境”( p r i s o n e r s d i l e m m a ) 。他们 两个人的著作基本上奠定了现代非合作博弈论的基石。 到6 0 年代后又出现了一些重要任务。s e l t e n ( 1 9 6 5 ) t 5 】将纳什均衡的概念引入 7 山东大学硕士学位论文 了动态分析，提出了“精练纳什均衡概念；h a r s 锄y i ( 1 9 6 7 1 9 6 8 ) 1 6 则把不完全信 息引入博弈论的研究。1 9 7 5 年，泽尔腾1 5 1 定义了“颤抖手的均衡”( t r e m b l i n g h a n d e q u i l i b r i u m ) ，克锐普斯( k ，e p s ) 和威尔逊( 斯l s o n ) 刀定义了“序贯均衡一( s e q u e n t i a l e q u i l i b r i u m ) ，弗得伯格( f u d e n b e r g ) 和泰勒尔( t i r o l e ) 8 】贝0 给出了“完美贝叶斯均衡一 ( p e r f e c tb a y e s i a ne q u i l i b r i u m ) 。这三个概念在许多情况下是一致的。其要点为： 博弈参与者要根据其观察到的他人行为来修正自己有关后者类型的主观概率，并 据此选择自己的策略行动。修正过程使用贝叶斯规则。现实中许多经济决策问题 都是一种不完全信息动态博弈问题。该博弈均衡解的给出，为博弈论方法在经济 学领域的应用开辟了更加广泛的前景。 上世纪7 卜8 0 年代，博弈论在经济理论中的应用得到迅速的发展，并逐 步成为西方经济学的一部分，在现代微观经济学、产业组织理论和宏观经济政策 分析方面都得到广泛的应用。 1 9 9 4 年诺贝尔经济学奖授予了三位博弈论专家：纳什、泽尔腾和海萨尼；1 9 9 6 年又授予两位博弈论专家：詹姆斯米尔利斯( ( j a m e sa m i r r l e s s ) 和威廉维克里 ( w i l l i a mv i c k e r y ) ，以表彰他们对不对称信息条件下激励经济理论做出的开拓性 和奠基性贡献。这表明博弈论己经在经济学领域发挥了重大作用，产生了巨大影 响。 博弈论作为一种专门研究参与者之间相互依赖、相互影响的决策行为及其结 果的方法，特别强调参与者的理性行为及其相互关系，强调决策信息和决策时序 对决策行为及其后果的影响。这与现代经济学发展的趋势相一致，而它严密的逻 辑结构和分析方法也为现代经济学的理论研究提供了一个有效的分析工具。博弈 论在密码学中也有着广阔的应用，并且对以往的密码学模型有深刻影响。在密码 学模型中的参与者是单纯的，或者诚实或者恶意，将博弈论的思想引入以后，讨 论参与者是理性时对模型的影响，并对新模型进行构建研究，也已成为新的研究 方向。 2 1 3 博弈分类 总的来说，博弈论可以划分为合作博弈和非合作博弈。合作博弈和非合作博 弈之间的区别主要在于人们的行为相互作用时，当事人能否达成一个具有约束力 8 山东大学硕士学位论文 的协议，如果能，就是合作博弈，否则就是非合作博弈。如两寡头企业，如果它 们之间达成一个协议，联合最大化垄断利润，并且各自按照这个协议组织生产， 这就是合作博弈，他们面临的问题就是如何分享合作带来的收益；但是，如果这 两个企业间的协议不具有约束力，就是说，没有哪一方强制另一方遵守这个协议， 每个企业都可只选择自己的最优产量或价格，则是非合作博弈。合作博弈强调的 是团体理性，强调的是效率、公平、公正：非合作博弈强调的是个人理性、个人 最优决策，其结果可能是有效率的，也可能是无效率的。 非合作博弈的划分可以从两个角度进行： 第个角度是从时间上来划分，即考虑局中人行动的先后顺序。从这个角度， 博弈论又可以分为静态博弈和动态博弈。在静态博弈中，局中人同时选择行动或 虽非同时，但后行动者并不知道先行动者采取了什么具体行动；动态博弈指的是 局中人的行动有先后顺序，后行动者能够观察到先行动者所选择的行动，并且能 给根据观察来决定自己的行动。 划分非合作博弈的第二个角度是从信息方面来划分，即局中人对有关其他局 中人的特征、策略空间及支付函数的知识。从这个角度，博弈可以划分为完全信 息博弈和不完全信息博弈。完全信息博弈是指每个局中人对所有其他局中人的特 征、策略空间及支付函数都准确的知识；如果局中人对其他局中人的信息没有准 确的知识，则是不完全信息博弈。 将上述两个角度的划分结合起来，可以得到四种不同类型的非合作博弈：完 全信息静态博弈、完全信息动态博弈、不完全信息静态博弈、不完全信息动态博 弈。 而与上述四种博弈相对应的是四个均衡概念：纳什均衡( n a s he q u i l i b r i u m ) ( 纳什，1 9 5 0 1 9 5 1 ) ；子博弈完美纳什均衡( s u b g a m ep e r f e c tn a s he q u i l i b f i u r n ) ( 泽尔腾，1 9 6 5 ) ；贝叶斯一纳什均衡( b a y e s i a n - - n a s he q u i l i b r i u m ) ( 豪尔绍尼， 1 9 6 7 - 1 9 6 8 ) ；完美贝叶斯一纳什均衡( p e r f e c tb a y e s i a n - - n a s he q u i l i b r i u m ) 【泽尔 腾，1 9 7 5 ；克瑞普斯( k r e p s ) 和威尔逊( w i l s o n ) ，1 9 8 2 ；弗登博格( f u d e n b e r g ) 和泰洛尔( t i r o l e ) ，1 9 9 1 】。 下表概括了上面所讲的四种博弈及对应的四个均衡的概念。 9 山东大学硕士学位论文 表2 1 博弈论分类 完全信息不完全信息行动顺序 完全信息静态博弈不完全信息静态博 静态纳什均衡 弈 贝叶斯一纳什均衡 完全信息动态博弈不完全信息动态博 动态子博弈完美纳什均弈 衡完美贝叶斯一纳什 均衡 还有其他的一些划分方法。例如根据博弈方的个数，博弈可以分为单人博弈， 两人博弈和多人博弈。此外，根据博弈中的得益，可以分为零和博弈、常和博弈 以及变和博弈。零和博弈各博弈方得益之和总为零，常和博弈指各博弈方得益之 和总为常数，变和博弈指的是各博弈方得益之和不定。 2 2 典型的博弈模型 l 、囚徒困境 囚徒困境问题是博弈论中最为经典的问题。囚徒困境讲的是两个嫌疑犯作案 后被警察抓住，分别被关在不同的屋子里审讯( 非合作) 。警察告诉它们：如何两 人都坦白，各判五年刑；若两人都抵赖，各判一年；如果一人坦白，一人抵赖，则 坦白者无罪开释，抵赖者判八年刑。 1 0 山东大学硕士学位论文 表2 2 囚徒博弈 囚徒b 坦白抵赖 囚徒a 坦白5 ，- 50 ，- 8 抵赖 8 ，o1 ，1 表2 2 给出了囚徒困境的策略式表达。每一囚徒有两个策略：坦白和抵赖。 表中每一格又两个数字，第一个对应囚徒a 的得益；第二个对应囚徒b 的得益。 策略形式又称标准形式，是博弈的两种表述形式之一( 另外一种是扩展形式) ， 它特别方便于静态博弈分析。 在这个例子中，纳什均衡就是( 坦白，坦白) 。不论对方如何选择，个人最优 选择是坦白。这是一种纯策略纳什均衡。虽然从得益上看，( 抵赖，抵赖) 对对方 而言更理想，但它不满足个人理性要求，因此不是纳什均衡。由此可见，纳什均 衡往往是低效的。 囚徒困境在现实生活中具有相当的普遍性，在市场竞争、环境问题、公共资 源开发利用以至军备竞赛中屡见不鲜，它反映了个人理性与集体理性之间的矛 盾。 2 、猜硬币博弈 这是一个古老的博弈。两人通过猜硬币的正反面赌输赢，其中一人用手盖住 一枚硬币，由另外一个人猜是正面朝上还是反面朝上。若猜对，则猜者赢l 元： 否则，猜者输1 元。 这里不能像分析囚徒困境那样给出一个纯策略纳什均衡。在这一博弈中，取 胜的关键是不能让另一方猜到自己的策略而同时自己又要尽可能猜出对方的策 略。在多次重复中，如果双方的决策方式都正确，则可求得平均的双方得益。 山东大学硕士学位论文 表2 3 硬币博弈 猜方 正面 反面 盖方 正面1 ，ll ， 1 反面 1 ，11 ，l 与猜硬币博弈情况类似的还有诸如田忌赛马，石头剪子布博弈等等。这 类博弈不可能有确定性的解，他们需要用混合策略来解决。 3 、性别战 性别战说的是，一男一女约会，或者去看足球比赛，或者看芭蕾舞演出。男 的偏好足球赛，女的偏好芭蕾舞，但他们都宁愿在一起而不愿分开，下表给出了 得益矩阵。 表2 4 性别战博弈 足球芭蕾 男 足球2 ，l 0 。0 芭蕾 o ， ol ，2 这个博弈有两个纯策略纳什均衡：( 足球，足球) ，( 芭蕾，芭蕾) 。事实上这个 博弈还有一个混合策略纳什均衡。类似的例子还有斗鸡博弈，商场消耗战博弈等 等。这些例子充分表明了纳什均衡的多重性。 4 、s t a c k d b e r g 寡头竞争模型