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 › peer-review

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/Territory	United Kingdom
City	London
Period	26/07/10 → 28/07/10

Access to Document

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

Cite this

@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",

note = "International Workshop on Combinatorial Algorithms, IWOCA 2010 ; Conference date: 26-07-2010 Through 28-07-2010",

}

Single parameter FPT-algorithms for non-trivial games. / Estivill-Castro, Vladimir; Parsa, Mahdi.

Combinatorial Algorithms. ed. / Costas S. Iliopoulos; William F. Smyth. Springer Berlin, 2011. p. 121-124 (Lecture Notes in Computer Science; Vol. 6460).

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

TY - GEN

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

AU - Estivill-Castro, Vladimir

AU - Parsa, Mahdi

N1 - Conference code: 21st

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

T2 - International Workshop on Combinatorial Algorithms

Y2 - 26 July 2010 through 28 July 2010

ER -

Single parameter FPT-algorithms for non-trivial games

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this