QQ客服 官方微博 反馈留言

	Settling the complexity of computing two-player Nash equilibria
	Xi Chen ; Xiaotie Deng ; Shang-hua Teng
	2010-10-12 ; 2010-10-12
关键词	Bibliography Theoretical or Mathematical/ computability computational complexity game theory randomised algorithms/ two-player Nash equilibrium polynomial parity argument PPAD complexity algorithmic game theory randomized polynomial time solvability BIMATRIX/ C1140E Game theory C4240C Computational complexity
中文摘要	We prove that BIMATRIX, the problem of finding a Nash equilibrium in a two-player game, is complete for the complexity class PPAD (polynomial parity argument, directed version) introduced by Papadimitriou in 1991. Our result, building upon the work of Daskalakis et al. (2006) on the complexity of four-player Nash equilibria, settles a long standing open problem in algorithmic game theory. It also serves as a starting point for a series of results concerning the complexity of two-player Nash equilibria. In particular, we prove the following theorems: i) BIMATRIX does not have a fully polynomial-time approximation scheme unless every problem in PPAD is solvable in polynomial time. ii) The smoothed complexity of the classic Lemke-Howson algorithm and, in fact, of any algorithm for BIMATRIX is not polynomial unless every problem in PPAD is solvable in randomized polynomial time. Our results also have a complexity implication in mathematical economics: Arrow-Debreu market equilibria are PPAD-hard to compute.
语种	英语
出版者	ACM ; USA
内容类型	期刊论文
源URL	[http://hdl.handle.net/123456789/78676]
专题	清华大学
推荐引用方式 GB/T 7714	Xi Chen,Xiaotie Deng,Shang-hua Teng. Settling the complexity of computing two-player Nash equilibria[J],2010, 2010.
APA	Xi Chen,Xiaotie Deng,&Shang-hua Teng.(2010).Settling the complexity of computing two-player Nash equilibria..
MLA	Xi Chen,et al."Settling the complexity of computing two-player Nash equilibria".(2010).

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。