Parameterized Complexity Applied in Algorithmic Game Theory

Mahdi Parsa

Research output: ThesisDoctoral Thesis

Abstract

The modern mathematical treatment of the study of decisions taken by participants whose interests are in conflict is now generally labeled as “game theory”. To understand these interactions the theory provides some solution concepts. An important such a concept is the notion of Nash equilibrium, which provides a way of predicting the behavior of strategic participants in situations of conflicts. However, many decision problems regarding to the computation of Nash equilibrium are computationally hard. Motivated by these hardness results, we study the parameterized complexity of the Nash equilibrium. In parameterized complexity one considers computational problems in a twodimensional setting: the first dimension is the usual input size n, the second dimension is a positive integer k, the parameter. A problem is fixed-parameter tractable (FPT) if it can be solved in time f(k)nO(1) where f denotes a computable, possibly exponential, function. We show that some decision problems regarding to the computation of Nash equilibrium are hard even in parameterized complexity theory. However, we provide FPT algorithms for some other problems relevant to the computation of Nash equilibrium.
Original languageEnglish
Award date8 Nov 2011
Place of PublicationSouthport, Queensland, Australia
Publication statusPublished - 2011

Fingerprint

Nash equilibrium
Game theory
Solution concepts
Complexity theory
Integer
Interaction

Keywords

  • game theory
  • decision support techniques
  • Nash equilibrium

Cite this

Parsa, M. (2011). Parameterized Complexity Applied in Algorithmic Game Theory. Southport, Queensland, Australia.
Parsa, Mahdi. / Parameterized Complexity Applied in Algorithmic Game Theory. Southport, Queensland, Australia, 2011. 113 p.
@phdthesis{3ef020783b5b4724ba65ed752efa1bb1,
title = "Parameterized Complexity Applied in Algorithmic Game Theory",
abstract = "The modern mathematical treatment of the study of decisions taken by participants whose interests are in conflict is now generally labeled as “game theory”. To understand these interactions the theory provides some solution concepts. An important such a concept is the notion of Nash equilibrium, which provides a way of predicting the behavior of strategic participants in situations of conflicts. However, many decision problems regarding to the computation of Nash equilibrium are computationally hard. Motivated by these hardness results, we study the parameterized complexity of the Nash equilibrium. In parameterized complexity one considers computational problems in a twodimensional setting: the first dimension is the usual input size n, the second dimension is a positive integer k, the parameter. A problem is fixed-parameter tractable (FPT) if it can be solved in time f(k)nO(1) where f denotes a computable, possibly exponential, function. We show that some decision problems regarding to the computation of Nash equilibrium are hard even in parameterized complexity theory. However, we provide FPT algorithms for some other problems relevant to the computation of Nash equilibrium.",
keywords = "game theory, decision support techniques, Nash equilibrium",
author = "Mahdi Parsa",
year = "2011",
language = "English",

}

Parsa, M 2011, 'Parameterized Complexity Applied in Algorithmic Game Theory', Southport, Queensland, Australia.

Parameterized Complexity Applied in Algorithmic Game Theory. / Parsa, Mahdi.

Southport, Queensland, Australia, 2011. 113 p.

Research output: ThesisDoctoral Thesis

TY - THES

T1 - Parameterized Complexity Applied in Algorithmic Game Theory

AU - Parsa, Mahdi

PY - 2011

Y1 - 2011

N2 - The modern mathematical treatment of the study of decisions taken by participants whose interests are in conflict is now generally labeled as “game theory”. To understand these interactions the theory provides some solution concepts. An important such a concept is the notion of Nash equilibrium, which provides a way of predicting the behavior of strategic participants in situations of conflicts. However, many decision problems regarding to the computation of Nash equilibrium are computationally hard. Motivated by these hardness results, we study the parameterized complexity of the Nash equilibrium. In parameterized complexity one considers computational problems in a twodimensional setting: the first dimension is the usual input size n, the second dimension is a positive integer k, the parameter. A problem is fixed-parameter tractable (FPT) if it can be solved in time f(k)nO(1) where f denotes a computable, possibly exponential, function. We show that some decision problems regarding to the computation of Nash equilibrium are hard even in parameterized complexity theory. However, we provide FPT algorithms for some other problems relevant to the computation of Nash equilibrium.

AB - The modern mathematical treatment of the study of decisions taken by participants whose interests are in conflict is now generally labeled as “game theory”. To understand these interactions the theory provides some solution concepts. An important such a concept is the notion of Nash equilibrium, which provides a way of predicting the behavior of strategic participants in situations of conflicts. However, many decision problems regarding to the computation of Nash equilibrium are computationally hard. Motivated by these hardness results, we study the parameterized complexity of the Nash equilibrium. In parameterized complexity one considers computational problems in a twodimensional setting: the first dimension is the usual input size n, the second dimension is a positive integer k, the parameter. A problem is fixed-parameter tractable (FPT) if it can be solved in time f(k)nO(1) where f denotes a computable, possibly exponential, function. We show that some decision problems regarding to the computation of Nash equilibrium are hard even in parameterized complexity theory. However, we provide FPT algorithms for some other problems relevant to the computation of Nash equilibrium.

KW - game theory

KW - decision support techniques

KW - Nash equilibrium

UR - https://www120.secure.griffith.edu.au/rch/file/3ed187a5-f46d-f027-193b-e52ab6500c50/1/Parsa_2011_02Thesis.pdf

M3 - Doctoral Thesis

CY - Southport, Queensland, Australia

ER -

Parsa M. Parameterized Complexity Applied in Algorithmic Game Theory. Southport, Queensland, Australia, 2011. 113 p.