Reasoning About the Transfer of Control

Wiebe van der Hoek, Dirk Walther, Michael J. Wooldridge

Abstract

We present DCL-PC: a logic for reasoning about how the abilities of agents and coalitions of agents are altered by transferring control from one agent to another. The logical foundation of DCL-PC is CL-PC, a logic for reasoning about cooperation in which the abilities of agents and coalitions of agents stem from a distribution of atomic Boolean variables to individual agents -- the choices available to a coalition correspond to assignments to the variables the coalition controls. The basic modal constructs of DCL-PC are of the form coalition C can cooperate to bring about phi. DCL-PC extends CL-PC with dynamic logic modalities in which atomic programs are of the form agent i gives control of variable p to agent j; as usual in dynamic logic, these atomic programs may be combined using sequence, iteration, choice, and test operators to form complex programs. By combining such dynamic transfer programs with cooperation modalities, it becomes possible to reason about how the power of agents and coalitions is affected by the transfer of control. We give two alternative semantics for the logic: a direct semantics, in which we capture the distributions of Boolean variables to agents; and a more conventional Kripke semantics. We prove that these semantics are equivalent, and then present an axiomatization for the logic. We investigate the computational complexity of model checking and satisfiability for DCL-PC, and show that both problems are PSPACE-complete (and hence no worse than the underlying logic CL-PC). Finally, we investigate the characterisation of control in DCL-PC. We distinguish between first-order control -- the ability of an agent or coalition to control some state of affairs through the assignment of values to the variables under the control of the agent or coalition -- and second-order control -- the ability of an agent to exert control over the control that other agents have by transferring variables to other agents. We give a logical characterisation of second-order control.

Introduction

In multi-agent systems research, frameworks like Coalition Logic or Alternating-time Temporal Logic (ATL) are frequently used to reason about what groups of agents can achieve. However, these frameworks often treat an agent’s "power" as a static, black-box attribute. A more granular approach is CL-PC (Coalition Logic of Propositional Control), where an agent’s power is derived from their exclusive control over a set of Boolean variables—essentially "levers" they can pull to affect the world.

While CL-PC is powerful, it assumes the distribution of these levers is fixed. In real-world scenarios, such as human organizations or open software environments, control is fluid: agents delegate tasks, join groups, or leave positions. This paper introduces DCL-PC (Dynamic Coalition Logic of Propositional Control), which fills this gap by making the transfer of control a first-class citizen in the logic.

The DCL-PC Framework

DCL-PC extends the static foundation of CL-PC by incorporating concepts from Propositional Dynamic Logic (PDL). The core innovation is the introduction of transfer programs, which allow the logic to model the movement of control between agents.

The formal syntax of DCL-PC formulas and transfer programs.

As shown in the syntax above, the logic defines:

  1. Atomic Transfers: The program $i \leadsto_p j$ represents agent $i$ giving control of variable $p$ to agent $j$.
  2. Complex Programs: These atomic actions can be combined using standard programming constructs: sequence (;), non-deterministic choice ($\cup$), iteration ($*$), and tests ($?$).
  3. Cooperation Modalities: Formulas like $\diamond_C \phi$ express that a coalition $C$ can cooperate to bring about $\phi$ given their current control.

Key Insights: Levels of Control

A significant conceptual contribution of DCL-PC is the formal distinction between two types of power:

  • First-order control: The ability to change the state of the world by setting a variable to true or false.
  • Second-order control: The ability to change who has the power by transferring control of a variable to another agent.
Visual representation of agents and the dynamic transfer of control variables.

By combining dynamic transfer programs with cooperation modalities, it becomes possible to reason about how the power of agents and coalitions is affected by the transfer of control. The authors successfully defined a formula, CONTROLS(i, φ), that captures an agent's ability to achieve a state of affairs through a combination of both acting and delegating.

Complexity and Results

One might expect that adding dynamic programs to a logic would significantly increase its computational complexity. Surprisingly, the authors demonstrate that DCL-PC remains PSPACE-complete for both satisfiability and model checking. This is the same complexity class as the static CL-PC, indicating that the dynamic extensions do not make the logic inherently harder to solve.

Furthermore, the authors prove a Normal Form Theorem, showing that every DCL-PC formula is equivalent to a "proposition description." This reduction of complex dynamic transfers to static descriptions of control is the key to proving the logic's completeness and complexity bounds.

Future Work

While DCL-PC provides a robust foundation, several avenues for future research remain:

  • Parallelism: The current logic handles sequential transfers but cannot yet model simultaneous mutual transfers between agents.
  • Social Laws: Future extensions could introduce restrictions on transfers, such as "manager" roles that are the only ones permitted to reassign specific variables.
  • Coalitional Ownership: The model could be expanded to allow collective ownership of variables, requiring group consensus for value changes or transfers.
  • Temporal Integration: Integrating DCL-PC with temporal logics like LTL would allow for reasoning about long-term properties, such as whether an agent will eventually acquire control of a specific resource.

Summary updated

Abstract

We present DCL-PC: a logic for reasoning about how the abilities of agents and coalitions of agents are altered by transferring control from one agent to another. The logical foundation of DCL-PC is CL-PC, a logic for reasoning about cooperation in which the abilities of agents and coalitions of agents stem from a distribution of atomic Boolean variables to individual agents -- the choices available to a coalition correspond to assignments to the variables the coalition controls. The basic modal constructs of DCL-PC are of the form coalition C can cooperate to bring about phi. DCL-PC extends CL-PC with dynamic logic modalities in which atomic programs are of the form agent i gives control of variable p to agent j; as usual in dynamic logic, these atomic programs may be combined using sequence, iteration, choice, and test operators to form complex programs. By combining such dynamic transfer programs with cooperation modalities, it becomes possible to reason about how the power of agents and coalitions is affected by the transfer of control. We give two alternative semantics for the logic: a direct semantics, in which we capture the distributions of Boolean variables to agents; and a more conventional Kripke semantics. We prove that these semantics are equivalent, and then present an axiomatization for the logic. We investigate the computational complexity of model checking and satisfiability for DCL-PC, and show that both problems are PSPACE-complete (and hence no worse than the underlying logic CL-PC). Finally, we investigate the characterisation of control in DCL-PC. We distinguish between first-order control -- the ability of an agent or coalition to control some state of affairs through the assignment of values to the variables under the control of the agent or coalition -- and second-order control -- the ability of an agent to exert control over the control that other agents have by transferring variables to other agents. We give a logical characterisation of second-order control.
BibTeX
@article{hoek2010reasoning,
  author = {Wiebe van der Hoek and Dirk Walther and Michael J. Wooldridge},
  title = {{Reasoning About the Transfer of Control}},
  journal = {J. Artif. Intell. Res.},
  year = {2010},
  doi = {10.1613/jair.2901},
}

Loading related content...

Figure