On the parameterized complexity of dominant strategies

Vladimir Estivill-Castro, Mahdi Parsa

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedingspeer-review


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 simplynot 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 amixed 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-sparsegames, 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 problemasks 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 isW[2]-hard, therefore, it is unlikely to be a fixed-parameter tractable problem.
Original languageEnglish
Title of host publicationProceedings of the Thirty-Fifth Australasian Computer Science Conference (ACSC 2012)
Place of PublicationSydney
PublisherAustralian Computer Society
Number of pages5
ISBN (Print)978-1-921770-03-6
Publication statusPublished - 2012
Externally publishedYes
EventAustralasian Computer Science Conference (ACSC 2012 35th) - Melbourne, VIC; Australia, Melbourne, Australia
Duration: 1 Jan 2012 → …
Conference number: 2012


ConferenceAustralasian Computer Science Conference (ACSC 2012 35th)
Abbreviated titleACSC
Period1/01/12 → …


Dive into the research topics of 'On the parameterized complexity of dominant strategies'. Together they form a unique fingerprint.

Cite this