纳什平衡计算问题.pdfVIP

第12卷第1期 铜仁学院学报 Journalof 2010年1月 TongrenUniversity 纳什平衡的计算问题 许道云 (贵州大学计算机科学与技术学院，贵州贵阳550025) 摘要：本文介绍了博弈的形式描述系统，混合博弈实质上是基于纯博弈系统框架下在策略集上引入概率 分布。局中人之间的不合作性表现分布之间的独立性．给出了囚犯二难概型博弈系统与其纯博弈系统纳什平衡 之间的联系，并对概率纳什平衡的计算进行了讨论． 关键词： 纯博弈系统； 离散概型博弈系统； 纳什平衡； 支付计算 中图分类号：TP301．5文献标识码：A 文章编号：1673。9639(2010)Ol一0131—08 博弈论的产生背景主要源于经济学中经济行为冲突的量 (4)计算纳什平衡(如果存在)的有效算法及计算复 化分析与行为推断l”。随着不同博弈系统(模型)的提出以 杂性。 及在其它领域的应用。人们开始注意到：博弈论的应用不仅 基于上述动机，本文首先给出了博弈系统的形式描述。 局限于经济领域。除了经济学家以外，数学家和计算机科学 提出了概型博弈系统的概念，并指明通常的混合博弈实质上 家对博弈论的基本理论、数学描述、应用联系展开了更加深 是基于一个纯博弈系统框架产生的扩展系统，博弈中的不合 入的研究。如：参考文献【2】用非线性分析方法对纳什平衡的 作性表现为分布之间的相互独立性。这些有助于理解两类系 存在性及性质展开系统研究，参考文献[3】则将纳什平衡与(优 统之间的联系，以及概率论方法在研究博弈论中的应用。基 先)逻辑程序的回答集相联系，等等。 于此，概率论的工具可以用于讨论更复杂的博弈系统(如： 我们感兴趣如下问题的研究： 连续型博弈系统等)。其次，我们对一个典型的概型博弈系统 (1)博弈论中的一些思想和结论在布尔公式可满足性问 的纳什平衡的性质及其计算方法作了进一步的探讨和研究。 题(SAT问题)、以及在一般约束可满足性问题(CSP问题) 中的联系和应用。 1．博弈论基础知识 (2)弱纳什平衡问题。混合博弈(本文称概型博弈)的 一个纯博弈系统可以用一个三元组表示： 纳什平衡总是存在的。但是，纯博弈的纳什平衡不一定存在。 而由一个纯博弈系统可以诱导出一个概型博弈系统。一种自 个参与博弈的智能体(agent)，有限集Si={Jf。l．一，si,nj为第 然的想法是：如果一个纯博弈系统的纳什平衡不存在，如何 从对应的概型博弈系统的纳什平衡近似决定原系统的近似纳 表，描述n个智能体在各自的策略选择后的得益分配(也称 什平衡(称为弱纳什平衡问题)。 支付)，表现为一个取值为n维实向量的n元函数 (3)纳什平衡判定问题。纯博弈的纳什平衡不一定存在。 r：sl 于是自然有如下判定问题： NE问题(Nash 集。记S=S EquilibriumProblem)： 实例：给合一个纯博弈系统G=I彳，T，／sl，．一，S。}J． 的一个策略， 一个s=(sl，．一，s。)∈s称为 询问：G=【彳，T，isl，…，S。”是否存在一个纳什平衡? NE问题应该是一个NP．完全问题。 我们关心的是：哪种类型，或在何种充分条件下，纳什 平衡必然存在? 为xf。 收稿日期；2009．Ol—19 基金项目：贵州省优秀科技教育人才省长基金． 作者简介：许道云‘1959-)。男，博导，教授，主要研究领城为计算复杂性。可计算分析． 13l