Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Felix Fischer:

TR08-077 | 23rd May 2008
Felix Brandt, Felix Fischer, Markus Holzer

On Iterated Dominance, Matrix Elimination, and Matched Paths

We study computational problems that arise in the context of iterated dominance in anonymous games, and show that deciding whether a game can be solved by means of iterated weak dominance is NP-hard for anonymous games with three actions. For the case of two actions, this problem can be reformulated ... more >>>

TR07-136 | 28th November 2007
Felix Brandt, Felix Fischer, Markus Holzer

Equilibria of Graphical Games with Symmetries

We study graphical games where the payoff function of each player satisfies one of four types of symmetries in the actions of his neighbors. We establish that deciding the existence of a pure Nash equilibrium is NP-hard in graphical games with each of the four types of symmetry. Using a ... more >>>

TR06-091 | 29th May 2006
Felix Brandt, Felix Fischer, Markus Holzer

Symmetries and the Complexity of Pure Nash Equilibrium

Strategic games may exhibit symmetries in a variety of ways. A common aspect of symmetry, enabling the compact representation of games even when the number of players is unbounded, is that players cannot (or need not) distinguish between the other players. We define four classes of symmetric games by considering ... more >>>

ISSN 1433-8092 | Imprint