### Abstract

Original language | English |
---|---|

Award date | 8 Nov 2011 |

Place of Publication | Southport, Queensland, Australia |

Publication status | Published - 2011 |

### Fingerprint

### Keywords

- game theory
- decision support techniques
- Nash equilibrium

### Cite this

*Parameterized Complexity Applied in Algorithmic Game Theory*. Southport, Queensland, Australia.

}

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

Research output: Thesis › Doctoral 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 -