• 主题
高级搜索  >
历史搜索 清空历史
首页> 中文学位 >正规型纳什均衡点的整数规划计算方法及不动点算法的分布式实现
【6h】

正规型纳什均衡点的整数规划计算方法及不动点算法的分布式实现

代理获取
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

纳什均衡的正式定义第一次出现在文章中，但对它的研究已经具有了很长的历史，并且它在博弈论及其相关应用（比如经济学，计算机科学，管理科学，生物学，社会学等等）中发挥着基石作用。纳什均衡的概念是用来分析多决策者同时做决策时的决策结果，换句话说，它提供了当所有人的决策结果相互依赖时，对决策组的一种提前预测。纳什均衡是以John Forbes Nash命名的，他和博弈论理论学家Reinhard Selten，John Harsanyi在1994共享了诺贝尔经济学奖。在Antoine Augustin Cournot的垄断理论书[2]中，第一次出现了纳什均衡的概念，在Cournot的理论中所有公司都可以选择提高产品数量来提高公司利润，然而，对某一个公司来说，它最佳的生产产品数量依赖于别的公司，如果给定了其他的公司的生产数量，每个公司生产数量都可以使本公司利润最大化，就是一个Cournot均衡点，这是最早的关于纯策略纳什均衡点的研究。在Cournot分析均衡稳定性的时候，最佳动态响应的概念也被用到。当提出混合策略的纳什均衡的概念后，现在博弈论中关于纳什均衡的概念就完全被改变了。在这样的混合策略纳什均衡中，每一个参与者对可能的行动可以以一种概率的方式来选择决策。这种纳什均衡问题在书[3]中第一次被提及，但是书中仅仅考虑了一种零和的特殊类型。文章第一次给出了纳什均衡的正式定义，并证明了任何有限策略博弈中至少存在一个混合策略的纳什均衡。随着纳什均衡概念的发展，一些博弈论研究者发现在一些情况下所做的预测总是有误差，这主要是因为一个博弈中经常存在着多个纳什均衡点，而这些均衡点通常和我的直观概念不同。为了得到更精确的预测，一些被称为改良版纳什均衡的概念在文章中被提出来。
　　自从纳什均衡的概念被提出来，纳什均衡已经被应用到了各行各业。书[3]使用纳什均衡的概念扩展了经济学的范围;文章一次使用纳什均衡的概念来分析敌对情况，比如军备竞赛和战争];纳什均衡可以用来分析不同人之间合作的可能性，分析他们是否会冒险来得到一个合作结果;文章使用纳什均衡的概念来分析货币危机和银行倒闭的概率;其他方面的应用包括交通流，如何组织拍卖，立法管理，足球比赛里的点球以及教育过程中多社团竞争效果的分析。
　　在这些纳什均衡的应用中，一个重要的研究课题是如何有效的选择一个纳什均衡点，特别是如何选择一个多人有限策略博弈的均衡点。为了解决这个问题，接下来的文献中做了很多贡献。从计算复杂度方面来说，文章证明了仅仅寻找一个纳什均衡点的问题就是PPAD-complete问题，所以很难寻找到一个纳什均衡点，寻找所有纳什均衡点就更加困难了。Lemke-Howson算法是计算双矩阵博弈均衡点的第一个方法，这个算法是在用代数方法证明双矩阵博弈至少存在一个均衡点时得到的，在实际应用中，这个算法效率很高，被称为至今计算纳什均衡点最好的方法[27]，但是在最坏的情况下，旋转操作的数量会随纯策略数量指数增长.后来，文章证明了用Lemke-Howson算法寻找任何一个纳什均衡点都是一个PSPACE-complete问题。文章把Lemke-Howson算法扩展为可以求解多人博弈问题。为了估计一个连续映射的不动点，单纯型法第一次在文章提出，并在中得到了进一步的发展，这个单纯型法后来被用来计算纳什均衡点。文章很好的处理了非线性互补问题，这篇文章提出来一种很好的求解非合作多人博弈的纳什均衡点的方法。关于单纯型法的进一步研究可以在文章[42，43]中找到，计算结果显示这种方法的迭代次数很少。通过开发文章[44]中的线性追踪过程，一种旋转过程的方法在文章[45，46]中被提出用来计算双人博弈的纳什均衡点，这种旋转过程的方法可以表述如下:所有人开始任选一个策略组，通过考虑初始策略组而对现有策略进行改变，从而达到一个均衡点。更精确的说，初始最优化策略组被选到的概率越来越大，别的策略组被选到的概率越来越小。初始策略组在整个调整过程中发挥了很重要的作用，因为所有的调整都是基于初始策略组，这种方法很容易被计算机实现，同时，这个过程已经被扩展为寻找多人博弈的纳什均衡点[47]。1996年前关于计算纳什均衡点的文献可以在文章[48]中找到，计算两人博弈的纳什均衡点的文献可以在文章[49]中找到。通过研究问题的可微性，一些关于计算纳什均衡的方法已经在以下文献中提出。通过两个系数，一种平滑的对数跟踪过程在文章[50，6]中被开发出来，对每个博弈，这个对数跟踪过程首先在这个博弈的策略组规定一个优先的概率分布，给定优先概率分布，这个过程会在所有纳什均衡集合中找出唯一的一个纳什均衡，文章[51]证明了当两个系数依次趋向于0时，这种对数跟踪过程一定收敛于一个纳什均衡点。一种可微同伦方法在文章[52]中被提出，这种方法是基于线性跟踪过程及对优化条件系统变量的非线性转化。基于Kohlberg和Mertens的框架理论，文章[53]组合了牛顿全局方法[54]和同伦方法[33]得到了一种计算纳什均衡的算法，关于同伦方法来计算纳什均衡的讨论可以在文章[55]中找到。
　　以上介绍的方法都只能找到一个纳什均衡点，实际中，一个博弈中通常具有多个纳什均衡点，如何有效的选择一个合适的均衡点，依然是个具有挑战的课题，这个选择过程通常需要计算一个博弈中所有的纳什均衡点。为了解决这个问题，下述文献中给出了一些计算法方法。文章[56]中给出了一种路径跟踪算法来计算双矩阵博弈问题的所有纳什均衡点，一种同伦算法被用来计算多人博弈的所有均衡点，这两种方法都是基于一个多项式方程系统。对于多项式同伦连续方法计算所有纳什均衡点的调查可以在[58]中找到。文章[59]提出了一种混合整数规划的方法来计算双矩阵博弈的所有纳什均衡点。最近，通过枚举多面体所有端点，文章开发了出两种方法来计算双矩阵博弈问题的所有均衡点。
　　作为混合策略纳什均衡问题的一个特例，纯策略纳什均衡问题最近也得到了不少关注。文章[61]证明了判断纯策略纳什均衡点是否存在是一个NP-hard问题，文章[20]提出了一种在图像博弈和马尔科夫随机域之间的映射，从而前者的纯策略纳什均衡点可以通过后者的统计推算找到。基于博弈激励反应一种新的形式，文章[62]开发出了一种基于条件满足的算法来计算纯策略纳什均衡点。文章[63]提出了一种被称为Valued Nash Propagation的有效算法来计算纯策略纳什均衡点，这种方法满足具有稀疏交互结构博弈问题的各种迭代。其他关于纯策略纳什均衡计算的文献可以见[20，64，65]。
　　这篇文章中，我们使用了0-1线性规划方法来求解纯策略纳什均衡点，使用混合整数规划方法来求解混合策略纳什均衡点，这两种方法都需要求解整数规划问题。整数规划是线性规划的一个特殊情况，在这种特殊情况下全部或者部分变量是整数，不再像线性规划中所有变量都具有连续性。自从Dantzig[66]第一次把整数规划用于求解TSP问题后，整数规划已经成为了一种最成功最有效的求解现实世界中离散变量问题的建模工具。文章[22]中已经证明了整数规划问题是一种NP-complete问题，现在已经有好多成熟的算法可以求解整数规划问题。Gomory在文章[67]中用切平面的方法来求解混合整数规划，这个方法是通过求解原整数规划的线性松弛来工作的。分支定界算法第一次在文章[77]中被开发出来，这个方法包含了一个系统的关于所有候选点的枚举方法，通过上下界条件判定，很大部分不满足条件的候选点被舍弃掉。别的一些比较优秀的整数规划算法包括临近算法，降基算法等等。通过构建一个单调升的映射，DANG和YE[23，24]开发出一种计算整数规划的不动点算法，给定一个多面体，这个算法或者能够找出一个混合整数解，或者证明此多面体没有整数解。理论上讲，如果问题维度是固定的，这个算法就是多项式的。作为这个算法的一个特性，它可以很容易进行分布式实现，初始的计算结果证明这种分布式不动点迭代算法效率很高。
　　在数值计算中，当有很困难问题需要求解时常常需要借助于分布式计算。在分布式计算中，一个问题可以被分割成很多小问题，每个小问题都可以由不同的计算机来计算，然后汇总，得到最终的计算结果。分布式计算方式有两种模型，分别对应我们文章中的图(5.3)和图(5.4)，图(5.3)是一种简单模型，数据和信息的交流只存在于主机和分机之间，图(5.4)是一种交互模型，分机之间可以进行数据和信息交流，当有一台分机计算完自己的任务时可以继续分担其他分机的工作，从而大大提高整体的计算效率。作为DANG和YE算法的一个附带的优点，是它可以很容易用分布式的方法实现。所有的代码都是用C++编写，并在WINDOW平台运行，我们用免费软件MPICH2来实现计算机之间的通信。在分配工作中，如何把总的工作平均分给各个分机比较重要，我们在文章中考虑了两种分割方法，第一种是一种大致平均分配方法，第二种是一种概率分配，这种方法源于对拉丁方的分配方法[117]，数据结果表明当计算机数量比较少时第一种方法比较好，当计算机数量很大时，第二种方法可以取得很好的计算结果。我们用这个分布式系统求解了几类经典的运筹学问题，数据结果显示我们的方法具有很大的优越性，并且我们可以用此类方法求解别的运筹学问题，我们下一步工作是开发一个基于这个分布式方法的软件包，来更好的求解实际问题。
　　这篇文章包括了六个章节。第一章是纳什和整数规划的介绍，这章中首先介绍了纳什均衡和整数规划的背景，然后系统介绍了文章的研究目标，本章最后一部分调研了计算纳什均衡点的方法以及一些有名的整数规划计算方法。文章第二章，我们会介绍一些计算纳什均衡点的初始工作。第一个初始工作是关于把多人博弈降基为三人博弈，这种降基方法在文章[96，97]中被开发出来，并且这种降基是多项式时间的。基于这种降基方法，我们以后只需要考虑3人博弈问题，因为任何的多人博弈都可以在多项式时间内降基为3人博弈问题。在这篇文章中，我们考虑的是多人博弈问题，这种降基方法可以使我只需要考虑3人博弈，这在数值计算方面是足够的。另外一个初始工作是关于多线性项的一个估计，当我们在计算混合策略纳什均衡点时，会有出现这个多线性项，如果直接计算这个多线性项，非常困难，在这种情况下文章[98，99]给出了一种对这个多线性项的估计，通过合理利用这个估计，我们可以有效的避开直接计算多线性项，从而大大降低了问题的计算难度，后面的数值计算结果表明这种方法是有很有效的。文章的第三章，我们主要是计算所有正规型纯策略纳什均衡点，为了求解所有纯策略纳什均衡点，一种混合的0-1线性规划方法被开发出来，这种方法主要是基于开发纯策略的特性和多线性项的特性，通过对0-1线性规划算式的求解，可以得到所有纯策略纳什均衡点，求解所有0-1线性规划有很多算法可以使用，一些商业软件可以很好求解这种0-1线性规划，比如MATLAB，CPLEX等等，我们用CPLEX来求解这个规划问题，数据结果显示我们的算法是可行的，并且计算效率很高，据我们所知这种0-1线性规划方法求解纳什均衡点是首次被提出，而且这种方法可以很好的用在一些类似的问题上。文章的第四章致力于求解正规型混合策略多人博弈的纳什均衡点，在混合策略下，对于线性项的直接求解很困难，在这种情况下我们提出了一种对线性项的估计方法，进而得到一种混合整数规划方法来求解这类混合策略纳什均衡点的问题，通过求解这个混合整数规划可以得到相应博弈的所有混合纳什均衡点，实验结果证明了这种方法的有效性。为了更好的求解混合整数规划问题，第五章我们对DANG和YE的不动点迭代算法进行了并行实现，这章中共有五部分，第一部分是对DANG和YE算法的详细介绍，第二部分介绍了部分分布式计算的技术细节，接下来三部分分别计算了三个算例:求解纳什均衡点问题，市场分割问题，背包可行性问题，这三个算例用了多种整数算法来计算，结果显示我们的分布式实现方法具有很大的优越性。文章的第六章给出了一些总结性讨论，并讨论了一些将来有可能要做的工作。
　　文章的创新点和贡献可以分为以下三个部分:
　　1、一种混合0-1线性规划方法被开发出来求解正规型有限博弈的所有纯策略纳什均衡点。这种新的方法是通过研究纯策略和多线性项得到的，据我们所知，这是第一次用0-1线性规划方法来求解纯策略纳什均衡点问题，并且文章给出了仿真计算结果，数据结果显示我们的方法是有效的。
　　2、一种混合整数线性规划方法被开发出来求解正规型有限博弈的所有混合策略纳什均衡点。这种新方法是基于对多线性项的估计以及对混合策略性质的开发，数据结果显示了这种计算方法的有效性，并且可以用到类似的具有多线性项的问题中。
　　3、用分布式的方式实现了DANG和YE的不动点迭代算法，并用这种分布式系统实现了求解整数规划问题。为了更好的求解整数规划问题，我们采用了分布式的方式来实现DANG和YE的迭代算法，并用这种分布式系统求解了三类经典的运筹学问题:求解纯策略纳什均衡点问题、市场分割问题和背包可行性问题。为了更好的比较计算结果，别的一些整数规划算法也用来求解同样的问题，数据显示我们的分布式方法具有很大的优越性。

著录项

相似文献

  • 中文文献
  • 外文文献
  • 专利
代理获取

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号