Single parameter FPT-algorithms for non-trivial games

Vladimir Estivill-Castro; Mahdi Parsa

doi:10.1007/978-3-642-19222-7_13

Single parameter FPT-algorithms for non-trivial games

Vladimir Estivill-Castro, Mahdi Parsa

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings

Abstract

We know that k -Uniform Nash is W[2]-Complete when we consider imitation symmetric win-lose games (with k as the parameter) even when we have two players. However, this paper provides positive results regarding Nash equilibria. We show that consideration of sparse games or limitations of the support result in fixed-parameter algorithms with respect to one parameter only for the k -Uniform Nash problem. That is, we show that a sample uniform Nash equilibrium in r-sparse imitation symmetric win-lose games is not as hard because it can be found in FPT time (i.e polynomial in the size of the game, but maybe exponential in r). Moreover, we show that, although NP-Complete, the problem of Best Nash Equilibrium is also fix-parameter tractable.

Original language	English
Title of host publication	Combinatorial Algorithms
Editors	Costas S. Iliopoulos, William F. Smyth
Publisher	Springer Berlin
Pages	121-124
Number of pages	4
ISBN (Electronic)	978-3-642-19222-7
ISBN (Print)	978-3-642-19221-0
DOIs	https://doi.org/10.1007/978-3-642-19222-7_13
Publication status	Published - 2011
Externally published	Yes
Event	International Workshop on Combinatorial Algorithms - London, United Kingdom Duration: 26 Jul 2010 → 28 Jul 2010 Conference number: 21st

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	6460
ISSN (Print)	0302-9743

Conference

Conference	International Workshop on Combinatorial Algorithms
Abbreviated title	IWOCA 2010
Country	United Kingdom
City	London
Period	26/07/10 → 28/07/10

Fingerprint

Cite this

Estivill-Castro, V., & Parsa, M. (2011). Single parameter FPT-algorithms for non-trivial games. In C. S. Iliopoulos, & W. F. Smyth (Eds.), Combinatorial Algorithms (pp. 121-124). (Lecture Notes in Computer Science; Vol. 6460). Springer Berlin. https://doi.org/10.1007/978-3-642-19222-7_13

@inproceedings{625187130b034444b73ab9a413726b48,

title = "Single parameter FPT-algorithms for non-trivial games",

abstract = "We know that k -Uniform Nash is W[2]-Complete when we consider imitation symmetric win-lose games (with k as the parameter) even when we have two players. However, this paper provides positive results regarding Nash equilibria. We show that consideration of sparse games or limitations of the support result in fixed-parameter algorithms with respect to one parameter only for the k -Uniform Nash problem. That is, we show that a sample uniform Nash equilibrium in r-sparse imitation symmetric win-lose games is not as hard because it can be found in FPT time (i.e polynomial in the size of the game, but maybe exponential in r). Moreover, we show that, although NP-Complete, the problem of Best Nash Equilibrium is also fix-parameter tractable.",

author = "Vladimir Estivill-Castro and Mahdi Parsa",

year = "2011",

doi = "10.1007/978-3-642-19222-7_13",

language = "English",

isbn = "978-3-642-19221-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin",

pages = "121--124",

editor = "Iliopoulos, {Costas S.} and Smyth, {William F.}",

booktitle = "Combinatorial Algorithms",

address = "Germany",

}

TY - GEN

T1 - Single parameter FPT-algorithms for non-trivial games

AU - Estivill-Castro, Vladimir

AU - Parsa, Mahdi

PY - 2011

Y1 - 2011

N2 - We know that k -Uniform Nash is W[2]-Complete when we consider imitation symmetric win-lose games (with k as the parameter) even when we have two players. However, this paper provides positive results regarding Nash equilibria. We show that consideration of sparse games or limitations of the support result in fixed-parameter algorithms with respect to one parameter only for the k -Uniform Nash problem. That is, we show that a sample uniform Nash equilibrium in r-sparse imitation symmetric win-lose games is not as hard because it can be found in FPT time (i.e polynomial in the size of the game, but maybe exponential in r). Moreover, we show that, although NP-Complete, the problem of Best Nash Equilibrium is also fix-parameter tractable.

AB - We know that k -Uniform Nash is W[2]-Complete when we consider imitation symmetric win-lose games (with k as the parameter) even when we have two players. However, this paper provides positive results regarding Nash equilibria. We show that consideration of sparse games or limitations of the support result in fixed-parameter algorithms with respect to one parameter only for the k -Uniform Nash problem. That is, we show that a sample uniform Nash equilibrium in r-sparse imitation symmetric win-lose games is not as hard because it can be found in FPT time (i.e polynomial in the size of the game, but maybe exponential in r). Moreover, we show that, although NP-Complete, the problem of Best Nash Equilibrium is also fix-parameter tractable.

UR - http://www.scopus.com/inward/record.url?scp=79953223726&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-19222-7_13

DO - 10.1007/978-3-642-19222-7_13

M3 - Conference Paper published in Proceedings

SN - 978-3-642-19221-0

T3 - Lecture Notes in Computer Science

SP - 121

EP - 124

BT - Combinatorial Algorithms

A2 - Iliopoulos, Costas S.

A2 - Smyth, William F.

PB - Springer Berlin

ER -

Access to Document

10.1007/978-3-642-19222-7_13

Link to publication in Scopus