On the Structure and Complexity
		       of Worst-Case Equilibria

		  Simon Fischer and Berthold Vöcking

We study an intensively studied resource allocation game introduced by
Koutsoupias and Papadimitriou where $n$ weighted jobs are allocated to
$m$ identical machines.  It was conjectured by Gairing et al. that the
fully mixed Nash equilibrium is the worst Nash equilibrium for this
game w.r.t. the expected maximum load over all machines. The known
algorithms for approximating the so-called "price of anarchy" rely
on this conjecture.  We present a counter-example to the conjecture
showing that fully mixed equilibria cannot be used to approximate the
price of anarchy within reasonable factors. In addition, we present an
algorithm that constructs so-called concentrated equilibria that
approximate the worst-case Nash equilibrium within constant factors.