Single parameter FPT-algorithms for non-trivial games

V. Estivill-Castro; M. Parsa

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

Single parameter FPT-algorithms for non-trivial games

V. Estivill-Castro, M. Parsa

Management Science

Research output: Chapter in Book/Report/Conference proceeding › Chapter (peer-reviewed) › peer-review

4 Citations (Scopus)

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
Subtitle of host publication	21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010. Revised Selected Papers
Editors	Costas S. Iliopoulos, William F. Smyth
Publisher	Springer
Pages	121-124
Number of pages	4
ISBN (Print)	9783642192210
DOIs	https://doi.org/10.1007/978-3-642-19222-7_13
Publication status	Published - 2011
Event	21st International Workshop, IWOCA 2010 - London, United Kingdom Duration: 26 Jul 2010 → 28 Jul 2010

Publication series

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

Conference

Conference	21st International Workshop, IWOCA 2010
Country/Territory	United Kingdom
City	London
Period	26/07/10 → 28/07/10

Keywords

algorithmic game theory
computational complexity
combinational algorithms
discrete mathematics
data structures
coding
information theory

Access to Document

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

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: 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010. Revised Selected Papers (pp. 121-124). (Lecture Notes in Computer Science; Vol. 6460). Springer. https://doi.org/10.1007/978-3-642-19222-7_13

@inbook{074f793c96ce48e9929d278f45cce0cd,

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

keywords = "algorithmic game theory , computational complexity, combinational algorithms, discrete mathematics, data structures, coding, information theory",

author = "V. Estivill-Castro and M. Parsa",

year = "2011",

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

language = "English",

isbn = "9783642192210",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "121--124",

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

booktitle = "Combinatorial Algorithms",

note = "21st International Workshop, IWOCA 2010 ; Conference date: 26-07-2010 Through 28-07-2010",

}

Estivill-Castro, V & Parsa, M 2011, Single parameter FPT-algorithms for non-trivial games. in CS Iliopoulos & WF Smyth (eds), Combinatorial Algorithms: 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010. Revised Selected Papers. Lecture Notes in Computer Science, vol. 6460, Springer, pp. 121-124, 21st International Workshop, IWOCA 2010, London, United Kingdom, 26/07/10. https://doi.org/10.1007/978-3-642-19222-7_13

Single parameter FPT-algorithms for non-trivial games. / Estivill-Castro, V.; Parsa, M.
Combinatorial Algorithms: 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010. Revised Selected Papers. ed. / Costas S. Iliopoulos; William F. Smyth. Springer, 2011. p. 121-124 (Lecture Notes in Computer Science; Vol. 6460).

Research output: Chapter in Book/Report/Conference proceeding › Chapter (peer-reviewed) › peer-review

TY - CHAP

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

AU - Estivill-Castro, V.

AU - Parsa, M.

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.

KW - algorithmic game theory

KW - computational complexity

KW - combinational algorithms

KW - discrete mathematics

KW - data structures

KW - coding

KW - information theory

UR - http://www.scopus.com/inward/record.url?eid=2-s2.0-79953223726&partnerID=40&md5=27f24a7a89db8dc4dcbef3fa07f0e3bb

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

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

M3 - Chapter (peer-reviewed)

SN - 9783642192210

T3 - Lecture Notes in Computer Science

SP - 121

EP - 124

BT - Combinatorial Algorithms

A2 - Iliopoulos, Costas S.

A2 - Smyth, William F.

PB - Springer

T2 - 21st International Workshop, IWOCA 2010

Y2 - 26 July 2010 through 28 July 2010

ER -

Single parameter FPT-algorithms for non-trivial games

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this