二人博弈问题中单一纳什均衡的搜索算法

二人博弈问题中单一纳什均衡的搜索算法

孙舒杨, 刘大有, 孙成敏

吉林大学计算机科学与技术学院, 长春 130012; 吉林大学符号计算与知识工程教育部重点实验室, 长春 130012

收稿日期:2005-04-28 修回日期:1900-01-01 出版日期:2006-05-26 发布日期:2006-05-26
通讯作者: 孙舒杨

A Search Method for Finding a Simple Nash Equilibrium in Twoplayer Games

SUN Shu-yang, LIU Da-you, SUN Cheng-min

College of Computer Science and Technology, Jilin University, Changchun 130012, China; Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China

Received:2005-04-28 Revised:1900-01-01 Online:2006-05-26 Published:2006-05-26
Contact: SUN Shu-yang

摘要/Abstract

摘要： 给出计算二人博弈问题中单一纳什均衡的一种搜索算法, 用支付矩阵的秩数和条件占优行的个数限定待搜索策略对空间, 将该空间按一定规则排序, 通过对有序有限策略对空间进行搜索得到一个简单的纳什均衡.

关键词: 二人博弈, 纳什均衡, 支撑集, 条件占优策略

Abstract: Nash Equilibria computing is one of the most important problems in noncooperative games. In this paper, we give a searching algorithm for finding a simple Nash equilibrium in twoplayer games. We limit the searching strategy space according to rank and the conditionally dominant rows of the payoff matrix, order the space, and seach the limited and ordered strategy space for finding a simple Nash equilibrium.

Key words: twoplayer games, Nash equilibrium, support set, conditionally dominant

中图分类号:

TP301.4

孙舒杨, 刘大有, 孙成敏. 二人博弈问题中单一纳什均衡的搜索算法[J]. J4, 2006, 44(03): 418-420.

SUN Shu-yang, LIU Da-you, SUN Cheng-min. A Search Method for Finding a Simple Nash Equilibrium in Twoplayer Games[J]. J4, 2006, 44(03): 418-420.