Decision-Theoretic Planning under Anonymity in Agent Populations

Ekhlas Sonu, Yingke Chen, Prashant Doshi

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)


We study the problem of self-interested planning under uncertainty in settings shared with more than a thousand other agents, each of which plans at its own individual level. We refer to such large numbers of agents as an agent population. The decision-theoretic formalism of interactive partially observable Markov decision process (I-POMDP) is used to model the agent's self-interested planning. The first contribution of this article is a method for drastically scaling the finitely-nested I-POMDP to certain agent populations for the first time. Our method exploits two types of structure that is often exhibited by agent populations -- anonymity and context-specific independence. We present a variant called the many-agent I-POMDP that models both these types of structure to plan efficiently under uncertainty in multiagent settings. In particular, the complexity of the belief update and solution in the many-agent I-POMDP is polynomial in the number of agents compared with the exponential growth that challenges the original framework.
Original languageEnglish
Pages (from-to)725-770
Number of pages46
JournalJournal of Artificial Intelligence Research
Publication statusPublished - 29 Aug 2017
Externally publishedYes


Dive into the research topics of 'Decision-Theoretic Planning under Anonymity in Agent Populations'. Together they form a unique fingerprint.

Cite this