Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Bounding the Uncertainty of Graphical Games: The Complexity of Simple Requirements, Pareto and Strong Nash Equilibria
Gianluigi Greco, Francesco Scarcello
Abstract:
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).
Keywords:
Pages: 225-232
PS Link:
PDF Link: /papers/05/p225-greco.pdf
BibTex:
@INPROCEEDINGS{Greco05,
AUTHOR = "Gianluigi Greco and Francesco Scarcello",
TITLE = "Bounding the Uncertainty of Graphical Games: The Complexity of Simple Requirements, Pareto and Strong Nash Equilibria",
BOOKTITLE = "Proceedings of the Twenty-First Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-05)",
PUBLISHER = "AUAI Press",
ADDRESS = "Arlington, Virginia",
YEAR = "2005",
PAGES = "225--232"
}


hosted by DSL   •   site info   •   help