  We investigate the complexity of bounding the uncertainty of graphical games,
and we provide new insight into the intrinsic difficulty of computing Nash
equilibria. In particular, we show that, if one adds very simple and natural
additional requirements to a graphical game, the existence of Nash equilibria
is no longer guaranteed, and computing an equilibrium is an intractable
problem. Moreover, if stronger equilibrium conditions are required for the
game, we get hardness results for the second level of the polynomial hierarchy.
Our results offer a clear picture of the complexity of mixed Nash equilibria in
graphical games, and answer some open research questions posed by Conitzer and
Sandholm (2003).
