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

Keywords

  • game theory
  • decision support techniques
  • Nash equilibrium

Fingerprint Dive into the research topics of 'Parameterized Complexity Applied in Algorithmic Game Theory'. Together they form a unique fingerprint.

  • Cite this