On the parameterized complexity of dominant strategies
EstivillCastro, V. and Parsa, M.; Reynolds, M. and Thomas, B, eds. (2012) On the parameterized complexity of dominant strategies. In: Proceedings of Computer Science 2012 (ACSC 2012). Conferences in Research and Practice in Information Technology, 122 . Australian Computer Society Inc., Melbourne, Australia, pp. 2126. ISBN 9781921770036 (http://crpit.com/confpapers/CRPITV122EstivillCast...)
Full text not available in this repository.Request a copyAbstract
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 MINIMUM MIXED 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 winlose games. Also, we show that it is a fixedparameter tractable problem on rsparse 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 ksteps 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 fixedparameter tractable problem.


Item type: Book Section ID code: 48197 Dates: DateEvent2012PublishedSubjects: Science > Mathematics > Electronic computers. Computer science
Science > Mathematics > Probabilities. Mathematical statisticsDepartment: Strathclyde Business School > Management Science Depositing user: Pure Administrator Date deposited: 21 May 2014 13:15 Last modified: 08 Apr 2024 13:11 Related URLs: URI: https://strathprints.strath.ac.uk/id/eprint/48197