An Abstract Model for the Process of Deliberation within Multiagent Systems

A. G. Stankevicius  G. R. Simari

Laboratorio de Investigación y Desarrollo en Inteligencia Artificial Departamento de Cs. de la Computación - Universidad Nacional del Sur

Bahía Blanca - Buenos Aires - ARGENTINA

                  e-mail: {ags,grs}@cs.uns.edu.ar

Abstract

A multiagent system is no more than a collection of interacting autonomous agents. However, this interaction allows the system as a whole to perform tasks beyond the reach of its individual members. This clearly accounts for the boost in research geared towards profitting from this interaction. Accordingly, this paper addresses the formal modeling of a common kind of interaction known as deliberation. Simply put, a group of agents deliberate whenever they need to come to a mutually accepted position on some matter. The proposed model stems from the newly developed trend of reinterpreting agent interactions as an exchange of arguments in the context of some theory of defeasible argumentation.

Keywords: deliberation, defeasible argumentation, multiagent systems.

1 Introduction

A multiagent system is no more than a collection of interacting autonomous agents. However, this interaction allows the system as a whole to perform tasks beyond the reach of its individual members. The customary example depicts a heavy armchair, easily lifted by coordinating the effort of a few freighters, still an unbearable burden for each one of them alone. This clearly accounts for the boost in research geared towards profitting from this interaction. The literature has already explored notions such as agent coordination, cooperation, or collaboration in the context of multiagent systems. Accordingly, this paper addresses the formal modeling of a common kind of interaction known as deliberation.

Simply put, a group of agents deliberate whenever they need to come to a mutually accepted position on some matter. The proposed model stems from the newly developed trend of reinterpreting agent interactions as an exchange of arguments within the context of a theory of defeasible argumentation. For instance, pursuing this approach Parsons et al. introduced a model for multiagent negotiation [3, 6] derived from the theory of defeasible argumentation due to Krause et al. [4], and also Stankevicius et al. defined a negotiation framework [12, 13] built around the theory of defeasible logic programming [2]. These formalisms exploit the structural similarities between multiagent interaction and the process of obtaining inferences in the dialectical characterizations of defeasible argumentation. This fruitful analogy was first emphasized by the philosopher Nicholas Rescher in his essay on the role of dialectics in scientific inquiry [10]. In this work, Rescher envisioned knowledge discovery as a dialectical process, where new ideas could be discussed and analyzed, weighting reasons for and against them, and determining whether they should stand. Briefly stated, his main contribution was a protocol for governing these disputes. Rescher also postulated another striking conjecture: according to his findings, unilateral and multilateral dialectic are in fact isomorphic.^{1} This keen observation established the aforementioned analogy between the sort of debate that takes place inside the mind of a researcher testing new hypotheses, and the kind of dispute that arise when these results are presented to rest of the scientific community.

Rescher’s isomorphism allows us to reinterpret any model of agent interaction as if it were a model of dialectical reasoning, and conversely to reinterpret any model of dialectical reasoning as if it were a model of agent interaction. Since multiagent deliberation is in fact a particular form of agent interaction, this paper adopts the latter strategy. To this purpose, we plan to take advantage from those well established models of dialectical reasoning introduced in the literature as follows: section 2 depicts a framework for dialectical reasoning that abstracts away many of those models. Then, Section 3 applies Rescher’s isomorphism to the model just obtained, reinterpreting it as a model of the process of deliberation. Finally, section 4 surveys the related work in the literature, and section 5 summarizes the main results obtained in this paper.

2 An abstract model of dialectical reasoning

This section covers the first half of our strategy: to elicit an abstract model of dialectical reasoning. Given that dialectical argumentation has always been the formalism of choice for reasoning in dialectical terms, our set of definitions are the outcome of a careful analysis of several theories of dialectical argumentation (e.g., [11, 8, 2] among others). Unfortunately, this insightful analysis and its conclusions fall beyond the scope of this paper. (Not withstanding, we refer the avid reader to [9, 1] for in-depth surveys of these and many other theories of defeasible argumentation.)

The following section introduces the intuitions behind our model, deferring its formal definition until section 2.2.

2.1 Discussion

Lets consider an scenario where an agent is about to weight a certain claim through a dialectical dispute. Clearly, it takes at least to contenders to dispute: one defending the claim (called proponent), and one attacking it (called opponent). In this context, both proponent and opponent are enacted by the same agent switching back and forth between these roles. Reasons posed in the dispute must be supported by agreed-upon premises. These premises are kept inside the agent’s knowledge base. Proponent and opponent use this knowledge base to build arguments; the former backs the claim being disputed, and the latter challenges or attacks it.

Considering the structure of these disputes, they can be easily reinterpreted as a game where each move conveys a reason. This particular view provides us with a conceptual framework that simplifies the introduction of more elaborate concepts. Reasons within this game are raised to fulfill a purpose. Note that reasons are arguments, and that the purpose of an arguments is to counterargue another argument. Thus, the notion of move must accommodate arguments and their targets.

1we have found this to be not entirely true. See section 3 for further details.

Sometimes, proponent and opponent exchange arguments comprising a certain line of reasoning until it gets exhausted. This situation, fairly common in actual disputes, denotes the traversing of a line of argumentation [11]. Simply put, a line of argumentation is a sequence of related moves (an argument followed by one of its counterargument, then followed by a counterargument of the first counterargument, and so on). Our entire model of dialectical reasoning rests upon this notion, since gathering lines of argumentation allows us to describe any conceivable dispute. Furthermore, the set of argumentation lines being explored in a dispute represents a snapshot of its current state.

Once established what the state of dispute is, several question regarding its prospect arise:

• Which contender is next to move?

• What are the legal moves available?

• Is this dispute over? If so, who has prevailed?

Given that the precise answer to these question induces a particular theory of defeasible argumentation, our formal definitions leave them unspecified. In doing so, this model clearly increases its applicability since it becomes more generic.

Last but not least, there must be a function prescribing the effect of playing a move in a dispute. This function in fact captures the dynamics of a dispute: it relates the states before and after taking into account a certain move in the context of some dispute. This completes the overview of our model of dialectical reasoning. We cannot further refine these notions without introducing their formal definitions.

2.2 Formal definitions

This section formally defines the abstract model of defeasible reasoning briefly sketched in the previous section. In the outset, a dialectical dispute over a certain claim C involves two contenders: the proponent P, and the opponent O. Let KB be the knowledge base available to both, and let args(P) = args(KB) = args(O) be the set of all the possible arguments that can be build using the information stored in KB. Note that the internal structure of these arguments is of little concern to our present purpose and it shall be ignored.

Definition 2.1 (move) A move is a tuple (contender, argument, line), where contender is either P or O, argument is an arguments in args(contender), and line is a line of argumentation on some claim. ■

One might argue that the concept of move is too unconstrained. In fact, against all intuitions it seems to be somewhat independent of the claim being disputed. We deal with this issue later on, but before that we must introduce some preliminary notions.

In the previous section we have structured moves into sequences to denote lines of argumentation. However, not every sequence of moves models valid lines of argumentation. For instance, a sequence of moves accruing unrelated arguments does not seem to be a line of argumentation. The following definition takes this into account:

Definition 2.2 (line of argumentation) Let C be a claim. A line of argumentation on C is a sequence of moves ⟨m_{0}, m_{1}, …, m_{k}⟩, such that:

• m_{0} = (P, argument, ⟨⟩), where argument is an argument backing C, and

• for every i, 1 ≤ i ≤ k, it is the case that m_{i} ∈ legal(⟨m_{0}, …, m_{i−1}⟩).

■

The first move in every argumentation line must back the claim being disputed. In addition, since it does not counterargue another argument it has to pertain to the empty line of argumentation (denoted as ‘⟨⟩’). For the general case, legal stands for a function from Lines into 2^{|Moves|}, where Lines is the set of all the conceivable lines of argumentation, and Moves is the set of all the possible moves. This function returns the set of moves that are allowed to further extend a given line of argumentation. This function allows us to discard nonsensical moves such as those mixing an argument with an unrelated line of argumentation. By combining the function legal with the notion of move we can refine it to its final shape:

Definition 2.3 (move revisited) A move is a tuple (contender, argument, line), where contender is either P or O, argument is an arguments in args(contender), and line is a line of argumentation on some claim such that (contender, argument, line) ∈ legal(line). ■

According to what we have argued in the previous section, the state of a dispute can be formalized as an unordered collection of lines of argumentation. That is to say:

Definition 2.4 (state of a dispute) Let C be a claim. The state of a dispute about C is a set of lines of argumentation on C. ■

From the state of a dispute we should be able to answer the questions raised in the previous section, such as who is next to move or which contender prevailed in the dispute. It is clear that we must not restrict this model to only those answers we consider appropriate; instead we leave these features unspecified so to obtain a model as generic as possible. Therefore, these questions are addressed through the following abstract functions, where States represents the set of all the possible states of disputes:

• toMove, a function from States into {P, O}, that given the state of a dispute about a claim returns which contender is next to move.

• winner, a function from States into {P, O} ∪ {none}, that given the state of a dispute about a claim returns which contender (if any) has won the dispute.

The function toMove models the burden of the proof^{2} that shifts sides throughout the dispute. We assume that the functions legal and toMove agree with each other, at least in the sense that the contender playing each move in the sequence ought to be whichever toMove would have determined if this sequence were the only line of argumentation explored in the dispute. This can be achieved by making the function legal satisfy the following restriction:

(contender, argument, line) ∈ legal(⟨m_{0}, …, m_{n}⟩) ⇒ contender = toMove({line})

2in Rescher’s terms.

The last component of our abstract model is the function next, defined from States×Moves into States, that given a move about to be played in a certain state computes its resulting state. Once again, this function is left unspecified and should be instantiated accordingly when modeling a particular theory. Within our model, next is the only component able to modify the state of a dispute. That is to say, nothing else can create, change, or eliminate lines of argumentation. As we mentioned before, the function next captures the dynamics of the dispute. This notion allow us to define an abstract entailment relation.

Definition 2.5 (entailment) Let C be a claim. We say that C is entailed by a particular instantiation of this framework if, and only if, there exist a finite sequence s_{0}, s_{1}, …, s_{n} of states of disputes about C such that:

• for every i, 0 ≤ i ≤ n − 1, winner(s_{i}) = none and there exists a line line ∈ s_{i}, and a move move ∈ legal(line), such that next(s_{i},move) = s_{i+1}.

   • winner(s_{n}) = P.

■

This completes the formal definition of our abstract model of dialectical argumentation. Despite its apparent simplicity, this model is able to describe a wide variety of theories of defeasible argumentation, even those that admits some sort of comparison criteria between arguments. (Should that be the case, the function legal must be extended accordingly to include these criteria.)

3 An abstract model of deliberation

In accord to the strategy depicted in the introduction, we should now reinterpret the abstract model introduced in the last section as if it were a model of deliberation. This is almost immediate due to Rescher’s isomorphism, but there is a subtlety we should not neglect. It is clear that within unilateral dialectics there is only one source of premises upon which found reasons. However, in multilateral dialectical there are as many sources of premises as parties involved in the dispute. This rather naive observation breaks down Rescher’s isomorphism. Even though, this objection can be addressed by simply taking into account what Rescher did not.

In what follows, we formally defines our proposed model of deliberation. Note that we are mainly concerned with the actual deliberation: its initial setup or the account of its outcome [14] are irrelevant to the present purpose. A dialectical dispute over a certain claim C now involves several agents: P_{1}, P_{2}, …, P_{n} backing C, and O_{1}, O_{2}, …, O_{m} attacking it. Let Agents be the set of all the agents involved in a dispute (i.e., Agents = {P_{1}, …, P_{n}, O_{1}, …, O_{m}}). What Rescher did not include in his isomorphism can be overcame by allowing each agent to have its own knowledge base. For each Ag ∈ Agents, let KB(Ag) be the knowledge base of the agent Ag, and args(Ag) be the set of all the possible arguments that can be build using the information stored in KB(Ag). Recall that, once again, the internal structure of these arguments shall be ignored for the present purpose. In this new context, the revisited notion of move remains almost unchanged.

Definition 3.1 (move) A move is a tuple (Ag, argument, line), where Ag ∈ Agents, argument ∈ args(Ag), and line is a line of deliberation on some claim such that (Ag, argument, line) ∈ legal(line). ■

The former notion of line of argumentation now models lines of deliberation. Accordingly, let Lines be the set of all the conceivable lines of deliberation, and Moves the set of the possible moves. The function legal still assumes the same role as before, that is, a function from Lines into 2^{|Moves|} that returns the set of moves that are allowed to further extend a given line of deliberation.

Definition 3.2 (line of deliberation) Let C be a claim. A line of deliberation on C is a sequence of moves ⟨m_{0}, m_{1}, …, m_{k}⟩, such that:

• m_{0} = (P_{i}, argument, ⟨⟩), where P_{i} ∈ {P_{1}, …, P_{n}} and argument is an argument backing C, and

• for every i, 1 ≤ i ≤ k, it is the case that m_{i} ∈ legal(⟨m_{0}, …, m_{i−1}⟩).

■

Not surprisingly, the state of a deliberation is characterized through an unordered collection, this time of lines of deliberation.

Definition 3.3 (state of a deliberation) Let C be a claim. The state of a deliberation about C is a set of lines of deliberation on C. ■

Note that those questions posed in the context of dialectical argumentation remain relevant in this new setting. Following a like approach, we introduce an analogous set of auxiliary functions:

• toMove, the function from States^{3} into 2^{|Agents|} that given the state of a deliberation about a claim returns the set of agents that might move next.

• winner, the function from States into 2^{|Agents|} ∪ {none} that given an state of a deliberation about a claim returns which party (if any) has prevailed in it.

The discussion from the previous section also applies here. In particular, toMove and legal must agree on how agents take turns when pursuing a given line of deliberation. Formally stated, the following restriction must be observed:

(Ag, argument, line) ∈ legal(⟨m_{0}, …, m_{n}⟩) ⇒ Ag ∈ toMove({line})

The function next, also left unspecified in this abstract model, is defined in a like manner from States×Moves into States. For any given state of a deliberation, it computes the successor state obtained from playing a certain move in that state. Note that this function is capturing the dynamics of a deliberation once again. Considering this, we can define a similar entailment relation.

Definition 3.4 (entailment) Let C be a claim. We say that C is entailed by a particular instantiation of this framework if, and only if, there exist a finite sequence s_{0}, s_{1}, …, s_{n} of states of deliberation about C such that:

3this time standing for the set of all possible states of deliberations.

• for every i, 0 ≤ i ≤ n − 1, winner(s_{i}) = none and there exists a line line ∈ s_{i} and a move move ∈ legal(line), such that next(s_{i},move) = s_{i+1}.

• winner(s_{n}) ⊆ {P_{1}, …, P_{n}}.

■

It should be stressed that the strategy we have pursued in developing this abstract model of multiagent deliberation has induced a framework for distributed argumentation: each agent can argue from its own position about the claim that prompted the deliberation, or about a previous argument posed by another agent. Moreover, a natural form of collaboration—another kind of agent interaction—arises among those agents in the same party, since they are all contributing to the same goal. For instance, an agent can assist a fellow agent in attacking a strong argument the latter cannot rebut on its own.

4 Related work

This sections briefly overviews the related work in the literature, commenting their main results. To begin with, the approach we have developed toward modeling multiagent interaction was first suggested in the groundbreaking work [5] of R. Loui. In this article, Loui pondered the existence of a generic model for argument-based dialectical reasoning. He successfully introduced a set of abstract notions that were able to capture the dynamics of many attractive theories of defeasible argumentation. However, Loui involvement with this approach was rather tangential since he was mainly concerned with adding resource-boundedness into defeasible argumentation. Despite of this, Loui’s style of presenting new ideas have certainly influenced many of the design decisions behind our own model.

Later on, H. Prakken drove Loui’s work in single-agent dialectical reasoning into what he calls dynamic multiagent debates [7]. He proposed a somewhat messy model of dialectical argumentation in accord to Loui’s designs. Following an strategy similar to ours, he then reinterpreted his model as a model of multiagent interaction. It should be noted that Prakken’s goal was to allow the agents taking part in a debate to dynamically modify their knowledge bases. In contrast, our model concerns only with static debates. We strongly believe further experimentation on static multiagent deliberation is required before exploring these more involved scenarios. Unfortunately, Prakken’s proposal falls short of expectations. Like Rescher, he also assumed that all the intervening parties in the debate share the same knowledge base. This natural assumption in the single agent scenario becomes unsustainable in the context of a multiagent system.

5 Conclusions

In this paper, we have outlined a strategy for developing a model of multiagent interaction (i.e., multilateral dialectics) from a model of dialectical reasoning (i.e., unilateral dialectics). This strategy was largely motivated after Rescher’s claim that unilateral and multilateral dialectics are isomorphic. In order to do so, we have defined an abstract model of dialectical argumentation—the preferred way of reasoning in dialectical terms. This abstract model of dialectical argumentation was later reinterpreted as an abstract model of multiagent deliberation, a rather recurrent type of multiagent interaction.

Bear in mind that as an abstract model, any property established over it is immediately inherited by all its instances. This observation highlights an attractive avenue of future work. In addition, another aspect deserving further examination is the connection (if any) between the properties satisfied by the entailment relation and the restrictions imposed over the unspecified components.

To conclude, this model is being tested against several deliberation benchmarks gathered from the literature. We expect a better outcome given its higher level of abstraction when compared with previous proposals.

References

[1] Chesñevar, C. I., Maguitman, A., and Loui, R. P. Logical Models of Argument. ACM Computing Surveys 32, 4 (2000), 337–383.

[2] García, A. J. Programación en Lógica Rebatible: Lenguaje, Semántica Operacional, y Paralelismo. PhD thesis, Departamento de Ciencias de la Computación, Universidad Nacional del Sur, Bahía Blanca, Argentina, Dec. 2000.

[3] Jennings, N. R., Parsons, S., Noriega, P., and Sierra, C. On argumentationbased negotiation. In Proceedings of the International Workshop on Multi-Agent Systems (Boston, United States, 1998).

[4] Krause, P., Ambler, S., Elvang-Goransson, M., and Fox, J. A logic of argumentation for reasoning under uncertainty. Computational Intelligence 11, 1 (1995), 113–131.

[5] Loui, R. P. Process and Policy: Resource-Bounded Nondemonstrative Reasoning. Computational Intelligence 14 (1998), 1–38.

[6] Parsons, S., Sierra, C., and Jennings, N. Agents that Reason and Negotiate by Arguing. Journal of Logic and Computation 8, 3 (1998), 261–292.

[7] Prakken, H. Relating protocols for dynamic dispute with logics for defeasible argumentation. To appear in Synthese 2001, special issue on New Perspectives in Dialogical Logic.

[8] Prakken, H., and Sartor, G. Argument-based extended logic programming with defeasible priorities. Journal of Applied Non-classical Logics 7 (1997), 25–75.

[9] Prakken, H., and Vreeswijk, G. Logical systems for defeasible argumentation. In Handbook of Philosophical Logic, D. Gabbay, Ed. Kluwer Academic Publisher, 1999. To appear.

[10] Rescher, N. Dialectics: A Controversy-Oriented Approach to the Theory of Knowledge. State University of New York Press, Albany, United States, 1977.

[11] Simari, G. R., Chesñevar, C. I., and García, A. J. The Role of Dialectics in Defeasible Argumentation. In Proceedings of the XIV Conferencia Internacional de la Sociedad Chilena para Ciencias de la Computación (Concepción, Chile, Nov. 1994), Universidad de Concepción, pp. 111–121.

[12] Stankevicius, A. G., and García, A. J. Modelling Negotiation Protocols in a Dialectical Framework. In Proceedings del 6to Workshop sobre Aspectos Teóricos de la Inteligencia Artificial (ATIA), 1er Workshop de Investigadores en Ciencias de la Computación (WICC) (San Juan, Argentine, May 1999), Universidad Nacional de San Juan, pp. 69–76.

[13] Stankevicius, A. G., and García, A. J. Could negotiation among agents be regarded as an argumentative process? In Proceedings del 7mo Workshop sobre Aspectos Teóricos de la Inteligencia Artificial (ATIA), 2do Workshop de Investigadores en Ciencias de la Computación (WICC) (La Plata, Argentine, May 2000), Universidad Nacional de La Plata, pp. 22–25.

[14] Stankevicius, A. G., and Simari, G. R. A Framework for Multiagent Deliberation Based on Dialectical Argumentation. In Proceedings del 1er Workshop en Agentes y Sistemas Inteligentes (WASI), 6to Congreso Argentino de Ciencias de la Computación (CACiC) (Ushuaia, Argentine, Oct. 2000), Universidad Nacional de la Patagonia San Juan Bosco, pp. 1469–1480.