On the NP-Completeness of Finding an Optimal Strategy in Games with Common Payoffs

Given a finite game with common payoffs (i.e. the players have completely common interests), we show that the problem of determining whether there exists a joint strategy where each player nets at least k is NP-complete.

MoreLess

Year of publication:	2000-11-22
Authors:	Chu, Francis C. ; Halpern, Joseph Y.
Institutions:	EconWPA
Subject:	common payoff games \| NP-completeness

More details

Extent:	application/pdf
Series:	Game Theory and Information.
Type of publication:	Book / Working Paper
Notes:	Type of Document - PDF; prepared on Unix; pages: 7; figures: included 7 pages
Classification:	C70 - Game Theory and Bargaining Theory. General ; C80 - Data Collection and Data Estimation Methodology; Computer Programs. General
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10005118639