On the parameterized complexity of dominant strategies

File Size Format
73662_1.pdf 673Kb Adobe PDF View
Title On the parameterized complexity of dominant strategies
Author Estivill-Castro, Vladimir; Parsa, Mahdi
Publication Title Thirty-Fifth Australasian Computer Science Conference
Editor M. Reynolds & B. Thomas
Year Published 2012
Place of publication Australia
Publisher Australian Computer Society
Abstract In game theory, a strategy for a player is dominant if, regardless of what any other player does, the strategy earns a better payoff than any other. If the payoff is strictly better, the strategy is named strictly dominant, but if it is simply not worse, then it is called weakly dominant. We investigate the parameterized complexity of two problems relevant to the notion of domination among strategies. First, we study the parameterized complexity of the MINIMUMMIXED DOMINATING STRATEGY SET problem, the problem of deciding whether there exists a mixed strategy of size at most k that dominates a given strategy of a player. We show that the problem can be solved in polynomial time on win-lose games. Also, we show that it is a fixed-parameter tractable problem on r-sparse games, games where the payoff matrices of players have at most r nonzero entries in each row and each column. Second, we study the parameterized complexity of the ITERATED WEAK DOMINANCE problem. This problem asks whether there exists a path of at most k-steps of iterated weak dominance that eliminates a given pure strategy. We show that this problem is W [2]-hard, therefore, it is unlikely to be a fixed-parameter tractable problem.
Peer Reviewed Yes
Published Yes
Publisher URI http://acsc.csse.uwa.edu.au/
Alternative URI http://crpit.com/abstracts/CRPITV122Estivill-Castro.html
Copyright Statement Copyright 2012 Australian Computer Society Inc. The attached file is reproduced here in accordance with the copyright policy of the publisher. Please refer to the conference's website for access to the definitive, published version.
ISBN 1445-1336
Conference name ACSC 2012
Location Melbourne, Australia
Date From 2012-01-30
Date To 2012-02-02
URI http://hdl.handle.net/10072/47118
Date Accessioned 2012-02-07
Language en_US
Research Centre Institute for Integrated and Intelligent Systems
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Analysis of Algorithms and Complexity
Publication Type Conference Publications (Full Written Paper - Refereed)
Publication Type Code e1

Show simple item record

Griffith University copyright notice