Agent Influence as a Predictor of Difficulty for Decentralized Problem-Solving
Martin Allen
Shlomo Zilberstein
Abstract
We study the effect of problem structure on the practical performance
of optimal dynamic programming for decentralized
decision problems. It is shown that restricting agent influence
over problem dynamics can make the problem easier to solve.
Experimental results establish that agent influence correlates
with problem difficulty: as the gap between the influence of
different agents grows, problems tend to become much easier
to solve. The measure thus provides a general-purpose, automatic
characterization of decentralized problems, identifying
those for which optimal methods are more or less likely to
work. Such a measure is also of possible use as a heuristic in
the design of algorithms that create task decompositions and
control hierarchies in order to simplify multiagent problems.
Download
[pdf]