一种求解二人序贯博弈均衡的新算法  

New algorithm for solving equilibria of two-player sequential games

作　　者：黄武军[1] 吴启迪[1,2] 杨继君[1] 冯云生[1] 许维胜[2] 

机构地区：[1]同济大学经济与管理学院,上海201804 [2]同济大学电子与信息工程学院,上海201804

出　　处：《计算机工程与应用》2009年第27期39-42,共4页Computer Engineering and Applications

基　　金：国家自然科学基金No.70871091;No.70640007~~

摘　　要：虽然线性规划方法处理正规型零和博弈均衡问题有其独特的优点,但对零和序贯博弈均衡问题的求解却无能为力,而常用的逆向归纳法求解该类问题也有其固有的不足。鉴于上述原因,首先在序贯型博弈中定义了行动序列和实现概率等概念并给出相关定理。在此基础上,结合线性规划的思想,推出了求解二人零和序贯博弈均衡的新算法。该算法的目的是把序贯型博弈纳什均衡求解问题转化为线性规划问题,然后通过使用现成的线性规划软件(比如LINDO/LINGO软件)进行求解。该算法对解决该类问题提供了新的途径,具有一定的理论价值和实用价值。最后的算例对比分析说明了算法的可行性和有效性。Although the linear programming approach to the zero-sum games of normal form has its unique advantages,it is powerless to solve the equilibria of zero-sum sequential games.And the commonly used method of such backward induction has its inherent shortcomings.For these reasons,first of all,the definitions of the aetion sequence and realization probability and related theorems are introduced.On this basis,combining linear programming ideas,the new algorithm for solving the equilibria of twoplayer and zero-sum sequential games is deduced.The ultimate goal of the algorithm is to transfer the eqnilibria of sequential games into the linear program,and it is very easy to solve the equilibria of games through using readymade linear programming software such as LINDO/LINGO software.Therefore the proposed method to easily solve such problems has the theoretical value and practical value.Finally,an example of comparative analysis shows that the proposed method is effective and feasible.

关 键 词：二人序贯博弈 行动序列 实现概率 线性规划 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]