正规型纳什均衡点的整数规划计算方法及不动点算法的分布式实现
|
摘要
纳什均衡的正式定义第一次出现在文章[1]中,但对它的研究已经具有了很长的历史,并且它在博弈论及其相关应用(比如经济学,计算机科学,管理科学,生物学,社会学等等)中发挥着基石作用。纳什均衡的概念是用来分析多决策者同时做决策时的决策结果,换句话说,它提供了当所有人的决策结果相互依赖时,对决策组的一种提前预测。纳什均衡是以John Forbes Nash命名的,他和博弈论理论学家Reinhard Selten, John Harsanyi在1994共享了诺贝尔经济学奖。在Antoine Augustin Cournot的垄断理论书[2]中,第一次出现了纳什均衡的概念,在Cournot的理论中所有公司都可以选择提高产品数量来提高公司利润,然而,对某一个公司来说,它最佳的生产产品数量依赖于别的公司,如果给定了其他的公司的生产数量,每个公司生产数量都可以使本公司利润最大化,就是一个Cournot均衡点,这是最早的关于纯策略纳什均衡点的研究。在Cournot分析均衡稳定性的时候,最佳动态响应的概念也被用到。当提出混合策略的纳什均衡的概念后,现在博弈论中关于纳什均衡的概念就完全被改变了。在这样的混合策略纳什均衡中,每一个参与者对可能的行动可以以一种概率的方式来选择决策。这种纳什均衡问题在书[3]中第一次被提及,但是书中仅仅考虑了一种零和的特殊类型。文章[1]第一次给出了纳什均衡的正式定义,并证明了任何有限策略博弈中至少存在一个混合策略的纳什均衡。随着纳什均衡概念的发展,一些博弈论研究者发现在一些情况下所做的预测总是有误差,这主要是因为一个博弈中经常存在着多个纳什均衡点,而这些均衡点通常和我的直观概念不同。为了得到更精确的预测,一些被称为改良版纳什均衡的概念在文章[4-7]中被提出来。
自从纳什均衡的概念被提出来,纳什均衡已经被应用到了各行各业。书[3]使用纳什均衡的概念扩展了经济学的范围；文章[8]第一次使用纳什均衡的概念来分析敌对情况,比如军备竞赛和战争[10]；纳什均衡可以用来分析不同人之间合作的可能性,分析他们是否会冒险来得到一个合作结果[11]；文章[12]使用纳什均衡的概念来分析货币危机和银行倒闭的概率；其他方面的应用包括交通流[13],如何组织拍卖[14-16],立法管理[17],足球比赛里的点球[18]以及教育过程中多社团竞争效果的分析[19]。
在这些纳什均衡的应用中,一个重要的研究课题是如何有效的选择一个纳什均衡点,特别是如何选择一个多人有限策略博弈的均衡点。为了解决这个问题,接下来的文献中做了很多贡献。从计算复杂度方面来说,文章[20,21]证明了仅仅寻找一个纳什均衡点的问题就是PAD-complete问题,所以很难寻找到一个纳什均衡点,寻找所有纳什均衡点就更加困难了。Lemke-Howson算法[26]是计算双矩阵博弈均衡点的第一个方法,这个算法是在用代数方法证明双矩阵博弈至少存在一个均衡点时得到的,在实际应用中,这个算法效率很高,被称为至今计算纳什均衡点最好的方法[27],但是在最坏的情况下,旋转操作的数量会随纯策略数量指数增长[28].后来,文章[29]证明了用Lemke-Howson算法寻找任何一个纳什均衡点都是一个PSPACE-complete问题。文章[30,31]把Lemke-Howson算法扩展为可以求解多人博弈问题。为了估计一个连续映射的不动点,单纯型法第一次在文章[32]提出,并在[33-39]中得到了进一步的发展,这个单纯型法后来被用来计算纳什均衡点[40]。文章[41]很好的处理了非线性互补问题,这篇文章提出来一种很好的求解非合作多人博弈的纳什均衡点的方法。关于单纯型法的进一步研究可以在文章[42,43]中找到,计算结果显示这种方法的迭代次数很少。通过开发文章[44]中的线性追踪过程,一种旋转过程的方法在文章[45,46]中被提出用来计算双人博弈的纳什均衡点,这种旋转过程的方法可以表述如下：所有人开始任选一个策略组,通过考虑初始策略组而对现有策略进行改变,从而达到一个均衡点。更精确的说,初始最优化策略组被选到的概率越来越大,别的策略组被选到的概率越来越小。初始策略组在整个调整过程中发挥了很重要的作用,因为所有的调整都是基于初始策略组,这种方法很容易被计算机实现,同时,这个过程已经被扩展为寻找多人博弈的纳什均衡点[47]。1996年前关于计算纳什均衡点的文献可以在文章[48]中找到,计算两人博弈的纳什均衡点的文献可以在文章[49]中找到。通过研究问题的可微性,一些关于计算纳什均衡的方法已经在以下文献中提出。通过两个系数,一种平滑的对数跟踪过程在文章[50,6]中被开发出来,对每个博弈,这个对数跟踪过程首先在这个博弈的策略组规定一个优先的概率分布,给定优先概率分布,这个过程会在所有纳什均衡集合中找出唯一的一个纳什均衡,文章[51]证明了当两个系数依次趋向于0时,这种对数跟踪过程一定收敛于一个纳什均衡点。一种可微同伦方法在文章[52]中被提出,这种方法是基于线性跟踪过程及对优化条件系统变量的非线性转化。基于Kohlberg和Mertens的框架理论,文章[53]组合了牛顿全局方法[54]和同伦方法[33]得到了一种计算纳什均衡的算法,关于同伦方法来计算纳什均衡的讨论可以在文章[55]中找到。
以上介绍的方法都只能找到一个纳什均衡点,实际中,一个博弈中通常具有多个纳什均衡点,如何有效的选择一个合适的均衡点,依然是个具有挑战的课题,这个选择过程通常需要计算一个博弈中所有的纳什均衡点。为了解决这个问题,下述文献中给出了一些计算法方法。文章[56]中给出了一种路径跟踪算法来计算双矩阵博弈问题的所有纳什均衡点,一种同伦算法[57]被用来计算多人博弈的所有均衡点,这两种方法都是基于一个多项式方程系统。对于多项式同伦连续方法计算所有纳什均衡点的调查可以在[58]中找到。文章[59]提出了一种混合整数规划的方法来计算双矩阵博弈的所有纳什均衡点。最近,通过枚举多面体所有端点,文章[60]开发了出两种方法来计算双矩阵博弈问题的所有均衡点。
作为混合策略纳什均衡问题的一个特例,纯策略纳什均衡问题最近也得到了不少关注。文章[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的迭代算法,并用这种分布式系统求解了三类经典的运筹学问题：求解纯策略纳什均衡点问题、市场分割问题和背包可行性问题。为了更好的比较计算结果,别的一些整数规划算法也用来求解同样的问题,数据显示我们的分布式方法具有很大的优越性。
A primary concern in applications of game theory is how to effectively select a Nash equilibrium, especially, a Nash equilibrium for a finite n-person game in normal form. This selection process often requires the computation of all Nash equilibria. It is well known that determining whether a finite game has a Nash equilibrium is an NP-hard problem and it is difficult to solve by naive enumeration algorithm. By exploiting the properties of pure strategy and multilinear terms in the payoff functions, this thesis begins by formulating a new mixed0-1linear program for computing all pure-strategy Nash equilibrium of finite n-person game in normal form. To our knowledge, it is the first method to formulate a mixed0-1linear programming for pure-strategy Nash equilibria and it may work well for other similar problems. Numerical results show that the approach is effective and this method can be easily distributed. For the mixed-strategy Nash equilibrium of a finite n-person game in normal form, multilinear terms appears in the payoff functions too. However, it is more difficult than the pure-strategy problem since the variables are0or1in pure-strategy cases and0to1in mixed-strategy cases. A good approximation of multilinear terms is introduced to fix this problem. Based on this approximation and the properties of mixed-strategy Nash equilibria, a mixed integer linear programming is obtained to find all mixed-strategy Nash equilibria of a finite n-person game in normal form.
In order to solve the integer programming effectively, a distributed implemen-tation of Dang and Ye's distributed fixed-point iterative method, which is a new al-ternative algorithm for integer programming, is also developed in this thesis. This fixed-point algorithm is derived from an increasing mapping which satisfies certain properties. Three classical problems, the problem of finding the pure-strategy Nash equilibria, the market split problem and the knapsack feasibility problem, are solved by this distributed implementation which is demonstrated by numerical results to be effective, with the potential for extension to other integer problems.
自从纳什均衡的概念被提出来,纳什均衡已经被应用到了各行各业。书[3]使用纳什均衡的概念扩展了经济学的范围；文章[8]第一次使用纳什均衡的概念来分析敌对情况,比如军备竞赛和战争[10]；纳什均衡可以用来分析不同人之间合作的可能性,分析他们是否会冒险来得到一个合作结果[11]；文章[12]使用纳什均衡的概念来分析货币危机和银行倒闭的概率；其他方面的应用包括交通流[13],如何组织拍卖[14-16],立法管理[17],足球比赛里的点球[18]以及教育过程中多社团竞争效果的分析[19]。
在这些纳什均衡的应用中,一个重要的研究课题是如何有效的选择一个纳什均衡点,特别是如何选择一个多人有限策略博弈的均衡点。为了解决这个问题,接下来的文献中做了很多贡献。从计算复杂度方面来说,文章[20,21]证明了仅仅寻找一个纳什均衡点的问题就是PAD-complete问题,所以很难寻找到一个纳什均衡点,寻找所有纳什均衡点就更加困难了。Lemke-Howson算法[26]是计算双矩阵博弈均衡点的第一个方法,这个算法是在用代数方法证明双矩阵博弈至少存在一个均衡点时得到的,在实际应用中,这个算法效率很高,被称为至今计算纳什均衡点最好的方法[27],但是在最坏的情况下,旋转操作的数量会随纯策略数量指数增长[28].后来,文章[29]证明了用Lemke-Howson算法寻找任何一个纳什均衡点都是一个PSPACE-complete问题。文章[30,31]把Lemke-Howson算法扩展为可以求解多人博弈问题。为了估计一个连续映射的不动点,单纯型法第一次在文章[32]提出,并在[33-39]中得到了进一步的发展,这个单纯型法后来被用来计算纳什均衡点[40]。文章[41]很好的处理了非线性互补问题,这篇文章提出来一种很好的求解非合作多人博弈的纳什均衡点的方法。关于单纯型法的进一步研究可以在文章[42,43]中找到,计算结果显示这种方法的迭代次数很少。通过开发文章[44]中的线性追踪过程,一种旋转过程的方法在文章[45,46]中被提出用来计算双人博弈的纳什均衡点,这种旋转过程的方法可以表述如下：所有人开始任选一个策略组,通过考虑初始策略组而对现有策略进行改变,从而达到一个均衡点。更精确的说,初始最优化策略组被选到的概率越来越大,别的策略组被选到的概率越来越小。初始策略组在整个调整过程中发挥了很重要的作用,因为所有的调整都是基于初始策略组,这种方法很容易被计算机实现,同时,这个过程已经被扩展为寻找多人博弈的纳什均衡点[47]。1996年前关于计算纳什均衡点的文献可以在文章[48]中找到,计算两人博弈的纳什均衡点的文献可以在文章[49]中找到。通过研究问题的可微性,一些关于计算纳什均衡的方法已经在以下文献中提出。通过两个系数,一种平滑的对数跟踪过程在文章[50,6]中被开发出来,对每个博弈,这个对数跟踪过程首先在这个博弈的策略组规定一个优先的概率分布,给定优先概率分布,这个过程会在所有纳什均衡集合中找出唯一的一个纳什均衡,文章[51]证明了当两个系数依次趋向于0时,这种对数跟踪过程一定收敛于一个纳什均衡点。一种可微同伦方法在文章[52]中被提出,这种方法是基于线性跟踪过程及对优化条件系统变量的非线性转化。基于Kohlberg和Mertens的框架理论,文章[53]组合了牛顿全局方法[54]和同伦方法[33]得到了一种计算纳什均衡的算法,关于同伦方法来计算纳什均衡的讨论可以在文章[55]中找到。
以上介绍的方法都只能找到一个纳什均衡点,实际中,一个博弈中通常具有多个纳什均衡点,如何有效的选择一个合适的均衡点,依然是个具有挑战的课题,这个选择过程通常需要计算一个博弈中所有的纳什均衡点。为了解决这个问题,下述文献中给出了一些计算法方法。文章[56]中给出了一种路径跟踪算法来计算双矩阵博弈问题的所有纳什均衡点,一种同伦算法[57]被用来计算多人博弈的所有均衡点,这两种方法都是基于一个多项式方程系统。对于多项式同伦连续方法计算所有纳什均衡点的调查可以在[58]中找到。文章[59]提出了一种混合整数规划的方法来计算双矩阵博弈的所有纳什均衡点。最近,通过枚举多面体所有端点,文章[60]开发了出两种方法来计算双矩阵博弈问题的所有均衡点。
作为混合策略纳什均衡问题的一个特例,纯策略纳什均衡问题最近也得到了不少关注。文章[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的迭代算法,并用这种分布式系统求解了三类经典的运筹学问题：求解纯策略纳什均衡点问题、市场分割问题和背包可行性问题。为了更好的比较计算结果,别的一些整数规划算法也用来求解同样的问题,数据显示我们的分布式方法具有很大的优越性。
A primary concern in applications of game theory is how to effectively select a Nash equilibrium, especially, a Nash equilibrium for a finite n-person game in normal form. This selection process often requires the computation of all Nash equilibria. It is well known that determining whether a finite game has a Nash equilibrium is an NP-hard problem and it is difficult to solve by naive enumeration algorithm. By exploiting the properties of pure strategy and multilinear terms in the payoff functions, this thesis begins by formulating a new mixed0-1linear program for computing all pure-strategy Nash equilibrium of finite n-person game in normal form. To our knowledge, it is the first method to formulate a mixed0-1linear programming for pure-strategy Nash equilibria and it may work well for other similar problems. Numerical results show that the approach is effective and this method can be easily distributed. For the mixed-strategy Nash equilibrium of a finite n-person game in normal form, multilinear terms appears in the payoff functions too. However, it is more difficult than the pure-strategy problem since the variables are0or1in pure-strategy cases and0to1in mixed-strategy cases. A good approximation of multilinear terms is introduced to fix this problem. Based on this approximation and the properties of mixed-strategy Nash equilibria, a mixed integer linear programming is obtained to find all mixed-strategy Nash equilibria of a finite n-person game in normal form.
In order to solve the integer programming effectively, a distributed implemen-tation of Dang and Ye's distributed fixed-point iterative method, which is a new al-ternative algorithm for integer programming, is also developed in this thesis. This fixed-point algorithm is derived from an increasing mapping which satisfies certain properties. Three classical problems, the problem of finding the pure-strategy Nash equilibria, the market split problem and the knapsack feasibility problem, are solved by this distributed implementation which is demonstrated by numerical results to be effective, with the potential for extension to other integer problems.
引文
[1]John F. Nash. Non-cooperative games. The Annals of Mathematics,54(2):286-295,1951.
[2]Antoine A. Cournot. Researches into the mathematical principles of the theory of wealth. New York:A. M. Kelley,1938;1960.
[3]John Von Neumann and Oskar Morgenstern. Theory of games and economic behavior, volume 60. Princeton University Press,1947.
[4]Reinhard Selten. Reexamination of the perfectness concept for equilibrium points in extensive games. International journal of game theory,4(1):25-55, 1975.
[5]Roger B. Myerson. Refinements of the nash equilibrium concept. International Journal of Game Theory,7(2):73-80,1978.
[6]John C. Harsanyi and Reinhard Selten. A general theory of equilibrium selection in games, volume 1. The MIT Press,1988.
[7]John Hillas and Elon Kohlberg. Foundations of strategic equilibrium. Handbook of Game Theory with Economic Applications,3:1597-1663,2002.
[8]Thomas C. Schelling. The strategy of conflict. Harvard University Press, 1960,1980.
[9]Shaun Hargreaves-Heap and Yanis Varoufakis. Game theory:A critical intro-duction. Routledge,2004.
[10]Robert D. Luce and Howard Raiffa. Games and decisions:Introduction and critical survey. Courier Dover Publications,1957.
[11]Brian Skyrms. The stag hunt and the evolution of social structure. Cambridge University Press,2004.
[12]Russell Cooper. Coordination games. Cambridge University Press,1999.
[13]John G. Wardrop. Road paper:some theoretical aspects of road traffic research. In ICE Proceedings:Engineering Divisions, volume 1, pages 325-362. Thomas Telford,1952.
[14]Paul R. Milgrom and Robert J. Weber. A theory of auctions and competitive bidding. Econometrica:Journal of the Econometric Society, pages 1089-1122, 1982.
[15]Susan Athey. Single crossing properties and the existence of pure strategy equi-libria in games of incomplete information. Econometrica,69(4):861-889,2001.
[16]Philip J. Reny and Shmuel Zamir. On the existence of purestrategy monotone equilibria in asymmetric first-price auctions. Econometrica,72(4):1105-1125, 2004.
[17]Hugh Ward. Game theory and the politics of global warming:The state of play and beyond. Political Studies,44(5):850-871,1996.
[18]P-A Chiappori, Steven Levitt, and Timothy Groseclose. Testing mixed-strategy equilibria when players are heterogeneous:the case of penalty kicks in soccer. American Economic Review, pages 1138-1151,2002.
[19]Gianni De Fraja, Tania Oliveira, and Luisa Zanchi. Must try harder:Evaluat-ing the role of effort in educational attainment. The Review of Economics and Statistics,92(3):577-597,2010.
[20]Constantinos Daskalakis and Christos H. Papadimitriou. Computing pure nash equilibria in graphical games via markov random fields. In Proceedings of the 7th ACM conference on Electronic commerce, pages 91-99. ACM,2006.
[21]Xi Chen and Xiaotie Deng. Settling the complexity of two-player nash equilib-rium. In Proceedings of the 47th Annual Symposium on Foundations of Com-puter Science (FOCS), pages 261-272,2006.
[22]Michael R Gary and David S Johnson. Computers and intractability:A guide to the theory of np-completeness. Freeman, San Francisco,1979.
[23]Chuangyin Dang. An increasing-mappingapping approach to integer program- ming based on lexicographic ordering and linear programming. In Proceedings of the 9th International Symposium on Operations Research and Its Applica-tions, pages 55-60,2010.
[24]Chuangyin Dang and Yinyu Ye. A fixed-point iterative approach to integer pro-gramming and distributed computation. City University of Hong Kong, TR-1, 2011.
[25]John F. Nash. Equilibrium points in n-person games. Proceedings of the Na-tional Academy of Sciences,36(1):48-49,1950.
[26]Carlton E. Lemke and Joseph T. Howson. Equilibrium points of bimatrix games. Journal of the Society for Industrial & Applied Mathematics,12(2):413-423, 1964.
[27]Noam Nisan. Algorithmic game theory. Cambridge University Press,2007.
[28]Rahul Savani and Bernhard Stengel. Hard-to-solve bimatrix games. Economet-rica,74(2):397-429,2006.
[29]Paul W. Goldberg, Christos H. Papadimitriou, and Rahul Savani. The complexity of the homotopy method, equilibrium selection, and lemke-howson solutions. ACM Transactions on Economics and Computation,1(2):9,2013.
[30]Robert Wilson. Computing equilibria of n-person games. SIAM Journal on Applied Mathematics,21(1):80-87,1971.
[31]Joachim Rosenmuller. On a generalization of the lemke-howson algorithm to noncooperative n-person games. SIAM Journal on Applied Mathematics,21(1): 73-79,1971.
[32]Herbert E. Scarf. The approximation of fixed points of a continuous mapping. SIAM Journal on Applied Mathematics,15(5):1328-1343,1967.
[33]B. Curtis Eaves. Homotopies for computation of fixed points. Mathematical Programming,3(1):1-22,1972.
[34]Michael J. Todd. The computation of fixed points and applications, volume 1. Springer-Verlag Berlin,1976.
[35]Gerardus Van der Laan and Adolphus J. J. Talman. A restart algorithm for com-puting fixed points without an extra dimension. Mathematical Programming,17 (1):74-84,1979.
[36]C. B. Garcia and Willard I. Zangwill. Pathways to solutions, fixed points, and equilibria. Englewood Cliffs:Prentice Hall,1981.
[37]Masakazu Kojima and Yoshitsugu Yamamoto. A unified approach to the imple-mentation of several restart fixed point algorithms and a new variable dimension algorithm. Mathematical Programming,28(3):288-328,1984.
[38]Chuangyin Dang. The D1-triangulation of Rn for simplicial algorithms for com-puting solutions of nonlinear equations. Mathematics of Operations Research, 16(1):148-161,1991.
[39]Eugene L. Allgower and Kurt Georg. Piecewise linear methods for nonlinear equations and optimization. Journal of Computational and Applied Mathemat-ics,124(1):245-261,2000.
[40]C. B. Garcia, C. E. Lemke, and H. Luethi. Simplicial approximation of an equi-librium point of noncooperative n-person games. Mathematical Programming, 4:227-260,1973.
[41]Go Van der Laan, A. J. J. Talman, and L. Van der Heyden. Simplicial variable dimension algorithms for solving the nonlinear complementarity problem on a product of unit simplices using a general labelling. Mathematics of Operations Research,12(3):377-397,1987.
[42]T. M. Doup and A. J. J. Talman. A new simplicial variable dimension algo-rithm to find equilibria on the product space of unit simplices. Mathematical Programming,37(3):319-355,1987.
[43]T. M. Doup and A. J. J. Talman. A continuous deformation algorithm on the product space of unit simplices. Mathematics of Operations Research,12(3): 485-521,1987.
[44]John C. Harsanyi. The tracing procedure:A bayesian approach to defining a solution for n-person noncooperative games. International Journal of Game Theory,4(2):61-94,1975.
[45]A. H. Van den Elzen and A. J. J Talman. A procedure for finding nash equilibria in bi-matrix games. Mathematical Methods of Operations Research,35(1):27-43,1991.
[46]Antoon Van den Elzen and Dolf Talman. An algorithmic approach toward the tracing procedure for bi-matrix games. Games and Economic Behavior,28(1): 130-145,1999.
[47]P. Jean J. Herings and Antoon Van den Elzen. Computation of the nash equilib-rium selected by the tracing procedure in n-person games. Games and Economic Behavior,38(1):89-117,2002.
[48]Richard D. McKelvey and Andrew McLennan. Computation of equilibria in finite games. Handbook of Computational Economics,1:87-142,1996.
[49]Bernhard Von Stengel. Computing equilibria for two-person games. Handbook of Game Theory with Economic Applications,3:1723-1759,2002.
[50]John C. Harsanyi. The tracing procedure:A bayesian approach to defining a solution forn-person noncooperative games. International Journal of Game Theory,4(2):61-94,1975.
[51]Stephen H. Schanuel, Leo K. Simon, and William R. Zame. The algebraic ge-ometry of games and the tracing procedure. Game Equilibrium Models,2:9-43, 1991.
[52]R Jean J. Herings and Ronald J. A.P. Peeters. A differentiable homotopy to compute nash equilibria of n-person games. Economic Theory,18(1):159-185, 2001.
[53]Srihari Govindan and Robert Wilson. A global newton method to compute nash equilibria. Journal of Economic Theory,110(1):65-86,2003.
[54]Steve Smale. A convergent process of price adjustment and global newton meth-ods. Journal of Mathematical Economics,3(2):107-120,1976.
[55]P. Jean J. Herings and Ronald J. A. P. Peeters. Homotopy methods to compute equilibria in game theory. Economic Theory,42(1):119-156,2010.
[56]M. M. Kosrnnva and L. A. Kinard. A differentiable homotopy approach for solv-ing polynomial optimization problems and noncooperative games. Computers & Mathematics with Applications,21 (6-7):135-143,1991.
[57]P. Jean-Jacques Herings and Ronald J. A. P. Peeters. A globally convergent algo-rithm to compute all nash equilibria for n-person games. Annals of Operations Research,137(1):349-368,2005.
[58]Ruchira S. Datta. Finding all nash equilibria of a finite game using polynomial algebra. Economic Theory,42(1):55-96,2010.
[59]Tuomas Sandholm, Andrew Gilpin, and Vincent Conitzer. Mixed-integer pro-gramming methods for finding nash equilibria. In Proceedings of the National Conference on Artificial Intelligence, pages 495-501,2005.
[60]David Avis, Gabriel D. Rosenberg, Rahul Savani, and Bernhard Von Stengel. Enumeration of nash equilibria for two-player games. Economic Theory,42(1): 9-37,2010.
[61]Georg Gottlob, Gianluigi Greco, and Francesco Scarcello. Pure nash equilibria: hard and easy games. In Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge, pages 215-230. ACM,2003.
[62]Min Jiang. Finding pure nash equilibrium of graphical game via constraints satisfaction approach. In Combinatorics, Algorithms, Probabilistic and Experi-mental Methodologies, pages 483-494. Springer,2007.
[63]Archie C. Chapman, Alessandro Farinelli, Enrique Munoz de Cote, Alex Rogers, and Nicholas R. Jennings. A distributed algorithm for optimising over pure strategy nash equilibria. In AAAI,2010.
[64]Georg Gottlob, Gianluigi Greco, and Toni Mancini. Complexity of pure equi-libria in bayesian games. In International Joint Conference On Artificial Intelli-gence, pages 1294-1299,2007.
[65]Archie C. Chapman. Control of large distributed systems using games with pure strategy Nash equilibria. PhD thesis, University of Southampton,2009.
[66]George Dantzig, Ray Fulkerson, and Selmer Johnson. Solution of a large-scale traveling-salesman problem. Journal of the Operations Research Society of America,2(4):393-410,1954.
[67]Ralph E. Gomory. Outline of an algorithm for integer solutions to linear pro-grams. Bulletin of the American Mathematical Society,64(5):275-278,1958.
[68]R. Gray Parker and Ronald L. Rardin. Discrete optimization. Academic Press Professional, Inc.,1988.
[69]G. L. Nemhauser, A. Rinnooy Kan, S. Graves, and P. Zipkin. Handbooks in operation research and management science. Optimization,1,1993.
[70]Ralph E. Gomory. Early integer programming. Operations Research,50(1): 78-81,2002.
[71]Manfred Padberg and Giovanni Rinaldi. A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM review, 33(1):60-100,1991.
[72]Hilary P. Williams. Model building in mathematical programming.1999.
[73]Egon Balas, Sebastian Ceria, Gerard Cornuejols, and N. Natraj. Gomory cuts revisited. Operations Research Letters,19(1):1-9,1996.
[74]James E. Kelley. The cutting-plane method for solving convex programs. Jour-nal of the Society for Industrial & Applied Mathematics,8(4):703-712,1960.
[75]Gerard Cornuejols. Valid inequalities for mixed integer linear programs. Math-ematical Programming,112(1):3-44,2008.
[76]Mordecai Avriel. Nonlinear programming:analysis and methods. Courier Dover Publications,2012.
[77]Ailsa H. Land and Alison G. Doig. An automatic method of solving discrete programming problems. Econometrica:Journal of the Econometric Society, pages 497-520,1960.
[78]Eugene L. Lawler and David E. Wood. Branch-and-bound methods:a survey. Operations Research,14(4):699-719,1966.
[79]Patrenahalli M. Narendra and Keinosuke Fukunaga. A branch and bound algo-rithm for feature subset selection. IEEE Transactions on Computers,100(9): 917-922,1977.
[80]M. D. Hendy and David Penny. Branch and bound algorithms to determine minimal evolutionary trees. Mathematical Biosciences,59(2):277-290,1982.
[81]Luc Jaulin. Applied interval analysis:with examples in parameter and state estimation, robust control and robotics, volume 1. Springer,2001.
[82]Manfred Padberg and Giovanni Rinaldi. A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM review, 33(l):60-100,1991.
[83]Herbert E. Scarf. Production sets with indivisibilities, part i:Generalities. Econometrica:Journal of the Econometric Society, pages 1-32,1981.
[84]Herbert E. Scarf. Neighborhood systems for production sets with indivisibilities. Econometrica:Journal of the Econometric Society, pages 507-532,1986.
[85]Hendrik W. Lenstra. Integer programming with a fixed number of variables. Mathematics of Operations Research,8(4):538-548,1983.
[86]Laszlo Lovasz and Herbert E. Scarf. The generalized basis reduction algorithm. Mathematics of Operations Research,17(3):751-764,1992.
[87]Chuangyin Dang and Hans Van Maaren. A simplicial approach to the determi-nation of an integer point of a simplex. Mathematics of Operations Research, 23(2):403-415,1998.
[88]Chuangyin Dang. An arbitrary starting homotopy-like simplicial algorithm for computing an integer point in a class of polytopes. SIAM Journal on Discrete Mathematics,23(2):609-633,2009.
[89]George L. Nemhauser and Laurence A. Wolsey. Integer and combinatorial op-timization, volume 18. Wiley New York,1988.
[90]Alexander I. Barvinok. A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. Mathematics of Operations Research, 19(4):769-779,1994.
[91]Gerard Cornuejols and Milind Dawande. A class of hard small 0-1 pro-grams. In Integer Programming and Combinatorial Optimization, pages 284-293. Springer,1998.
[92]Alexander Schrijver. Theory of linear and integer programming. John Wiley & Sons,1998.
[93]Dimitris Bertsimas and Robert Weismantel. Optimization over integers, volume 13. Dynamic Ideas Belmont,2005.
[94]Jesus A. De Loera, Raymond Hemmecke, Matthias Koppe, and Robert Weis-mantel. Integer polynomial optimization in fixed dimension. Mathematics of Operations Research,31(1):147-153,2006.
[95]Michael Junger, Thomas Liebling, Denis Naddef, George Nemhauser, William Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, and Laurence Wolsey.50 Years of Integer Programming 1958-2008. Springer, Berlin,2010.
[96]V. Bubelis. Relation of non-cooperative n-person games to three-person games. Contemporary Directions in Game Theory, pages 18-24,1976.
[97]V. Bubelis. On equilibria in finite games. International Journal of Game Theory, 8(2):65-79,1979.
[98]Faiz A. Al-Khayyal and James E. Falk. Jointly constrained biconvex program-ming. Mathematics of Operations Research,8(2):273-286,1983.
[99]James Luedtke, Mahdi Namazifar, and Jeff Linderoth. Some results on the strength of relaxations of multilinear functions. Mathematical Programming, 136(2):325-351,2012.
[100]V. Bubelis. A note on structure of equilibrium point in finite non-cooperative games. Mathematical Methods in Social Science,4:37-42,1974.
[101]David Gale, Harold W. Kuhn, and Albert W. Tucker. On symmetric games. Contributions to the Theory Games,1:81-87,1950.
[102]Garth P. McCormick. Computability of global solutions to factorable nonconvex programs:Parti-onvex underestimating problems. Mathematical Program-ming,10(1):147-175,1976.
[103]Nikolaos V. Sahinidis. Baron:A general purpose global optimization software package. Journal of Global Optimization,8(2):201-205,1996.
[104]Edward M. B. Smith and Constantinos C. Pantelides. A symbolic reformula-tion/spatial branch-and-bound algorithm for the global optimisation of noncon-vex minlps. Computers & Chemical Engineering,23(4):457-478,1999.
[105]Mohit Tawarmalani and Nikolaos V. Sahinidis. A polyhedral branch-and-cut approach to global optimization. Mathematical Programming,103(2):225-249, 2005.
[106]Pietro Belotti, Jon Lee, Leo Liberti, Francois Margot, and Andreas Wachter. Branching and bounds tightening techniques for non-convex minlp. Optimiza-tion Methods & Software,24(4-5):597-634,2009.
[107]Yves Crama. Concave extensions for nonlinear 0-1 maximization problems. Mathematical Programming,61(1-3):53-60,1993.
[108]James E. Falk and Karla R. Hoffman. A successive underestimation method for concave minimization problems. Mathematics of Operations Research,1(3): 251-259,1976.
[109]Hoang Tuy. Dc optimization:theory, methods and algorithms. In Handbook of Global Optimization, pages 149-216. Springer,1995.
[110]Anatoliy D. Rikun. A convex envelope formula for multilinear functions. Jour-nal of Global Optimization,10(4):425-437,1997.
[111]Hanif D. Sherali. Convex envelopes of multilinear functions over a unit hy-percube and over special discrete sets. Acta Mathematica Vietnamica,22(1): 245-270,1997.
[112]Hong S. Ryoo and Nikolaos V. Sahinidis. Analysis of bounds for multilinear functions. Journal of Global Optimization,19(4):403-424,2001.
[113]George B. Dantzig. Linear programming and extensions. Princeton University Press,1998.
[114]Yinyu Ye, Michael J. Todd, and Shinji Mizuno. An o (√nl)-iteration homoge-neous and self-dual linear programming algorithm. Mathematics of Operations Research, pages 53-67,1994.
[115]Yinyu Ye. Interior point algorithms:theory and analysis, volume 44. John Wiley & Sons,2011.
[116]Message Passing Interface Forum. MPI:A message-passing interface standard, version 2.2. http://www.mpiforum. org/docs/mpi-2.2/mpi22-report.pdf.,2009.
[117]Yuping Wang and Chuangyin Dang. An evolutionary algorithm for global opti-mization based on level-set evolution and latin squares. IEEE Transactions on Evolutionary Computation, 11(5):579-595,2007.
[118]Zhengtian Wu, Chuangyin Dang, Hamid Reza Karimi, Changan Zhu, and Qing Gao. A mixed 0-1 linear programming approach to the computation of all pure-strategy nash equilibria of a finite n-person game in normal form. Mathematical Problems in Engineering,2014,2014. In Press.
[119]Karen Aardal, Cor Hurkens, and Arjen K. Lenstra. Solving a linear diophantine equation with lower and upper bounds on the variables. In Integer Programming and Combinatorial Optimization, pages 229-242. Springer,1998.
[120]Karen Aardal, Robert E. Bixby, Cor A. J. Hurkens, Arjen K. Lenstra, and Job W. Smeltink. Market split and basis reduction:Towards a solution of the cornuejols-dawande instances. INFORMS Journal on Computing,12(3):192-202,2000.
[121]Alfred Wassermann. Attacking the market split problem with lattice point enu-meration. Journal of Combinatorial Optimization,6(1):5-16,2002.
[122]Heiko Vogel. Solving market split problems with heuristical lattice reduction. Annals of Operations Research,196(1):581-590,2012.
[123]M. Khorramizadeh. Numerical experiments with the Ⅲ-based hermite normal form algorithm for solving linear diophantine systems.Int. J. Contemp. Math. Sciences,7(13):599-613,2012.
[124]Arjen K. Lenstra, Hendrik W. Lenstra, and Laszlo Lovasz. Factoring polynomi-als with rational coefficients. Mathematische Annalen,261(4):515-534,1982.
[125]George B. Dantzig. Discrete-variable extremum problems. Operations Re-search,5(2):266-288,1957.
[2]Antoine A. Cournot. Researches into the mathematical principles of the theory of wealth. New York:A. M. Kelley,1938;1960.
[3]John Von Neumann and Oskar Morgenstern. Theory of games and economic behavior, volume 60. Princeton University Press,1947.
[4]Reinhard Selten. Reexamination of the perfectness concept for equilibrium points in extensive games. International journal of game theory,4(1):25-55, 1975.
[5]Roger B. Myerson. Refinements of the nash equilibrium concept. International Journal of Game Theory,7(2):73-80,1978.
[6]John C. Harsanyi and Reinhard Selten. A general theory of equilibrium selection in games, volume 1. The MIT Press,1988.
[7]John Hillas and Elon Kohlberg. Foundations of strategic equilibrium. Handbook of Game Theory with Economic Applications,3:1597-1663,2002.
[8]Thomas C. Schelling. The strategy of conflict. Harvard University Press, 1960,1980.
[9]Shaun Hargreaves-Heap and Yanis Varoufakis. Game theory:A critical intro-duction. Routledge,2004.
[10]Robert D. Luce and Howard Raiffa. Games and decisions:Introduction and critical survey. Courier Dover Publications,1957.
[11]Brian Skyrms. The stag hunt and the evolution of social structure. Cambridge University Press,2004.
[12]Russell Cooper. Coordination games. Cambridge University Press,1999.
[13]John G. Wardrop. Road paper:some theoretical aspects of road traffic research. In ICE Proceedings:Engineering Divisions, volume 1, pages 325-362. Thomas Telford,1952.
[14]Paul R. Milgrom and Robert J. Weber. A theory of auctions and competitive bidding. Econometrica:Journal of the Econometric Society, pages 1089-1122, 1982.
[15]Susan Athey. Single crossing properties and the existence of pure strategy equi-libria in games of incomplete information. Econometrica,69(4):861-889,2001.
[16]Philip J. Reny and Shmuel Zamir. On the existence of purestrategy monotone equilibria in asymmetric first-price auctions. Econometrica,72(4):1105-1125, 2004.
[17]Hugh Ward. Game theory and the politics of global warming:The state of play and beyond. Political Studies,44(5):850-871,1996.
[18]P-A Chiappori, Steven Levitt, and Timothy Groseclose. Testing mixed-strategy equilibria when players are heterogeneous:the case of penalty kicks in soccer. American Economic Review, pages 1138-1151,2002.
[19]Gianni De Fraja, Tania Oliveira, and Luisa Zanchi. Must try harder:Evaluat-ing the role of effort in educational attainment. The Review of Economics and Statistics,92(3):577-597,2010.
[20]Constantinos Daskalakis and Christos H. Papadimitriou. Computing pure nash equilibria in graphical games via markov random fields. In Proceedings of the 7th ACM conference on Electronic commerce, pages 91-99. ACM,2006.
[21]Xi Chen and Xiaotie Deng. Settling the complexity of two-player nash equilib-rium. In Proceedings of the 47th Annual Symposium on Foundations of Com-puter Science (FOCS), pages 261-272,2006.
[22]Michael R Gary and David S Johnson. Computers and intractability:A guide to the theory of np-completeness. Freeman, San Francisco,1979.
[23]Chuangyin Dang. An increasing-mappingapping approach to integer program- ming based on lexicographic ordering and linear programming. In Proceedings of the 9th International Symposium on Operations Research and Its Applica-tions, pages 55-60,2010.
[24]Chuangyin Dang and Yinyu Ye. A fixed-point iterative approach to integer pro-gramming and distributed computation. City University of Hong Kong, TR-1, 2011.
[25]John F. Nash. Equilibrium points in n-person games. Proceedings of the Na-tional Academy of Sciences,36(1):48-49,1950.
[26]Carlton E. Lemke and Joseph T. Howson. Equilibrium points of bimatrix games. Journal of the Society for Industrial & Applied Mathematics,12(2):413-423, 1964.
[27]Noam Nisan. Algorithmic game theory. Cambridge University Press,2007.
[28]Rahul Savani and Bernhard Stengel. Hard-to-solve bimatrix games. Economet-rica,74(2):397-429,2006.
[29]Paul W. Goldberg, Christos H. Papadimitriou, and Rahul Savani. The complexity of the homotopy method, equilibrium selection, and lemke-howson solutions. ACM Transactions on Economics and Computation,1(2):9,2013.
[30]Robert Wilson. Computing equilibria of n-person games. SIAM Journal on Applied Mathematics,21(1):80-87,1971.
[31]Joachim Rosenmuller. On a generalization of the lemke-howson algorithm to noncooperative n-person games. SIAM Journal on Applied Mathematics,21(1): 73-79,1971.
[32]Herbert E. Scarf. The approximation of fixed points of a continuous mapping. SIAM Journal on Applied Mathematics,15(5):1328-1343,1967.
[33]B. Curtis Eaves. Homotopies for computation of fixed points. Mathematical Programming,3(1):1-22,1972.
[34]Michael J. Todd. The computation of fixed points and applications, volume 1. Springer-Verlag Berlin,1976.
[35]Gerardus Van der Laan and Adolphus J. J. Talman. A restart algorithm for com-puting fixed points without an extra dimension. Mathematical Programming,17 (1):74-84,1979.
[36]C. B. Garcia and Willard I. Zangwill. Pathways to solutions, fixed points, and equilibria. Englewood Cliffs:Prentice Hall,1981.
[37]Masakazu Kojima and Yoshitsugu Yamamoto. A unified approach to the imple-mentation of several restart fixed point algorithms and a new variable dimension algorithm. Mathematical Programming,28(3):288-328,1984.
[38]Chuangyin Dang. The D1-triangulation of Rn for simplicial algorithms for com-puting solutions of nonlinear equations. Mathematics of Operations Research, 16(1):148-161,1991.
[39]Eugene L. Allgower and Kurt Georg. Piecewise linear methods for nonlinear equations and optimization. Journal of Computational and Applied Mathemat-ics,124(1):245-261,2000.
[40]C. B. Garcia, C. E. Lemke, and H. Luethi. Simplicial approximation of an equi-librium point of noncooperative n-person games. Mathematical Programming, 4:227-260,1973.
[41]Go Van der Laan, A. J. J. Talman, and L. Van der Heyden. Simplicial variable dimension algorithms for solving the nonlinear complementarity problem on a product of unit simplices using a general labelling. Mathematics of Operations Research,12(3):377-397,1987.
[42]T. M. Doup and A. J. J. Talman. A new simplicial variable dimension algo-rithm to find equilibria on the product space of unit simplices. Mathematical Programming,37(3):319-355,1987.
[43]T. M. Doup and A. J. J. Talman. A continuous deformation algorithm on the product space of unit simplices. Mathematics of Operations Research,12(3): 485-521,1987.
[44]John C. Harsanyi. The tracing procedure:A bayesian approach to defining a solution for n-person noncooperative games. International Journal of Game Theory,4(2):61-94,1975.
[45]A. H. Van den Elzen and A. J. J Talman. A procedure for finding nash equilibria in bi-matrix games. Mathematical Methods of Operations Research,35(1):27-43,1991.
[46]Antoon Van den Elzen and Dolf Talman. An algorithmic approach toward the tracing procedure for bi-matrix games. Games and Economic Behavior,28(1): 130-145,1999.
[47]P. Jean J. Herings and Antoon Van den Elzen. Computation of the nash equilib-rium selected by the tracing procedure in n-person games. Games and Economic Behavior,38(1):89-117,2002.
[48]Richard D. McKelvey and Andrew McLennan. Computation of equilibria in finite games. Handbook of Computational Economics,1:87-142,1996.
[49]Bernhard Von Stengel. Computing equilibria for two-person games. Handbook of Game Theory with Economic Applications,3:1723-1759,2002.
[50]John C. Harsanyi. The tracing procedure:A bayesian approach to defining a solution forn-person noncooperative games. International Journal of Game Theory,4(2):61-94,1975.
[51]Stephen H. Schanuel, Leo K. Simon, and William R. Zame. The algebraic ge-ometry of games and the tracing procedure. Game Equilibrium Models,2:9-43, 1991.
[52]R Jean J. Herings and Ronald J. A.P. Peeters. A differentiable homotopy to compute nash equilibria of n-person games. Economic Theory,18(1):159-185, 2001.
[53]Srihari Govindan and Robert Wilson. A global newton method to compute nash equilibria. Journal of Economic Theory,110(1):65-86,2003.
[54]Steve Smale. A convergent process of price adjustment and global newton meth-ods. Journal of Mathematical Economics,3(2):107-120,1976.
[55]P. Jean J. Herings and Ronald J. A. P. Peeters. Homotopy methods to compute equilibria in game theory. Economic Theory,42(1):119-156,2010.
[56]M. M. Kosrnnva and L. A. Kinard. A differentiable homotopy approach for solv-ing polynomial optimization problems and noncooperative games. Computers & Mathematics with Applications,21 (6-7):135-143,1991.
[57]P. Jean-Jacques Herings and Ronald J. A. P. Peeters. A globally convergent algo-rithm to compute all nash equilibria for n-person games. Annals of Operations Research,137(1):349-368,2005.
[58]Ruchira S. Datta. Finding all nash equilibria of a finite game using polynomial algebra. Economic Theory,42(1):55-96,2010.
[59]Tuomas Sandholm, Andrew Gilpin, and Vincent Conitzer. Mixed-integer pro-gramming methods for finding nash equilibria. In Proceedings of the National Conference on Artificial Intelligence, pages 495-501,2005.
[60]David Avis, Gabriel D. Rosenberg, Rahul Savani, and Bernhard Von Stengel. Enumeration of nash equilibria for two-player games. Economic Theory,42(1): 9-37,2010.
[61]Georg Gottlob, Gianluigi Greco, and Francesco Scarcello. Pure nash equilibria: hard and easy games. In Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge, pages 215-230. ACM,2003.
[62]Min Jiang. Finding pure nash equilibrium of graphical game via constraints satisfaction approach. In Combinatorics, Algorithms, Probabilistic and Experi-mental Methodologies, pages 483-494. Springer,2007.
[63]Archie C. Chapman, Alessandro Farinelli, Enrique Munoz de Cote, Alex Rogers, and Nicholas R. Jennings. A distributed algorithm for optimising over pure strategy nash equilibria. In AAAI,2010.
[64]Georg Gottlob, Gianluigi Greco, and Toni Mancini. Complexity of pure equi-libria in bayesian games. In International Joint Conference On Artificial Intelli-gence, pages 1294-1299,2007.
[65]Archie C. Chapman. Control of large distributed systems using games with pure strategy Nash equilibria. PhD thesis, University of Southampton,2009.
[66]George Dantzig, Ray Fulkerson, and Selmer Johnson. Solution of a large-scale traveling-salesman problem. Journal of the Operations Research Society of America,2(4):393-410,1954.
[67]Ralph E. Gomory. Outline of an algorithm for integer solutions to linear pro-grams. Bulletin of the American Mathematical Society,64(5):275-278,1958.
[68]R. Gray Parker and Ronald L. Rardin. Discrete optimization. Academic Press Professional, Inc.,1988.
[69]G. L. Nemhauser, A. Rinnooy Kan, S. Graves, and P. Zipkin. Handbooks in operation research and management science. Optimization,1,1993.
[70]Ralph E. Gomory. Early integer programming. Operations Research,50(1): 78-81,2002.
[71]Manfred Padberg and Giovanni Rinaldi. A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM review, 33(1):60-100,1991.
[72]Hilary P. Williams. Model building in mathematical programming.1999.
[73]Egon Balas, Sebastian Ceria, Gerard Cornuejols, and N. Natraj. Gomory cuts revisited. Operations Research Letters,19(1):1-9,1996.
[74]James E. Kelley. The cutting-plane method for solving convex programs. Jour-nal of the Society for Industrial & Applied Mathematics,8(4):703-712,1960.
[75]Gerard Cornuejols. Valid inequalities for mixed integer linear programs. Math-ematical Programming,112(1):3-44,2008.
[76]Mordecai Avriel. Nonlinear programming:analysis and methods. Courier Dover Publications,2012.
[77]Ailsa H. Land and Alison G. Doig. An automatic method of solving discrete programming problems. Econometrica:Journal of the Econometric Society, pages 497-520,1960.
[78]Eugene L. Lawler and David E. Wood. Branch-and-bound methods:a survey. Operations Research,14(4):699-719,1966.
[79]Patrenahalli M. Narendra and Keinosuke Fukunaga. A branch and bound algo-rithm for feature subset selection. IEEE Transactions on Computers,100(9): 917-922,1977.
[80]M. D. Hendy and David Penny. Branch and bound algorithms to determine minimal evolutionary trees. Mathematical Biosciences,59(2):277-290,1982.
[81]Luc Jaulin. Applied interval analysis:with examples in parameter and state estimation, robust control and robotics, volume 1. Springer,2001.
[82]Manfred Padberg and Giovanni Rinaldi. A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM review, 33(l):60-100,1991.
[83]Herbert E. Scarf. Production sets with indivisibilities, part i:Generalities. Econometrica:Journal of the Econometric Society, pages 1-32,1981.
[84]Herbert E. Scarf. Neighborhood systems for production sets with indivisibilities. Econometrica:Journal of the Econometric Society, pages 507-532,1986.
[85]Hendrik W. Lenstra. Integer programming with a fixed number of variables. Mathematics of Operations Research,8(4):538-548,1983.
[86]Laszlo Lovasz and Herbert E. Scarf. The generalized basis reduction algorithm. Mathematics of Operations Research,17(3):751-764,1992.
[87]Chuangyin Dang and Hans Van Maaren. A simplicial approach to the determi-nation of an integer point of a simplex. Mathematics of Operations Research, 23(2):403-415,1998.
[88]Chuangyin Dang. An arbitrary starting homotopy-like simplicial algorithm for computing an integer point in a class of polytopes. SIAM Journal on Discrete Mathematics,23(2):609-633,2009.
[89]George L. Nemhauser and Laurence A. Wolsey. Integer and combinatorial op-timization, volume 18. Wiley New York,1988.
[90]Alexander I. Barvinok. A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. Mathematics of Operations Research, 19(4):769-779,1994.
[91]Gerard Cornuejols and Milind Dawande. A class of hard small 0-1 pro-grams. In Integer Programming and Combinatorial Optimization, pages 284-293. Springer,1998.
[92]Alexander Schrijver. Theory of linear and integer programming. John Wiley & Sons,1998.
[93]Dimitris Bertsimas and Robert Weismantel. Optimization over integers, volume 13. Dynamic Ideas Belmont,2005.
[94]Jesus A. De Loera, Raymond Hemmecke, Matthias Koppe, and Robert Weis-mantel. Integer polynomial optimization in fixed dimension. Mathematics of Operations Research,31(1):147-153,2006.
[95]Michael Junger, Thomas Liebling, Denis Naddef, George Nemhauser, William Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, and Laurence Wolsey.50 Years of Integer Programming 1958-2008. Springer, Berlin,2010.
[96]V. Bubelis. Relation of non-cooperative n-person games to three-person games. Contemporary Directions in Game Theory, pages 18-24,1976.
[97]V. Bubelis. On equilibria in finite games. International Journal of Game Theory, 8(2):65-79,1979.
[98]Faiz A. Al-Khayyal and James E. Falk. Jointly constrained biconvex program-ming. Mathematics of Operations Research,8(2):273-286,1983.
[99]James Luedtke, Mahdi Namazifar, and Jeff Linderoth. Some results on the strength of relaxations of multilinear functions. Mathematical Programming, 136(2):325-351,2012.
[100]V. Bubelis. A note on structure of equilibrium point in finite non-cooperative games. Mathematical Methods in Social Science,4:37-42,1974.
[101]David Gale, Harold W. Kuhn, and Albert W. Tucker. On symmetric games. Contributions to the Theory Games,1:81-87,1950.
[102]Garth P. McCormick. Computability of global solutions to factorable nonconvex programs:Parti-onvex underestimating problems. Mathematical Program-ming,10(1):147-175,1976.
[103]Nikolaos V. Sahinidis. Baron:A general purpose global optimization software package. Journal of Global Optimization,8(2):201-205,1996.
[104]Edward M. B. Smith and Constantinos C. Pantelides. A symbolic reformula-tion/spatial branch-and-bound algorithm for the global optimisation of noncon-vex minlps. Computers & Chemical Engineering,23(4):457-478,1999.
[105]Mohit Tawarmalani and Nikolaos V. Sahinidis. A polyhedral branch-and-cut approach to global optimization. Mathematical Programming,103(2):225-249, 2005.
[106]Pietro Belotti, Jon Lee, Leo Liberti, Francois Margot, and Andreas Wachter. Branching and bounds tightening techniques for non-convex minlp. Optimiza-tion Methods & Software,24(4-5):597-634,2009.
[107]Yves Crama. Concave extensions for nonlinear 0-1 maximization problems. Mathematical Programming,61(1-3):53-60,1993.
[108]James E. Falk and Karla R. Hoffman. A successive underestimation method for concave minimization problems. Mathematics of Operations Research,1(3): 251-259,1976.
[109]Hoang Tuy. Dc optimization:theory, methods and algorithms. In Handbook of Global Optimization, pages 149-216. Springer,1995.
[110]Anatoliy D. Rikun. A convex envelope formula for multilinear functions. Jour-nal of Global Optimization,10(4):425-437,1997.
[111]Hanif D. Sherali. Convex envelopes of multilinear functions over a unit hy-percube and over special discrete sets. Acta Mathematica Vietnamica,22(1): 245-270,1997.
[112]Hong S. Ryoo and Nikolaos V. Sahinidis. Analysis of bounds for multilinear functions. Journal of Global Optimization,19(4):403-424,2001.
[113]George B. Dantzig. Linear programming and extensions. Princeton University Press,1998.
[114]Yinyu Ye, Michael J. Todd, and Shinji Mizuno. An o (√nl)-iteration homoge-neous and self-dual linear programming algorithm. Mathematics of Operations Research, pages 53-67,1994.
[115]Yinyu Ye. Interior point algorithms:theory and analysis, volume 44. John Wiley & Sons,2011.
[116]Message Passing Interface Forum. MPI:A message-passing interface standard, version 2.2. http://www.mpiforum. org/docs/mpi-2.2/mpi22-report.pdf.,2009.
[117]Yuping Wang and Chuangyin Dang. An evolutionary algorithm for global opti-mization based on level-set evolution and latin squares. IEEE Transactions on Evolutionary Computation, 11(5):579-595,2007.
[118]Zhengtian Wu, Chuangyin Dang, Hamid Reza Karimi, Changan Zhu, and Qing Gao. A mixed 0-1 linear programming approach to the computation of all pure-strategy nash equilibria of a finite n-person game in normal form. Mathematical Problems in Engineering,2014,2014. In Press.
[119]Karen Aardal, Cor Hurkens, and Arjen K. Lenstra. Solving a linear diophantine equation with lower and upper bounds on the variables. In Integer Programming and Combinatorial Optimization, pages 229-242. Springer,1998.
[120]Karen Aardal, Robert E. Bixby, Cor A. J. Hurkens, Arjen K. Lenstra, and Job W. Smeltink. Market split and basis reduction:Towards a solution of the cornuejols-dawande instances. INFORMS Journal on Computing,12(3):192-202,2000.
[121]Alfred Wassermann. Attacking the market split problem with lattice point enu-meration. Journal of Combinatorial Optimization,6(1):5-16,2002.
[122]Heiko Vogel. Solving market split problems with heuristical lattice reduction. Annals of Operations Research,196(1):581-590,2012.
[123]M. Khorramizadeh. Numerical experiments with the Ⅲ-based hermite normal form algorithm for solving linear diophantine systems.Int. J. Contemp. Math. Sciences,7(13):599-613,2012.
[124]Arjen K. Lenstra, Hendrik W. Lenstra, and Laszlo Lovasz. Factoring polynomi-als with rational coefficients. Mathematische Annalen,261(4):515-534,1982.
[125]George B. Dantzig. Discrete-variable extremum problems. Operations Re-search,5(2):266-288,1957.