2007
NeurIPS
NeurIPS 2007
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.
🌉
Interdisciplinary Bridge
- Artificial Intelligence and Mathematics & Optimization and Reinforcement Learning
📈
Trend Setter
- Decision Making
🧭
Keyword Pioneer
- complexity theory
🐣
Hot Topic Early Bird
- multi-agent system
Authors
Topics
Artificial Intelligence > Core AI > Multi-Agent Systems
Reinforcement Learning > Methods > Multi-Agent Systems
Machine Learning > Learning Types > Multi-Agent Systems
Mathematics & Optimization > Optimization > Game Theory
Artificial Intelligence > Core AI > Game Theory
Artificial Intelligence > Core AI > Decision Making
Machine Learning > Optimization & Theory > Game Theory