Efficient Decomposition of Bimatrix Games (Extended Abstract)

被引：1

作者：

Jiang, Xiang ^{[1
]}

Pauly, Arno ^{[1
]}

机构：

[1] Univ Cambridge, Comp Lab, Cambridge, England

来源：

ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE | 2014年 / 146期

关键词：

D O I：

10.4204/EPTCS.146.10

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Exploiting the algebraic structure of the set of bimatrix games, a divide-and-conquer algorithm for finding Nash equilibria is proposed. The algorithm is fixed-parameter tractable with the size of the largest irreducible component of a game as parameter. An implementation of the algorithm is shown to yield a significant performance increase on inputs with small parameters.

引用

页码：75 / 81

页数：7

共 24 条

[1]

Blackwell D., 1969, ZASTOWANIA MATEMATYK

[2] On the Complexity of Iterated Weak Dominance in Constant-Sum Games [J].

Brandt, Felix ;

Brill, Markus ;

Fischer, Felix ;

Harrenstein, Paul .

THEORY OF COMPUTING SYSTEMS, 2011, 49 (01) :162-181

[3]

Brattka Vasco, 2012, How the World Computes.Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, P56, DOI 10.1007/978-3-642-30870-3_7

[4] Closed choice and a Uniform Low Basis Theorem [J].