Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with PLS-Completeness:
TR06-067 | 12th April 2006
Heiner Ackermann, Heiko Röglin, Berthold Vöcking

On the Impact of Combinatorial Structure on Congestion Games

We study the impact of combinatorial structure in congestion games on the complexity of computing pure Nash equilibria and the convergence time of best response sequences. In particular, we investigate which properties of the strategy spaces of individual players ensure a polynomial convergence time. We show, if the strategy space ... more >>>

ISSN 1433-8092 | Imprint