Cooperation Structures

1 Introduction

Cooperation is perhaps the paradigm example of social activ­ ity in both real and artificial social systems; it is certainly the best studied process in multi-agent systems research. Coop­ eration in human societies is an intricate and subtle activity, which has defied many attempts to formalise it. However, some progress has been made on understanding the types of situation in which cooperation can arise, and how it can pro­ ceed.

Central to the study of cooperation is the notion of a social structure. A social structure is a set of relations that hold between agents in a society. These relations define the depen­ dencies that exist between agents (e.g., [Castelfranchi, 1990; d'Inverno and Luck, 1996a; 1996b]), and determine the rights and responsibilities of each agent in the society with respect to its peers. In order to cooperate effectively with its peers, an agent must represent any social structures in which it plays a part, and reason with these representations. This reason­ ing process is carried out in order to answer such questions as whether cooperation is possible, and to investigate how an agent stands in relation to other agents in the society. In · multi-agent systems, the representation of social structures is a central research issue. For example, Durfee has devel­ oped representations of multi-agent activity known as partial global plans [Durfee and Lesser, 1987]. These structures can be manipulated by an agent in order to find more efficient routes to solving complex multi-agent problems.

Much work on representing social structures in multi-agent systems has been purely formal, with no obvious, direct route to implementation. Game-theoretic and economic-theoretic studies of social behaviour fall into this category [Rosenschei n and Genesereth, 1985]. Although such work is central to our understanding of cooperation, it has little to tell us about the computational aspects of social reasoning, such as what types of social reasoning are tractable. Our aims in this paper are therefore threefold:

• to introduce an abstract symbolic representation of social structures;
• to identify and formally define some basic reasoning problems associated with these social structures; and finally
• to investigate the computational complexity of these problems.

We begin in the following section by introducing a simple, general formal framework, which can be used to represent a wide range of multi-agent scenarios. This framework defines agents as systems that have the ability to achieve certain goals, and that are capable of making independent decisions about how they will interact with other agents. We informally di s­ cuss the properties of cooperation and cooperation structures, and formally define cooperation structures within our frame­ work. We then introduce COOPSAT, a key deci sion problem in social reasoning. COOPSAT is the problem of determining, given some society of agents and a particular agent's goal , whether or not cooperation is in principle possible to achieve the agent's goal. We show that the problem is NP-complete, and that it cannot therefore be answered in practice. We then address the issue of manipulating social structures, and the conditions under which they can be combined. Finally, we discuss related work, and present some conclusions and future research directions.

2 Cooperation Structures

Before we can define cooperation and cooperation structures, we need a formal framework within which we can express the definitions. A number of such formal frameworks have previously been developed, the most obvious of which being game-theory (e.g., [Rosenschein and Genesereth, 1985]) and multi-modal logic (e.g., [Wooldridge and Jennings, 1994]).

With respect to the former, the models derived are by nature quantitative rather than symbolic, and hence not well-suited to representation within a computer system. With respect to the latter, the models derived tend to be rather arcane, and do not easily lend themselves to, for example, complexity­ theoretic analysis. For these reasons, we develop a simple formal framework for expressing multi-agent scenarios, us­ ing a notation based on the Z specification language [Spivey, 19.92] which, in turn, is based on set theory and first-order logic. In Z, a relation R is defined as a set of ordered pairs. The expression dom R represents the set of the first elements of each of the ordered pairs of R, and ran R represents the set of second elements. Also, R+ is the transitive closure, and R* is the reflexive transitive closure of R.

We start by assuming a fixed, finite set Ag of agents. We use i, j, k as variables ranging over Ag. The main assumptions that we make with respect to agents are that they are autonomous (in that they are not benevolent), and that they have capabilities (in that they have the ability to achieve goals). The properties of agents are discussed in more detail elsewhere [Wooldridge and Jennings, 1995; Luck and d'Inverno, 1995].

Next, we assume a fixed, finite set G of goals. We use g with annotations (g', g1, ... ) as variables ranging over G. Whereas the assumption that Ag is finite seems intuitively reasonable, it may seem odd to assume that the set of goals is finite: it is common in AI to represent goals as logical formulae, and hence to allow the set of goals to be infinite in size. We make this assumption in the interests of simplicity. In this paper, we are not concerned with the question of what a goal is - the contents of G are left undefined (but have been considered elsewhere [Luck and d'Inverno, 1995]). However, it seems essential to introduce some notion of consistency between goals. We thus assume a relation con ~ G x G, such that if (g , g') E con, then g and g' are said to be consistent with one another. We write con(g , g') to indicate that (g, g') E con. The intuitive meaning of con(g, g') is that g being satisfied does not preclude g' being satisfied: the two goals are not mutually exclusive. We shall not give a formal semantics to con, but we do require that this relation satisfies the following properties:

• reflexive: V g E G · con(g, g); and
• symmetric: V g, g' E G · con(g, g') <::} con(g', g).

In addition to consistency, we assume that goals are related to each other through a sub-goal relation: ~ ~ G x G. A sub-goal is a component goal of another, higher-order, goal. Thus if (g, g') E ~ (written g ~ g'), then g is said to be a sub-goal of g'.

The ~ relation must satisfy the following properties:

• reflexive:

• transitive:

• well-founded:

The first two conditions are intuitively obvious; well­ foundedness simply states that no goal has an infinite, non­ terminating chain of sub-goals.

We define the strict sub-goal relation, <. in the obvious way: g < g' <::} g ~ g' 1\ g =f g'. With the exception of reflexivity, < enjoys all the properties of~ and, in addition, < is asymmetric. Since < is well-founded, some goals are primitive and have no strict sub-goals. We write ..l < g to indicate that g has no strict sub-goals. We assume that there is just one way to achieve a goal, by achieving all its strict sub-goals. We make this assumption in the interests of simplicity though, of course, the real-world is somewhat more complicated than this. If I have a goal of drinking tea, I have many different possible courses of action available to me: for example, I can make the tea myself, ask someone to make me a cup, or go to a cafe.

Another useful extension to ~ is the immediate sub-goal relation: ~. This relation is defined as follows : g ~ g' <::} g < g' 1\ (· 3g" E G · ((g < g") 1\ (g" < g'))). The function isg : G--+ JlD G takes a goal and returns the set of all its immediate sub-goals: isg(g) = {g' I g' ~ g}.

We noted above that benevolence is not assumed in our framework. Crudely, the benevolence assumption states that agents will always attempt to do what is requested of them: they are not autonomous [Rosenschein and Genesereth, 1985]. While benevolence is reasonable for many distributed problem-solving systems, it is not an appropriate assumption in most multi-agent scenarios. In order to capture auton­ omy in our framework, we make use of a will-adopt function , will: Ag x Ag -+ JlD G. The idea is that agent i will adopt a goal g on behalf of another agent j iff g E will( i, j). Where there can be no confusion, we write will( i, g, j) to indicate g E will( i, j). We do not give a formal semantics to this relation, as its properties will be domain specific 1 ·

The capabilities of agents are represented in a function cap : Ag -+ JlD G. The idea is that cap( i) represents the set of goals that agent i can achieve in isolation. We require the following invariant to hold between the cap and will functions: will(i,g,j) => g E cap(i).

The various sets and relations introduced above together comprise a framework.

Definition 1 A framework is a 6-tuple

with components as above. Let Fr be the set of all frameworks. We use F with annotations ( F', F1, ·· · ) as variables ranging over Fr.

For most of this paper, the framework is assumed to be fixed and understood.

2.1 Defining Cooperation Structures

Previously, Luck and d'Inverno [ 1996] have taxonomised the types of interactions that occur between agents in a multiagent system, distinguishing in particular between engage­ ments of non-autonomous agents and cooperation between autonomous (motivated) agents. In this view, autonomous agents will only adopt goals if it is to their motivational ad­ vantage to do so, while non-autonomous agents may benevo­ lently adopt goals. Though we focus on autonomous agents, the discussion of cooperation structures below does not re­ fer to the reasons for goal adoption, nor to the autonomy or non-autonomy ofthe agents involved and, consequently, these structures are generic and may be applied to cooperations and engagements, as described here, equally.

1 There are certain properties that it seems reasonable to demand of will. For example, we might specify that if i will adopt g for j, then i will also adopt any sub-goal of g for j: \:1 i , j E Ag · \:1 g, g' E G · (g E will(i ,j) 1\ g' ~ g) => g' E will(i ,j) . However, none of these properties are essential for our framework.

We define cooperation by one agent with another to mean that the agent will adopt a goal on behalf of that other agent. These cooperations give rise to a graph structure, with nodes in the graph corresponding to agents, and arcs in the graph corresponding to cooperations, labelled with goals. This leads us to the definition of a structure.

Definition 2 A structure is a pair ( C, l) where:

• C ~ Ag x Ag is a binary cooperates relation;
• l : C --+ G labels each arc in C with a goal.

If (C, l) is a structure, then we write C(i,j) to indicate (i,j) E C. The intuitive interpretation of C(i,j) is that agent i has delegated goal /( i, j) to agent j, and thus that j is cooperating with i over this goal.

Not all structures are cooperation structures, however. For a structure to be a cooperation structure, there must first be at least two agents cooperating, and each agent in the structure must be connected to another through a cooperation over goals between them. Furthermore, agents cannot delegate goals to others who, in turn, delegate them back to the original agent. Hence there are no cycles, and no agent cooperates with itself. Also, if one agent j cooperates with another agent i over some goal 9, and another agent k cooperates with j for goal 9' then 9' must be a sub-goal of 9. Thus when agents delegate, they delegate sub-goals. Fi nail y, all goals in a cooperation structure must be consistent with each other. These considerations lead to the following definition.

Definition 3 A structure ( C, l) is a cooperation structure iff:

• /. C is non-empty: C ::j:. 0;
• C is weakly connected;
• Cis acyclic: ViE Ag ·-, c+(i, i);
• Cis irreflexive: Vi E Ag · -, C( i, i);
• agents delegate sub-goals: V i,j, k E Ag · C(i,j) 1\ C(j, k) => l(j, k) ::::; l(i, j);
• goals within a structure are mutually consistent: V g, g' E ran l· con(g, g'); and
• j cooperates with i only ifj is willing to do so: C(i,j) => will(j, l(i,j), i).

Let Coop be the set of all cooperation structures.

Condition (3) may seem too strong. To see why, consider the following scenario: John asks Paul to make some tea. Paul agrees, but asks that John boil the kettle. This kind of scenario (where i delegates a goal 9 to j, and j in return del­ egates a strict sub-goal of 9 back to i) occurs frequently in real life. However, the problem of determining whether an arbitrary, possibly cyclic structure was in fact a legal cooper­ ation structure would then become much harder. In addition, determining whether it was possible to fuse two cooperation structures (a problem we consider below) would also be much more complicated. For these reasons, cooperation structures are required to be acyclic.

Finally, the function, dele9 : A9 x Coop --+ 1!1' G, returns the set of goals that an agent delegates in some cooperation structure: dele9( i, ( C, I)) = {I( i, j) I C( i, j)}.

2.2 Complete Cooperation Structures

Consider the following scenario. Agent a1 wants to achieve goal 91, but 91 tf. cap( a1 ). The complete sub-goal structure for 91 is illustrated in Figure I (a). Agent a1 delegates goals 92, 93, and 94 to agents a2, a3, and a4 respectively. Agents a3 and a4 have the capabilities to achieve their respective goals (i.e., 93 E cap( a3) and 94 E cap( a4)), but a2 is not capable of 92· It should therefore delegate the sub-goals 95 and 96 to other agents, but it does not. So 92 will not be achieved, and hence neither will 91· The cooperation structure in Figure I (b) is thus in some sense incomplete.

This leads to the idea of a cooperation structure being com­ plete for some agent-goal pair. Informally, a cooperation structure is said to be complete for agent i and goal g iff either:

1. agent i has been delegated the goal 9, and i is capable of 9; or else

1. agent i has delegated each immediate sub-goal 9' of 9 to some agent j, and ( C, I) is complete for agent j and goal 9'.

Completeness is hence a recursive notion, with the first clause as the base. It is not difficult to see that the cooperation struc­ ture in Figure I (b) is incomplete according to this definition, but that Figure I (c) is complete (assuming that 95 E cap( as) and 96 E cap( a6)). Formally, completeness is defined as follows .

Definition 4 A cooperation structure c = ( C, 1) is said to be complete with respect to agent i and goal g iff either:

1. g E cap( i), and for some j E Ag, we have CU, i) and LU, i) = g; or else
2. isg(g) ~ deleg(i , ( C, !)), and V j E Ag, if C(i,j) and l(i, j) «:: g, then (C, 1) is complete for agent} and goal l( i,j).

In a complete cooperation structure, there are no sub-goals left dangling: all sub-goals are successfully delegated and hence, by the intuitive semantics for the sub-goal relation, every goal in the structure is achieved.

3 Is Cooperation Possible?

Suppose an agent has a goal that it wants to achieve, and further suppose that the agent either cannot achieve the goal in isolation (because it does not have the resources), or does not want to achieve it in isolation (because in so doing, it would clobber one of its other goals) [Wooldridge and Jennings, 1994]. The obvious question this agent should ask is: can I get other agents to help me with this goal? This is a satisfiability problem, similar in nature to the question of whether a formula of some particular logic is true under some interpretation. Formally, the problem can be stated as follows.

Definition 5 (The COOPSAT problem.) Given a framework F = (Ag, G, con, s;, will, cap), an agent i E Ag, and a goal g E G, does there exist a cooperation structure over F that is complete for ( i, g) ?

Theorem 1 COOPSAT is NP-complete.

Proof: Membership of NP is easy: given an instance ((Ag, G, con, s; , will , cap) , i, g) oftheCOOPSAT problem, sim­ ply guess a cooperation structure ( C, 1) that is complete for (i, g). The size of the structure is bounded above by #(Ag xAg) and, since Ag is finite, guessing can be done in polynomial time. Verifying that (C, 1) is complete for (i , g) can also be done in polynomial time.

For completeness, we must show that COOPSAT is in some sense no easier than all other NP-complete problems. To do this , it suffices to show that any instance I of some known NP-complete problem can be transformed into an instance of r(l ) of COOPSAT such that the transformation can be done in polynomial time, and the transformed problem r(/) has a solution only if the original problem I has a solution. For COOPSAT, we define a reduction from a version of the well­ known HAMILTONIAN CYCLE (HC) problem.

An instanceofHC is determined by a graph (N, A ~ N xN) . The aim is to answer 'yes' if A has a cycle containing all nodes without repetition, 'no' otherwise. The idea behind the reduction is to encode the relation A in the will relation , and the requirement for the cycle in the sub-goal relation <.

To see how the reduction works, consider the following graph G1 (illustrated in Figure 2):

This graph has a Hamiltonian cycle (n 1, n2 , n, , n4 ) . We trans­ form G1 into an instance r( G1) ofCOOPSAT. To do thi s. we first create five goals g0 , . · . , g4, and five agents. n1, .. . , n4, end. We then create a linear sub-goal structure for go:

The will relation is then generated as follows.

Now consider the COOPSAT problem determined by thi s frame­ work and the agent-goal pair (n 1, go). The problem clearly has a solution, which will look like that below, where each question mark represents an agent.

In fact, this problem has a simple solution:

The transformation from HC to COOPSAT is entirely automatic, (see Figure 3) and is polynomial. We leave it for the reader to see that the generated COOPSAT problem has a solution only if the original HC problem does, and so we are done. o

Suppose we had an algorithm that was guaranteed to give us the correct answer to an instance of the COOPSAT problem. This algorithm would take as input a framework, an agent and a goal and, some time later, would be guaranteed to generate as output of either 'yes' (indicating that a solution did indeed exist), or 'no' (indicating that the problem had no solution). Now, suppose the algorithm answered 'yes'. Then the agent would know that cooperation was possible. It would then have to start delegating goals to other agents. But the simple

let n = #N be the size of N for each node i E N, create a corresponding agent i create a 'dummy' agent, called end create n + I goals, g0 , . .. , gn set con(g , g') for all goals g, g' define < by gil «:: · · · «:: g1 «::go for each agent j -:f end for each agent k -:f end if U, k) E A then if k = n1 then will:= will U {U, end) r--+ {gil}} else will := will U {U, k) r--+ {gi , ... , gn}} else will:= will U {U, k) r--+ 0} end-for end-for cap := {end r--+ {gil}}

'yes' answer does not indicate exactly who the agent should delegate to. A more useful algorithm would not only say 'yes', but would also produce a solution to the problem. This leads us to the following, closely related problem.

Definition 6 (The COOPFIND problem.) Given a framework F = (Ag , G, con,::;, will, cap), an agent i E Ag, and a goal g E G. find a cooperation structure over F that is complete for ( i, g) if such a structure exists, or else answer that there is no solution.

This problem is clearly related to many similar planning prob­ lems [Allen et al., 1990]; it is also naturally viewed as a type of constraint satisfaction problem.

4 Composing Cooperation Structures

In a real society there will be many cooperation structures in existence at any given time. This may result in redun­ dancy through different agents achieving the same goals in different contexts. In order to remove this redundancy it may be possible to compose two cooperation structures. Given two cooperation structures, c = ( C, l) and c' = ( C', 1'), we write c U c' to denote the set-theoretic union ( C U C', l U /') of these structures. However, this composition can only oc­ cur in certain situations: we cannot expect the union of two arbitrary cooperation structures to be a legal structure. For example, if we have some arc, ( i, j), that appears in both C and C', but/( i, j) -:f !'( i, j), then /U /'is not a function (since (I U /')(i, j) is not well-defined). This raises the question of what conditions are required for the union of two cooperation structures itself to be a cooperation structure. It turns out that we can define these conditions precisely. First, we extend the notion of intra-structure goal consistency to inter-structure goal consistency.

Definition 7 Let c = ( C, l) and c' = ( C', I') be cooperation structures. Then c and c' are said to be consistent (written cons(c, c')) iffV g E ran l· V g' E ran l' · con(g, g').

We can now define what it means for two structures to be compatible.

Definition 8 If c = ( C, l) and c' = ( C', L') are cooperation compat(c, c')) iff:

• structures, then c and c' are said to be compatible (written I . C U C' is weakly connected; 2. C U C' is acyclic; 3. the two structures agree on labels: V i,j E Ag · C(i,j) 1\ C'(i,j):::} l(i,j) = l'(i,j) 4. V i,j, k E Ag, (a) if C(i,j) 1\ ..., CU, k) 1\ ..., C'(i,j) 1\ C'U, k) then

1. cons( c, c').

One might expect that compatibility is an equivalence relation over the set of all cooperation structures, but this is not in fact the case, as the following theorem establishes.

Theorem 2 The compatibility relation is reflexive and sym­ metric. but not transitive.

Proof: Reflexivity and symmetry are obvious. For transitiv­ ity, it is easy to construct a counter-example. Suppose we had three cooperation structures c, c', c". Further suppose that compat(c, c') and compat(c', c"), and that c and c' share a single agent i in common, and c' and c" share a different single agentj in common (i -:f j). Hence c and c" are disjoint, so c U c" is not weakly connected. Hence c and c" are not compatible. o

Determining whether two cooperation structures are compat­ ible is a tractable problem.

Theorem 3 It is possible to determine whether two coopera­ tion structures are compatible in polynomial time- no worse than O(#(Ag) 3 ).

Proof: The o,nly non-trivial step involves showing that there­ sulting cooperation relation is acyclic, which requires check­ ing the transitive closure of the relation- using Warshall's algorithm, the transitive closure can be computed in time O(#(Ag) 3 ) [van Leeuwen, 1990, pp540-544l The overall time complexity is therefore no worse than O(#(Ag?) . o

Theorem 4 If c = ( C, l) and c' = ( C', /') are coopera­ tion structures, then c U c' is a cooperation structure iff compat(c, c').

Proof: (Omitted due to lack of space.)

o

Once we know that two cooperation structures are compati­ ble, the problem of generating their union is computationally trivial.

5 Related Work

As we noted in Section I, cooperation is a widely studied issue in multi-agent systems research. Despite this, we are aware of little other work that considers cooperation in the complexity-theoretic way proposed in this paper. Probably the most closely related work to ours is that of Shehory and Kraus on coalition formation [Shehory and Kraus, 1996]. Coalition formation is the process of devising a team of agents to work on a goal, and is rather similar to our COOPSAT prob­ lem. The most obvious differences between our work and that of Shehory and Kraus are that they assume benevolent agents, and they present algorithms (adapted from the set cov­ ering problem) to design coalitions. In addition, the work of Tennenholtz and Moses on the multi-entity model of multi­ agent systems [Tennenholtz and Moses, 1989] is also closely related. This model is used to define the cooperative goal achievement (CGA) problem, which can crudely be stated as: given a set of benevolent agents, each with their own goals, is there some plan for the set that will achieve all their goals? Tennenholtz and Moses show that this problem is PSPACE­ complete. Our framework most significantly differs from theirs in that they allow a richer representation of goals (as arbitrary propositional logic formulae) and, in addition, they also assume benevolence.

6 Conclusion

Cooperation is a key process for multi-agent systems research and, as such, it has received a considerable amount of attention in the multi-agent systems literature. However, mathematical treatments of cooperation have focussed primarily on either game-theoretic or modal logic formulations.

When many agents cooperate together, a cooperation struc­ ture emerges, which can be represented formally as a directed graph with certain properties. In this paper, we have formally defined the properties that must hold of such a graph to be con­ sidered as a cooperation structure. We have shown that, even when making simplifying and limiting assumptions about the world, the problem of determining whether cooperation struc­ tures are available to achieve an agent's goal is NP-complete. The problem of computational complexity and tractability has often been overlooked in the design of multi-agent systems. In future work we wish to use our framework in order to for­ mally define other key social reasoning problems, and analyse the computational complexity of such problems. In addition, we aim to investigate algorithms for solving these problems.