Agent Influence as a Predictor of Difficulty for Decentralized Problem-Solving

Martin Allen, Shlomo ZilbersteinAAAI 2007

Introduction

Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs) are the gold standard for modeling multi-agent coordination under uncertainty. Despite their utility, they are notoriously difficult to solve, categorized as NEXP-complete. This computational complexity means that even small-scale problems can lead to a "doubly exponential" explosion in the resources required for an optimal solution. Historically, identifying which problem instances are solvable has been difficult, as common simplifications like transition independence do not consistently improve performance. This research introduces the Influence Gap, an information-theoretic metric that predicts the computational difficulty of Dec-POMDPs by measuring the asymmetry of agent influence.

Methodology

The researchers focused on the Optimal Dynamic Programming (DP) algorithm, which prunes dominated strategies to find optimal policy trees. To characterize the structure of a problem, they proposed three metrics based on Mutual Information:

  1. State-influence (SI): The degree to which an agent’s actions determine the environment's state.
  2. Reward-influence (RI): The degree to which an agent’s actions determine immediate rewards.
  3. Influence Gap (IG): The absolute difference in total influence ($SI + RI$) between agents.

A high IG indicates a system where one agent is significantly more influential than the others, while a zero IG represents perfect symmetry.

Experimental Setup

The study utilized a testbed of 900 two-agent "noisy broadcast channel" problems. The authors systematically varied transition matrices (random, independent, or single-agent influence) and reward structures. This diversity allowed for testing across a wide range of Influence Gaps.

Distribution of information gaps for random and independent transition instances.

As shown in the distribution of instances, transition independence does not inherently lead to high influence gaps; in fact, many independent-transition instances result in a zero gap, which correlates with higher difficulty.

Analysis of Influence and Difficulty

The core finding of the research is that symmetry is a curse. When agents have equal influence (Zero Gap), the DP algorithm struggles to prune the search space, making the problem significantly harder. Conversely, a large Influence Gap simplifies the problem because the less influential agent's optimal strategy becomes easier to identify.

Difficulty categories (Hard, Medium, Easy) across different Influence Gap ranges.

The results demonstrate a clear correlation:

  • Zero Gap: 68.5% of instances were "Hard" (solvable for only 3–4 steps), with only 15% categorized as "Easy."
  • Large Gap: The trend reverses, with 69.8% of instances being "Easy" (solvable for 100+ steps) and only 4.1% remaining "Hard."

This confirms that the Influence Gap is a powerful domain-independent predictor of ease. It also explains why transition independence alone is insufficient for simplification: if independence leads to a zero gap, the problem remains computationally taxing.

Conclusion and Future Work

The Influence Gap provides an automatic characterization of Dec-POMDP difficulty based on underlying dynamics rather than specific game rules. However, limitations remain. The current model focuses on transitions and rewards, omitting the observation model, which is a critical component of Dec-POMDPs. Future research will aim to incorporate observations into the metric and extend the pairwise Influence Gap to scenarios involving more than two agents.

Summary updated

BibTeX
@inproceedings{allen2007agent,
  author = {Martin Allen and Shlomo Zilberstein},
  title = {{Agent Influence as a Predictor of Difficulty for Decentralized Problem-Solving}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2007},
}
Figure