Liveness and Fairness Properties in Multi-Agent Systems

1 Introduction

Problems of liveness and fairness have been studied in­ tensively for concurrent systems. But related consid­ erations are missing for multi~agent systems neverthe­ less they have been inquired e.g. already in [Bond and Gasser, 1988] . This does not mean that there are no attempts to reach fairness conditions in the multi-agent systems (e.g. by scheduling), but there is also a need to consider general problems of liveness and fairness for such systems.

This paper is an attempt to fill this gap from a view point of abstract languages. A first problem is the def­ inition of deadlock-free, live or fair agents, respectively, and of deadlock-free, live or fair multi-agent systems.

The next problem is the relationship between e.g. fair multi-agent systems and fair agents. Are the properties of a multi-agent system given by the properties of its agents, does a community of fair agents constitute a fair system?

The last question is also of interest with respect to the analysis and verification of multi-agent systems. If the properties of a system are determined by its components, then the analysis can be done by analysing these com­ ponents. But a real benefit is given only if the component analysis can be done separately for each component without regarding the whole system.

The latter implies that it must be possible to define the properties of the agents "locally" without "globally" referring to the whole system. In the paper, we shall introduce two approaches to the definition of properties for the agents in a multi-agent system. The "local" one fulfills this restriction but may be sometimes misleading with respect to the intuitive meaning of the properties we want to define. The "global" one on the other hand may sometimes better reflect the intuitive meanings, but it needs the consideration of the whole system.

The "global" notions permit also in more cases the transformation of properties of the agents to the whole system- but as stated above, this is of only limited value for a componentwise system analysis. Such phenomena are well known for the verification of concurrent systems {cf. e.g. [Owicki and Gries, 1976]), where in many cases only a global analysis is possible after the construction of the whole system.

It is interesting that the properties of deadlock­ freedom, liveness, impartiality and fairness which are considered in the paper lead to different results con­ cerning the "locally" and "globally" defined properties of agents. This can be seen as a further hint that both ap­ proaches are of interest. Under certain conditions both approaches can coincide, thereby the behaviour of an agent must be in some sense independent of the rest of the system.

As a result, the study and the analysis of properties in multi-agent systems need in general the consideration of the system as a whole. Liveness and fairness properties must be analysed for the whole system and not sepa­ rately for single agents. It turns out that the behaviour of an agent should not be defined as a "stand-alone" be­ haviour, it must be defined and considered in the context of the underlying multi-agent system.

The paper is organized as follows: The properties of deadlock-freedom, liveness, impartiality and fairness are defined on the base of abstract languages after this in­ troduction.

Then multi-agent systems are introduced in the next section. Again, abstract languages are the base for the consideration of the behaviour for both the system and the agents. The top-down approach may be the main difference to other approaches : We start with a definition of the whole system, and the components (agents) are defined as parts of it, while other approaches derive the system by combination of its constituents. Discus­ sion is needed concerning the faithful description of the behaviour of the agents in the system. The introduction of self-determined agents is dedicated to this problem.

In section 4, the properties of the agents are defined in the "global" and the "local" sense as stated above. The differences and relationships are worked out. Some differences disappear for self-determined agents.

Finally in section 5, the relationships between the properties of the system and the related properties of the agents are considered with the results as mentioned above.

Most of the proofs bad to be omitted because of lack of space.

The following notions are used: N denotes the natural numbers, w denotes "infinitely many". VW and 3"1 denote "for allmost all" and "for infinitely many", respectively.

The set of all finite sequences over a set (alphabet) T is denoted by r·, e denotes the empty word. The set of all infinite sequences overT is denoted by T'l.

By 1rw(t) we denote the number of occurences of a symbol t E T in the sequence w E r· U T'l (Parikh­ vector).

By c and ~ we denote the prefix relations. The set of all prefixes of a (finite or infinite) sequence w is denoted by Pref(w). For a set M of sequences the set of all prefixes of these sequences is denoted by Pref(M).

2 Definition of system properties

Properties like deadlock avoidance, liveness and fair­ ness are defined with respect to the behaviour of a sys­ tem. Thereby the behaviour of a system is built up from atomic action!! (or events). These actions can oc­ cur sequentially and concurrently. Different calculi have been developed for formalizing concurrent ~ebaviour ( cf. e.g. [Brookes et al., 1985; Hoare, 1985; Milner, 1989; Manna and Pnueli, 1992]), but the simple approach of nondeterministic interleaving and a description using ac­ tion sequences is sufficient to describe deadlock, liveness and fairness properties. Related approaches are com­ mon in the DAI-literature but mostly they are further exploited using several kinds of logics (e.g. in [Werner, 1989; Halpern and Moses, 1989]). In our approach (cf. [Burkhard, 1985]) the behaviour of a system can be de­ scribed by a prefix closed language L ~ r·, where T is the finite set of atomic actions of the system. A sequence p E L describes a possible sequence (history) of actions of the system. Concurrent actions appear in a nonde­ terministically chosen order. Since each prefix of such a sequence is also a possible behaviour of the system, the language L is prefix closed.

The following definitions of deadlock avoidance and liveness are well known:

1. Definition
2. let L be a prefix closed language over a finite set T.
3. (a) L is deadlock- free iff Vp E L3t E T : pt E L.
4. (b) L is live with ·respect to a subset T' ~ T (for short: T'-live )

iff Vp E LVt E T' 3r E r· : prt E L .

• (c) L is live iff L is live with respect to T.

Fairness properties concern the infinite behaviour of a system which is given by the adherence:

(2) Definition

let L be a prefix closed language over a finite set T .

The adherence of L is defined by

Adh(L) := { w E T'l /Vp E 'r : p C w - p E L}.

Now fairness can be defined in different ways with different meanings. We adopt the following ones ( cf. [Lehmann et al., 1981]}:

(3) Definition

• let L be a prefix closed language over a finite set T .
• (a) L is impartial with respect to T' ~ T (for short: T' -impartial)

iffVw E Adh(L)Vt E T': 1rw(t) = w.

• (b) Lis fair w.r.t. T' ~ T (for short: T'-fair) iff Vw E Adh(L)Vt E T' : (3 111 p C w : pt E L) - 1rw(t) = W.
• (c) L is impartial (fair) iff L is impartial (fair) w.r.t. T.

Another notion of fairness, called justice, can be ob­ tained replacing "3 111 " by· "VW" in (b). But since the results for fairness and justice coincide as far as it con­ cerns this paper, we consider fairness only. In the litera­ ture fairness is also called strong fairness or compassion [Manna and Pnueli, 1992], while justice can be found under the notion of weak fairness.

The following relations bold:

( 4) Corollary

• let L be a prefix closed language over a finite set T.
• (a) If L is impartial (w.r.t. T') then L is fair (w.r.t. T').
• (b) If Lis impartial (w.r.t. T') and deadlock-free then Lis live (w.r.t. T~. ·
• (c) If L is live (w.r.t. T') then L is deadlock-free.
• (d) Lis impartial (w.r.t. T') iff Pref(Adh(L)) is impartial (w.r.t. T').

H there are at least two elements in T then only the implications given or implicated by the corollary bold in general. Concerning some counterexamples we re­ mark that all finite languages are fair, but neither live nor deadlock-free, vice versa the language L = {a, 6}· is live and deadlock-free, but not fair. By (d) we see that impartiality relies only on the infinite behaviour of a language. All finite languages fulfill the impartiality conditions. But fairness relies on the whole language (nevertheless finite languages are fair, too).

3 Multi-agent systems

Since the properties defined above are definable in terms of languages, it is sufficient for our purposes to consider the behaviour of a system just in the form of a language. Moreover, the further description of a system, e.g. by states and state transitions, is not necessary. Clearly, given an initial state and a sequence of actions, the re­ sulting state can be computed if a transition table is known, but for the consideration of liveness and fairness properties the states are not obligatory.

In the consequence, it is sufficient to consider and to describe the systems by their behaviour, i .e. a system is given only by some prefix closed language L over a finite alphabet T where Tis the set of atomar actions (or events) and L is the set of all possible action sequences (histories) which could appear in the system. Concurrent behaviour is described by nondeterministic interleaving.

By A we denote a finite set of agents a. Each agent a has a set Ta of its individual actions. This is re­ flected by the following definition of multi-agent systems [Burkhard, 1992] .

(5) Definition

A multi-agent system (MAS) is given by M = [A, T, T, L] where

A is a finite set of agents,

T is a finite set of all actions/events occuring in M,

• T is a mapping from A into the powerset 2T ofT where Ta := T(a) is the set of all actions/events from T which are connected with the agent a E A, we suppose T = U{Ta/a E A},
• L is a prefix closed subset of T· which describes the behaviour of the multi-agent system.

The sets Ta define the restricted knowledge and the re­ stricted influence of the agents a with respect to the whole system. Here we do not suppose that the sets Ta have to be disjoint (which can be desirable from tech­ nical reasons in so;me cases). Thus shared actions or events can be denoted by the same element t (otherwise a shared action/event must be represented by different notations in each set Ta whith common occurences in the sequences from L).

The interpretation of t as an action (an agent is "ac­ tively" doing something) or as an event (an agent is a more passive one, i.e. by observing something) is left open. Thus, if an agent a is doing an action t while b observes this action, this may be described by t E Ta and t E Tb.

Following these intentions about the sets Ta we define the behaviour of the agents a in a multi-agent systems by the projections of L to the sets Ta:

(6) Definition Let M = [A, T, T, L] be a MAS, and a E A. The behaviour of a in M is given by La := ha(L) where ha is a homomorphism erasing all t ft Ta. (i.e. fortE T: ha(t) := if t ETa then t else e ).

We remark that the behaviour La of an agent a is already defined within a given multi-agent system. Here we do not make any assumptions of the behaviour as a "stand alone" agent outside of this system. In general there need not exist any relation between such a "stand alone" behaviour (if it makes a sense at all) and the behaviour of an agent in a MAS. The possibilities of an agent may be restricted by the system (e.g. by conflicts w.r.t. resources) and the possibilities may be enlarged

(e.g. by some help of other agents), respectively. To give a more formal example: the behaviour of Petri nets is restricted by merging transitions from different nets and it is enlarged by merging places, respectively.

Now we have a possibility to consider the behaviour of the whole multi-agent system on the one hand and the behaviour of the single agents in this system on the other hand. The restrictions to the sets Ta offer the possibil­ ity to consider the restricted knowledge and influence of agents in a distributed world.

There may still be problems concerning the faithful description of the behaviour of an agent. We consider as example an MAS M with two agents a and b and simply Ta = {a} and Tb = {b}. For the behaviour L = Pref({a"b"/n E N}) we have Lb = {b}·. The interpretation of this language Lb as the behaviour of the agent b gives the impression that it can perform the action b arbitrarily often (even infinitely often since bw is in Adh(Lb)) . But in the underlying multi-agent system, whenever the agent b starts its work then there exists an absolute upper bound for the following occurences of the action b.

Obviously, there are infinitely many different states in which agent b can start its work. The changes of these states are due to the actions of the agent a. Thus the information about the situation for agent b includes in­ formation about actions of a. Vice versa, to know about its situation the agent b must have information about the actions of-agent a. Here is a point to ask if the intro­ duction of states into the consideration is necessary. But changes of (individual or global) states must be due to actions in the system, and the information about state changes is given by some action/event, hence we can follow the approach of language considerations through­ out this paper. Moreover, a description of multi-agent systems with global states could contradict our aim to have individual descriptions of the agents. On the other hand, using local states for the agents would lead to re­ lated problems concerning the exchange of information as in the language based approach.

Formally the need of information exchange with re­ spect to a faithful description of the behaviour is caused by actions of an agent b which are not part of the set Ta (and hence "not observable" in La) for another agent a but which may sometimes enable or disable actions of a. The exclusion of this phenomenon is possible only to a certain extent, as the following discussion shows.

1. Definition

Let M = [A,T,T,L] be a MAS, and a EA.

• (a) a is self-determined w.r.t. T' ~ Ta in M iffV't E T' 'Vp,p' E L: ha(P) ~ ha(P')-+ (ptE L iff p't E L).
• (b) a is self-determined in M iff a is self-determined w.r.t. Ta in M.

The notion of a self-determined agent depends on the description of the system, it may be a task to find a (non­ trivial) system description such that the agents are self­ determined. Thereby a trivial description can always be given if the sets Ta are set to Ta := T.

By the definition the actions of self-determined agents are independent of "the rest" of the system, but in the case of not disjoint sets Ta this does not mean the independence of other agents at all (cf. proposition (11) below). The problem can also be considered under the aspect of communication between agents ( cf. eg. (Dur­ fee et al., 1987; Genesereth et al., 1984]). Then to be self-determined does not mean the absence of commu­ nication (which can be given by the common actions in the sets Ta)·

Several distinctions between "locally" and "globally" defined properties df agents ( cf. section 4) will disappear for self-determined agents. As a first result we can show that for a self-determined agent the infinite behaviour in the MAS is in fact determined by its behaviour La in the MAS:

(8) Proposition

Let M = (A, T, r, L) be a multi-agent system and let a be a self-determined agent from M.

Then we have ha(Adh(L)) n TN= Adh(ha(L)).

The proof uses two lemmata:

(9) Lemma: ha(Adh(L) n TN~ Adh(ha(L)) holds for any agent a in any MAS.

(10) Lemma: If a is a self-determined agent

then we have Vp E L : ha(P) E L.

If an agent a is self-determined then its actions are independent from the actions not belonging to his set Ta. So it can be shown (cf. lemma. (10)) that for any p E L the sequences ha(P) and h;r{p)ha(P) belong to L, too, where h7r is the homomorphism erasing all t ¢ Ta. But in general ha(p)h7r(p) need not belong to L since the remaining actions from T - Ta may still depend on the actions of the agent a.

We obtain a total independence of the agents in a MAS if the sets T~' are disjoint and all agents are self­ determined. The independence is expressed by the shuffle-product (the arbitrary interleaving) of the languages La. '

(11) Proposition

Let M = (A, T, r, L] be a MAS, and

let all a E A be self-determined.

Furthermore let the sets Ta be pairwise disjoint.

Then we have L = Shuff({La/a E A}).

In a further consequence, a MAS where all agents are self-determined but not totally independent from each other, can not be described with disjoint sets Ta.

Results in subsequent sections show that for self­ determined agents we may have in some cases a cor­ respondence between individual properties and system properties (via the coincidence of "locally" and "glob­ ally" defined behaviour for self-determined agents). But it depends on the description of the multi-agent system if the agents are self-determined. Clearly each agent a is self-determined if Ta = T, but then we have no distinction between individual and global be­ haviour. Hence a restricted set Ta is essential if individ­ ual behaviour and individual properties should be dis­ tinguished from global ones.

In any case if we want to benefit from self-determined agents we have to consider the agent in its environment and not as a "stand-alone" agent. Its behaviour depends to some extent on other agents. The only exception are 1ystems were the agents act totally independent from each other, but those systems are of limited interest.

4 Properties of agents

Concerning 'the question if individual properties of the agents correspond to global properties of a multi-agent system, we are obliged to define the individual properties from the individual view point of the agents. We shall discuss this in the following.

According to our definitions from above the properties concerning multi-agent systems can easily be defined:

(12) Definition Let M = [A, T, r, L) be a multi-agent system.

M is deadlock-free (live, impartial, fair)

if L has this property.

In contrast to the global definition for multi-agent sys­ tems the definition of these properties for the agents is not obvious. A first approach is of course to define e.g. deadlock-freedom of an agent a by deadlock-freedom of the language La.

But if we consider a MAS with L = Pref({ab})U{b}* and Ta = {a}, Th = { b} then we obtain the deadlock­ free language Lh = hh(L) = {b}*, while agent b can be deadlocked with respect to the sequence ab in the MAS. Thus it is useful to consider another definition, too. Concerning the example we remark that the agent b is again not self-determined. If it was then the problem could not appear as proposition (14) will show.

{13) Definition

Let M = [A, T, r, L) be a MAS, and a E A.

• (a) a is locally deadlock-free if La is deadlock-free.
• (b) a is globally deadlock-free iff'Vp E L3r E T*3t ETa: prt E L.

The relationship between the two notions is given by the following proposition. The influence of self-determined agents for th~e notions will also appear for some other properties.

(14) Proposition

Let M = [A,T,r,L) be a MAS, and a eA.

• (a) If a is globally deadlock-free then a is locally deadlock-free , but in general not vice versa.
• (b) It holds for self-determined agents a : a is locally deadlock-free

iff a is globally deadlock-free .

• (c) If M is Ta-live (i.e. if a is globally live according to the following definition) then a is globally deadlock­ free , but in general not vice versa.

With respect to liveness we have an analogous situation and we can define:

1. Definition

Let M = [A,T,r,L) be a MAS, and a EA.

• (a) a is locally live iff La is Ta-live.
• (b) a is globally live iff L is Ta-live.

Remark: If La is considered as a language over the al­ phabet Ta then in (a) we could also say that La has to be "live". Again for self-determined agents the two notions coincide.

(16) Proposition

let M = [A, T, r, L] be a MAS, and a EA.

• (a) If a is globally live then a is locally live , but in general not vice versa.
• (b) It holds for self-determined agents a:
• a is locally live iff a is globally live .

Concerning impartiality the situation changes in some sense. If we consider the example from above then L& is impartial, and there is no contradiction to the intuitive meaning of impartiality. On the other hand, it may be hard to say that the T 0 -impartiality of L is the appro­ priate definition of an impartial agent a (consider e.g. L = {a}· U {b}· and T0 ={a}, T& = {b} where Lis not { b }-impartial).

In general . (also for fairness) there are at least three points of view to consider the infinite behaviour of an agent a in a MAS.

At first we can have the "local view" and only con­ sider the infinite sequences from Adh(La)· But we re­ mark that this may lead to unexpected results as in the case of L = {a"b" /n E N}, T& = {b}, where we obtain Adh(L&) = {bw} while there is no infinite behaviour for bin the system.

On the other hand we can relate the definitions to Adh(L) and adopt the definition of T0 -impartiality.

Finally we can restrict the infinite behaviour to the sequences from ha(Adh(L))nTw. In general this is only a subset of Adh(La) by lemma (9), but in the case of self­ determined agents both sets coincide. The last approach can be applied in different ways to the fairness notions. In this case also some differences between fairness and justice occur, but this is left for a subsequent paper.

Following the first two possibilities we can define:

(17) Definition

let M = [A,T,r,L] be a MAS, and a EA.

• (a) a is locally impartial iff La is T0 -impartial.
• (b) a is globally impartial iff L is T0 -impartial.

In the case of impartiality the "local" and the "global" notions are different even for self-determined agents.

(18) Proposition

let M = [A,T,r,L] be a MAS, and a EA.

• (a) If a is globally impartial then a is locally impartial, but in general not vice versa ( cf. (b)).
• (b) Even for self-determined agents a there exists the possibility that a is locally impartial but not globally impartial.

Concerning fairness the situation changes again.

1. Definition

let M = [A, T, r, L] be a MAS, and a E A.

• (a) a is locally fair iff La is T0 - fair.
• (b) a is globally fair iff Lis T0 -fair.

(20) Proposition

let M = [A,T,r,L] be a MAS, and a EA.

• (a) The notions of global fairness and local fairness are in general not comparable.
• (b) let a be a self-determined. If a is globally fair then a is locally fair , but in general not vice versa.

The relationships between the "globally" and the "lo­ cally" defined properties are different for the considered properties which we interprete as a kind of independence for the both approaches. Furthermore in some cases the two related notions are even incomparable. In all cases they are more close for self-determined agents.

With regard to the problem of correspondence be­ tween system properties and individual properties the "locally" defined notions are preferable since the "glob­ ally" defined notions always have in mind the behaviour of the whole system. But as discussed in the sec­ tion before, the languages La may sometimes not faith­ fully reflect the behaviour of an agent if it is not self­ determined.

5 Relationships between system properties and properties of the agents

Now we are going to study the relationships between the properties of the agents and the properties of the multi­ agent system.

It turns out that in the case of the "local" definitions there is almost no coincidence with the system proper­ ties. On the other hand, the "global" definitions coincide in many cases with the system properties. An exception is deadlock-freedom. We start with the consideration of the "global" notions:

1. Proposition
2. (a) let M = [A, T, r, L] be a multi-agent system. If at least one agent a E A is globally deadlock-free then M is deadlock-free .
3. (b) There exist deadlock-free multi-agent systems M = [A, T, T, L] where all a E A are not globally deadlock-free .

For the remaining properties it follows immediately from the definitions:

(22) Proposition

let M =[A, T, T, L] be a multi-agent system.

M is (1) live [(2) impartial, (3) fair, resp.]

iff all agents a E A are (1) globally live

• [(2) globally impartial, (3) globally fair , resp.].

Since the "global" properties are defined (and hence provable) in the context of the whole system, the re­ sults from above may be of limited value for the analy­ sis of systems by analysing the behaviour of the agents. The "local" properties may be more relevant. But the next propositions show that the "local" properties do in many cases not coincide with the system properties. As already mentioned the self-determined agents are of interest from this reasons if for them the "global" properties correspond to "local" properties. Via such a correspondence the results from above are useful.

(23) Proposition Let M =[A, T, r, L] be a multi-agent system. If M is (1) live [(2) impartial, resp.] then all a E A are (1) locally live [(2) locally impartial, respectively].

(24) Proposition

There are multi-agent systems M =[A, T, r, L] which are (1) deadlock- free [(2) fair, resp.] but where all a E A are (1) not locally deadlock- free [(2) not locally fair, respectively].

(25) Proposition

There are multi-agent systems M =[A, T, r, L] which are (1) not deadlock-free

[(2) not live, (3) not impartial, (4) not fair, resp.] but where all a E A are (1) locally deadlock- free [(2) locally live, (3) locally impartial, ( 4) locally fair, respectively] .

If we do not regard self-determined agents then the results are mostly negative concerning the correspon­ dence between properties of a system and properties of its agents, where the last ones are not defined using the behaviour of the whole system (otherwise several corre­ spondences are trivial).

The situation changes for self-determined agents. But then the problem of the context of an agent is only transfered since the notion of a self-determined agent itself may depend on the multi-agent system as a whole.

6 Conclusions

We have collected results concerning the correspondence between individual (local) properties of the single agents and the related properties of a multi-agent system. The question was if the properties of the whole system are given by the properties of its parts and vice versa. The answers to these questions are not unique. They depend on the properties in mind and they depe~d on the way of defining the individual properties of the agents. As less as these definitions make use of the context, i.e. of the behaviour of the whole system, as less exists a corre­ spondence between the properties of the agents and the properties of the system.

In the consequence, an analysis of system properties has to consider in general the behaviour of the whole system, it can not be done by analysing the parts of the system without regarding their context given by the sys­ tem. In the same sense the construction of systems with special properties can in general not be broken down only to the construction of related components.

There are different reasons to neglect approaches such as e.g. "build a fair system by cooperation of fair agents". Thereby these reasons are of different mean­ ing depending on the choosen approach.

The first reason is the problem to transform the "fair behaviour" of a "stand-alone" agent into a "fair be­ haviour" of the agent in the context of a multi-agent system as mentioned in section 3. The next reason are the problems to describe the fair behaviour of an agent without referring to the whole system (section 3 and 4). The last reason is that the combination of fair agents need not lead to fair systems (section 5).

All these reasons are in the one or other form rele­ vant for the different properties under different condi­ tions. Thus we conclude that system properties can not be achieved only by the interaction of agents "with this property". In the same tendency, the analysis of system properties can not be realized by a separate analysis of the single agents. In general a system must be analysed as a whole.

But there may be special conditions and laws of inter­ action and cooperation which permit the composition of special agents in order to obtain special system proper­ ties or which allow a separate analysis, respectively.