Complexity of Self-Preserving, Team-Based Competition in Partially Observable Stochastic Games

摘要

Partially observable stochastic games (POSGs) are a robust and precise model for decentralized decision making under conditions of imperfect information, and extend popular Markov decision problem models. Complexity results for a wide range of such problems are known when agents work cooperatively to pursue common interests. When agents compete, things are less well understood. We show that under one understanding of rational competition, such problems are complete for the class NEXPNP. This result holds for any such problem comprised of two competing teams of agents, where teams may be of any size whatsoever.