Context Independent Properties in Deliberation Protocols

A. G. Stankevicius^{∗}  A. J. García

Laboratorio de Investigación y Desarrollo en Inteligencia Artificial Departamento de Ciencias e Ingeniería de la Computación Universidad Nacional del Sur Bahía Blanca - Buenos Aires - ARGENTINA

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

1 Motivations

Multiagent systems provide a natural, intuitive model for a wide array of real world problems, where possibly heterogeneous components strive towards a common goal. Under the multiagent approach, these components can be implemented as independent agents. This ample flexibility has swayed a number of developers into adopting this scheme when dealing with industrial scale problems. On many of these systems, one can observe an striking phenomenon: the system as a whole is able to reach objectives beyond the individual capabilities of its members. For instance, suppose there are two roommates, and depict a large desk heavy enough to make changing its location an impossible task for either of them. However, the desk can be easily moved if they agree to coordinate their effort. This simple example underscores the important role of the interaction among agents in these systems. This interaction, when conducted in an orderly fashion, increases the potential of the system as a whole.

The literature also emphasizes the role of the interaction, since a great deal of attention has been devoted to developing formal models for it. For instance, the theory of speech acts [4], initially conceived as a formal model of human interaction has also been adapted as a model of agent communication. More recently, the development of agent communication languages [11] such as KQML or FIPA-ACL evidences a keen interest on the subject. Finally, other researchers have aimed their work towards particular kinds of interactions, such as multiagent collaboration, negotiation, decision making, or task delegation and supervision among others. Despite all this effort, no consensus has been reached when it comes to choosing a model for a given situation: many are applicable only when certain strict conditions are met, or when huge responsibilities rest upon the knowledge engineer, such as making most of the critical decisions beforehand.

Nowadays, the interest in analyzing the interaction among agents is still intact, always willing to explore new possibilities. For example, a new approach has been unveiled during the past decade, reinterpreting agent interaction as if it were the result of an argumentation process. Many promising formalisms were developed under this conception, such as the negotiation protocol of Parsons et al. [2], or the work on dispute protocols of Prakken [3], that follows the ground-breaking work of Loui [1]. In accord to this point of view, we have evolved the concept of deliberation protocol over a series of papers [7, 8, 9, 5, 10], where an abstract model subsuming the common characteristics of several argumentation formalisms is later reinterpreted as a model of the particular kind of agent interaction known as deliberation. Two or more agents deliberate whenever they want to reach a common position regarding some controversial topic.

∗Partially supported by CIC (Comisión de Investigaciones Científicas de la Provincia de Buenos Aires).

This extended abstract provides an outline on how to establish the properties a given family of deliberation protocols might posses without having to adapt the demonstration for each concrete context. In order to do so, we first give an overview of the main notions related to deliberation protocols, and then discuss the proposal itself.

2 Deliberation Protocols

A deliberation protocol models the interaction between a set of agents willing to deliberate about some controversial issue. This set of agents is split into two teams: those initially supporting the issue under consideration, and those initially against it. The resemblance with the starting setup of a dialectical analysis—like the one present in many theories of defeasible argumentation—is not casual, and has been the cornerstone of the evolution of this concept. Given the space restrictions, we will only be able to sketch an overview, having to refer the interested reader to its detailed formulation [6].

Throughout the actual deliberation, the agents actively exchange reasons supporting or attacking each others claims, in an attempt to bring about their own posture regarding the initial topic. It should be noted that the deliberation protocol only deals with the exchange of information during the actual deliberation. Notwithstanding, it is involving a particular set of agents, each possessing an independent mental state, which in term allowed them to formulate different reasons, possibly expressed in a knowledge representation language common to all. These aspects constitute the context upon which the deliberation takes place.

Definition. (deliberation context) We will call context the tuple C = (L, Agents_{P}, Agents_{O}, KBs, args), where:

• L is a knowledge representation language capable of expressing arguments.

• Agents_{P} is the set of agents supporting the thesis under consideration.

• Agents_{O} is the set of agents opposing the thesis under consideration.

• KBs is the set of the knowledge bases of each of the agents in Agents_{P} ∪ Agents_{O}, all of them expressed in terms of L.

• args is a mapping between knowledge bases and the set of all the arguments that can be constructed from the knowledge in those bases.

■

Observe that almost no requirements are imposed over the elements of the context, since one of the design objectives of this theory was to make it applicable to as many situations as possible. Having a formal notion of context, it is now possible to introduce the main components of a deliberation protocol.

Definition. (deliberation protocol) Let C be a context. We say that a deliberation protocol for C, noted 𝔻ℙ_{C}, is the tuple

(Moves, Lines, States, legal, toMove, winner, next)

where:

• Moves is the set of valid moves.

• Lines is the set of valid lines of deliberation.

• States is the set of all the possible states of deliberation.

• legal is a function from Lines into P(Moves), which determines the set of moves allowed to extend a given line of argumentation.

• toMove is a function from States into P(Agents), which returns the set of agents that might make the next move in that particular configuration.

• winner is a function from States into P(Agents) ∪ {none}, which determines the team that has prevailed the deliberation. If there are valid lines of deliberation still unexplored, the constant none is returned, making explicit that no team has prevailed yet.

• next is a function from States × Moves into States, which captures the effect of playing a certain move in a given state of a deliberation.

■

The intuition captured above is that the deliberation itself resembles a dialogical game, like those usual within dialectical reasoning. As a result, the exchange of reasons can be interpreted as a tree (actually, as a set of branches), where each path from the root to a leaf in this tree represents the exchange of reasons regarding a certain aspect of the main issue. These reasons are structured as moves, with each move containing the identification of the agent playing it, the reason being communicated, and the line of deliberation being referred to (where the new reason possibly defeats the last one in that line). The moves exchanged regarding some aspect of the main issue are then structured into a line of deliberation, with a set of those lines representing the current state of the deliberation.

Finally, there are four auxiliary functions that characterize the intended behavior of the deliberation. The function legal allows one to restrict the set of reasons that can extend a given line of deliberation; toMove determines which agents are allowed to make the next move (perhaps the same team might be allowed to expose several reasons at once, or it might the case that the teams are expected to take alternate turns to introduce new reasons). The function winner embodies the winning criterion adopted for the deliberation. Making the opponents run out of valid reasons is a frequent choice, but this function can capture any of them. Finally, the function next implements the update that takes place in the pool of reasons when a new move is considered. All these elements interact with each other to give rise to the following notion of entailment:

Definition. (entailment) Let 𝔻ℙ_{C} = (Moves, Lines, States, legal, toMove, winner, next) be a concrete instance^{1} of a deliberation protocol, and let t be a thesis. We say that t is entailed by 𝔻ℙ_{C} if, and only if, there exists a finite sequence s_{0}, s_{1}, …, s_{n} of states of a deliberation, such that:

1that is to say, each of its components are completely specified.

• s_{0} = {⟨(agent, A, ⟨⟩)⟩}, for some agent agent ∈ Agents_{P}, and some reason A, available to this agent, establishing t.

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

• Agents_{P} ⊆ winner(s_{n}).

■

Simply put, a given thesis is entailed by a particular deliberation protocol in a certain context if after considering all the reasons regarding that thesis, the proponents still withstand the objections raised by the opponents.

Working with an early formalization of this protocol, it became apparent that two of its components were referring the same object, yet they were not required to concord. Specifically, both toMove and legal make a suggestion regarding which agents might move next. On the one hand, toMove singles out which agents can make the next move. On the other hand, legal indicates the set of moves that can be played next, yet a move in this context encompasses not only the reason being exposed but also the agent providing that reason. That is to say, legal might allow moves played by an agent not permitted to move next by toMove. This contingency, not addressed in related works by other authors such as [3], can be easily taken into account by imposing the additional restriction that whenever (agent, reason, line) ∈ legal(line), then it must be the case that agent ∈ toMove({line}). Note that imposing a restriction on the interaction of the components of an uninstantiated deliberation protocol ensures that this particular restriction will be met by all its instances. That is to say, if we were able to prove some desired property by making some restriction upon the behavior of a particular component, or upon the interaction between them, then that desired property will be observable in all the instances of that deliberation protocol.

This constitute an interesting avenue for further research, as it provides a way of ascertaining protocol properties without having to deal with its particular instances. We are currently looking into this, exploring the effect of making assumptions on the behavior of the function next—which plays a major role in this setting, in order to see whether the resulting entailment relation satisfies the standard desired properties, such as consistency, completeness, soundness, and others.

3 Summary

Multiagent technology looks quite promising. Under this conception, tough, complex problems have been tackled with a satisfactory outcome when compared against previously achieved results. It seems clear now that the interaction among the agents is playing a key role in these systems. Accordingly, the community has reflected this focusing its attention in the past few years on the pursuit of adequate models of agent interaction, under all its forms, ranging from mere message passing to intricate negotiation protocols. In a like manner, we developed the concept of deliberation protocol, a formalism capable of modelling the information exchange and outcome of a deliberation among multiple agents. Even though this notion is abstract in nature (allowing several possible instantiations, depending on the context in mind), it is possible to restrict the interaction among its components in order to ensure the satisfaction of a certain property in all its instances. This constitutes a methodology for establishing properties on deliberation protocols in a context independent way.

References

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

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

[3] Prakken, H. Relating protocols for dynamic dispute with logics for defeasible argumentation. Synthese 127, 1/2 (2001), 187–219.

[4] Searle, J. R. Speech Acts: An Essay in the Philosophy of Language. Cambridge University Press, 1970.

[5] Stankevicius, A. G. Modelling Multiagent Deliberation from an Abstract Standpoint. In Proceedings del 8vo Workshop sobre Aspectos Teóricos de la Inteligencia Artificial (ATIA), 3do Workshop de Investigadores en Ciencias de la Computación (WICC) (San Luis, Argentina, May 2001), Universidad Nacional de San Luis.

[6] Stankevicius, A. G. Un Modelo Dialéctico para la Deliberación Multiagente. Master’s thesis, Departamento de Ciencias e Ingeniería de la Computación, Universidad Nacional del Sur, Bahía Blanca, Argentina, 2004.

[7] 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, Argentina, May 1999), Universidad Nacional de San Juan, pp. 69–76.

[8] 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, Argentina, May 2000), Universidad Nacional de La Plata, pp. 22–25.

[9] 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, Argentina, Oct. 2000), Universidad Nacional de la Patagonia San Juan Bosco, pp. 1469–1480.

[10] Stankevicius, A. G., and Simari, G. R. An Abstract Model for the Process of Deliberation within Multiagent Systems. In Proceedings del 2er Workshop en Agentes y Sistemas Inteligentes (WASI), 7mo Congreso Argentino de Ciencias de la Computación (CACiC) (El Calafate, Oct. 2001), Universidad Nacional de la Patagonia Austral, pp. 1017–1026.

[11] Yannis Labrou, T. F., and Peng, Y. Agent communication languages: The current landscape. Intelligent Systems 14, 2 (1999), 45–52.