2007
NIPS
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 Reinforcement Learning
📈
Trend Setter
— Multi-Agent Systems
🧭
Keyword Pioneer
— dec-pomdp
🐣
Hot Topic Early Bird
— multi-agent system
🐝
Cross-Pollinator
— Artificial Intelligence, Computer Science, Deep Learning, Healthcare & Medicine, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics
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