On the complexity of two-player win-lose games

被引：36

作者：

Abbott, T ^{[1
]}

Kane, D ^{[1
]}

Valiant, P ^{[1
]}

机构：

[1] MIT, Comp Sci & Artificial Intelligence Lab, Stata Ctr, Cambridge, MA 02139 USA

来源：

46th Annual IEEE Symposium on Foundations of Computer Science, Proceedings | 2005年

关键词：

D O I：

10.1109/SFCS.2005.59

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The efficient computation of Nash equilibria is one of the most formidable challenges in computational complexity today. The problem remains open for two-player games. We show that the complexity of two-player Nash equilibria is unchanged when all outcomes are restricted to be 0 or 1. That is, win-or-lose games are as complex as the general case for two-player games.

引用

页码：113 / 122

页数：10

共 12 条

[1]

[Anonymous], STOC 01

[2] On the computational complexity of Nash equilibria for (0,1) bimatrix games [J].

Codenotti, B ;

Stefankovic, D .

INFORMATION PROCESSING LETTERS, 2005, 94 (03) :145-150

[3]

CONITZER V, 2003, IJCAI 2003, P765

[4]

GILBOA I, 1989, GAMES EC BEHAV

[5]

KOLLER D, 1995, INT J GAME THEORY

[6] EQUILIBRIUM POINTS OF BIMATRIX GAMES [J].

LEMKE, CE ;

HOWSON, JT .

JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS, 1964, 12 (02) :413-423

[7]

PAPADIMITRIOU C, 2005, STOC, P49

[8]

PAPADIMITRIOU CH, 2005, SODA

[9]

SAVANI R, 2004, FOCS, P258

[10]

SCHOENEBECK G, TR05052 ECCC

← 1 2 →