Competition Adds Complexity
Abstract
It is known that determinining whether a DEC-POMDP, namely, a cooperative partially observable stochastic game (POSG), has a cooperative strategy with positive expected reward is complete for NEXP. It was not known until now how cooperation affected that complexity. We show that, for competitive POSGs, the complexity of determining whether one team has a positive-expected-reward strategy is complete for the class NEXP with an oracle for NP.
Cite
Text
Goldsmith and Mundhenk. "Competition Adds Complexity." Neural Information Processing Systems, 2007.Markdown
[Goldsmith and Mundhenk. "Competition Adds Complexity." Neural Information Processing Systems, 2007.](https://mlanthology.org/neurips/2007/goldsmith2007neurips-competition/)BibTeX
@inproceedings{goldsmith2007neurips-competition,
title = {{Competition Adds Complexity}},
author = {Goldsmith, Judy and Mundhenk, Martin},
booktitle = {Neural Information Processing Systems},
year = {2007},
pages = {561-568},
url = {https://mlanthology.org/neurips/2007/goldsmith2007neurips-competition/}
}