Power, Dependence and Stability in Multiagent Plans

Sviatoslav Brainov, Tuomas SandholmAAAI 1999 · OpenReview

Abstract

This paper presents a decision-theoretic model of social power and social dependence that accounts for the origins of choices available in multiagent environments. The model posits that group activities—ranging from cooperation to exploitation—originate in the resolution of dependence or power relations. Designed for self-interested agents, the framework explains power and dependence through relations between agents' plans. It generalizes the dependence network model to account for group dependence, where an agent depends on a collective or vice versa. By applying this model to the analysis of multiagent plan stability, the authors identify stable dependence structures and provide necessary and sufficient conditions for the stability of joint plans.

Introduction

In multiagent systems (MAS), coordination is often the result of complex negotiations between autonomous, self-interested agents. Traditional models of social dependence frequently relied on qualitative descriptions or assumed a degree of altruism that does not always hold in competitive or resource-constrained environments. Furthermore, early models often focused on bilateral (one-to-one) dependencies, failing to capture the nuances of group dynamics.

This research addresses these gaps by introducing a formal decision-theoretic framework to define "social power" and "dependence." By grounding these concepts in utility functions and plan structures, the authors provide a rigorous method for predicting whether a joint multiagent plan will remain stable or collapse due to individual or group defection.

Theoretical Framework: Power as Utility Influence

The authors move away from abstract social roles, instead defining power through the lens of decision theory. In this model, power is fundamentally linked to an agent's ability to influence the utility of others.

Defining Power

Agent $j$ is said to have power over agent $i$ if $j$ can switch to an alternative plan that lowers $i$’s utility without simultaneously lowering their own. This introduces the concept of "cheap" influence: true social power exists when an agent can harm or benefit another at zero or negative cost to themselves. If exercising influence requires a significant sacrifice in utility for the power-holder, their effective power is diminished, as the threat of action is less credible.

Generalizing Dependence

The framework extends the traditional "dependence network" model in three critical ways:

  1. Transitive Dependence: If agent $i$ depends on agent $k$, and agent $k$ depends on agent $j$, then $i$ transitively depends on $j$. This allows for the modeling of long-chain supply or command structures.
  2. Conditional Dependence: This accounts for "tacit consent." An agent’s power over another may only exist if third parties choose not to intervene. If a bystander can mitigate the harm, the primary agent's power is conditional on the bystander's inaction.
  3. Group Dependence: The authors define the "minimal group" required to exert power. A group only truly holds power over an individual if every member of that group is necessary to maintain that influence. If a member can be removed without reducing the group's leverage, that member was not part of the core dependence structure.

Stability Analysis in Multiagent Plans

The core of the paper involves mapping these dependence structures onto game-theoretic stability concepts. The authors distinguish between Individual Stability (where no single agent has an incentive to deviate) and Coalitional Stability (where no group can collectively improve their situation by deviating), similar to the concept of a Strong Nash Equilibrium.

The Reciprocity Requirement

The most significant finding is that for a joint plan involving dependencies to be stable, the structure must be built on reciprocal dependence. In a "strongly connected" dependence graph—where every agent depends on others in a way that eventually loops back to themselves—no agent has a rational incentive to break the plan. They recognize that harming another agent in the chain will eventually result in a loss of their own utility through the feedback loop of dependencies.

Key Results and Propositions

The paper establishes several formal propositions regarding the stability of plans:

  • Propositions 4 & 5: In two-agent scenarios, if a plan is Pareto optimal and the agents either share a mutual dependence or are entirely independent, the plan is inherently stable.
  • Proposition 7: This serves as the paper's central theorem: A joint plan based on dependence is individually stable if and only if it is based on reciprocal dependence.
  • Proposition 9: In group settings, stability is achieved when power is balanced. If a group depends on an individual agent, but that agent simultaneously depends on at least one member of that group, a "power loop" is created that maintains equilibrium.

Discussion and Limitations

While the model provides a robust logical foundation for social power, it operates under certain idealizations:

  • Observability: The model assumes perfect observability. In real-world distributed systems, "hidden actions" or information asymmetry could allow agents to exercise power or defect without immediate detection.
  • Temporal Evolution: While the authors acknowledge that the cost of replanning often increases over time—making existing plans more stable as they progress—the current model lacks a formal temporal calculus for these shifting costs.
  • Potential vs. Action: The framework distinguishes between "power potential" and the actual "exercise of power." Future research is needed to explore how agents perform deliberative actions to actively increase their power potential during the negotiation phase of a plan.

Conclusion

By formalizing power and dependence through utility and plan relations, this research provides a mathematical basis for understanding social structures in MAS. The requirement for reciprocal dependence offers a clear guideline for designing stable multiagent protocols: to ensure cooperation among self-interested agents, one must ensure that every agent is both a provider and a recipient of dependence within the social network.

Summary updated

Abstract

In this paper we present a decision-theoretic model of social power and social dependence that accounts for origins of different choices available in different situations. According to the model almost every group activity, whether it is cooperation or exploitation, has its origins in resolving some dependence or power relation. The model is intended for self-interested agents and explains power and dependence in terms of relations between agents' plans. It is a generalization of the dependence network model and accounts for situations of group dependence, i.e., situations in which an agent depends on a group or a group depends on an agent. The model is applied to the analysis of stability of multiagent plans. Stable dependence structures of multiagent plans are identified. Necessary and sufficient conditions for stability of joint plans are provided.
BibTeX
@inproceedings{brainov1999power,
  author = {Sviatoslav Brainov and Tuomas Sandholm},
  title = {{Power, Dependence and Stability in Multiagent Plans}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
  url = {https://openreview.net/forum?id=HJbdA6edZH},
}
Figure