  Agents in dynamic multi-agent environments must monitor their peers to
execute individual and group plans. A key open question is how much monitoring
of other agents' states is required to be effective: The Monitoring Selectivity
Problem. We investigate this question in the context of detecting failures in
teams of cooperating agents, via Socially-Attentive Monitoring, which focuses
on monitoring for failures in the social relationships between the agents. We
empirically and analytically explore a family of socially-attentive teamwork
monitoring algorithms in two dynamic, complex, multi-agent domains, under
varying conditions of task distribution and uncertainty. We show that a
centralized scheme using a complex algorithm trades correctness for
completeness and requires monitoring all teammates. In contrast, a simple
distributed teamwork monitoring algorithm results in correct and complete
detection of teamwork failures, despite relying on limited, uncertain
knowledge, and monitoring only key agents in a team. In addition, we report on
the design of a socially-attentive monitoring system and demonstrate its
generality in monitoring several coordination relationships, diagnosing
detected failures, and both on-line and off-line applications.
