Master of mathematics
Contact details for Mahdi Parsa
Thesis
Parameterized complexity in algorithmic game theory
Description
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 problems. Motivated by these hardness results, we study the parameterized complexity of the Nash equilibrium. In parameterized complexity one considers computational problems in a two dimensional 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)n^(O(1)) where f denotes a computable, possibly exponential, function.
Supervisors
Professor Vladimir Estivill-Castro
Professor Rodney Topor
Research expertise
Contact details for Mahdi Parsa
Thesis
Parameterized complexity in algorithmic game theory
Description
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 problems. Motivated by these hardness results, we study the parameterized complexity of the Nash equilibrium. In parameterized complexity one considers computational problems in a two dimensional 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)n^(O(1)) where f denotes a computable, possibly exponential, function.
Supervisors
Professor Vladimir Estivill-Castro
Professor Rodney Topor
Research expertise
- Algorithm and complexity
- Parameterized complexity
- Graph algorithms
- Algorithmic game theory
- Combinatorial algorithm
- V. Estivill-Castro and M. Parsa. Computing Nash equilibria gets harder: new results show hardness even for parameterized complexity. In Downey, R. and Manyem, P., editors, CATS-09, Proceedings of the Fifteenth Australasian Symposium on Computing: The Australasian Theory, volume 94, pages 83-90, Australian Computer Society, Inc., Darlinghurst, Australia, 2009.
- V. Estivill-Castro and M. Parsa. Single parameter fpt-algorithms for non-trivial games. In C. S. Iliopoulos andW. F. Smyth, editors, IWOCA-10, Proceedings of the 21st International Workshop On Combinatorial Algorithms, London, UK, volume 6460 of Lecture Notes in Computer Science, pages 121-124. Springer, 2011.
- V. Estivill-Castro and M. Parsa. The parameterized complexity of Nash equilibria in win-lose games. Journal of Discrete Algorithms (JDA), 2010. Submitted.