Negotiation and Argumentation in Multi-Agent Systems

The autonomous agents and multi-agent systems domain was very active and fruitful along the last decade, mainly due to the community research efforts, with the organization of more than 50 workshops and a yearly major international conference (AAMAS). Moreover, the domain has reached the 3rd. place in IJCAI 2009 and the 2nd. place in ECAI 2010 in the number of accepted full papers, thus revealing its high relevance within the mainstream current research in the major field of Artificial Intelligence. In this paper, we try to cover its five key elements (agents, environments, interactions, organizations and users), after presenting a brief sketch of its historical milestones. We conclude by pointing out the future aims of research and the right place of negotiation and argumentation within the context of the domain.

Bargaining is one of the most common negotiation situations in which agents must reach an agreement regarding how to distribute objects or a monetary amount. On the one side, each agent prefers to reach an agreement, rather than abstaining from doing so. On the other side, each agent prefers that agreement which most favors her interests. This problem has been widely studied in the game theory literature, under the assumption that agents are intelligent (i.e., able to collect all the information over the opponents) and rational (i.e., able to maximize their gain). The most satisfactory models represent a bargaining situation as a non–cooperative (strategic) game, where a solution is a strategy profile, specifying a strategy per agent, that is somehow in equilibrium. This chapter surveys the game theoretic strategic models for bargaining and the corresponding solving algorithms. Although the bargaining problem has been studied in the literature for almost 30 years, no algorithm able to solve a general bargaining problem with uncertainty is known. The critical issues behind the game theoretic approaches and some possible new research directions are also discussed.

Negotiation is a process of opportunistic interaction by which two or more parties seek a solution for a divergence of interests through jointly decided action. Traditional negotiation, conducted face-to-face and via telephone or mail, is a critically important activity in all realms of human interaction and often proceeds through several distinct phases or stages—notably a beginning or initiation phase, a middle or problem-solving phase, and an ending or resolution phase. Automated negotiation, conducted autonomously by software agents representing individuals or organizations, is an active area of research in artificial intelligence and computer science generally. Increasingly, automated negotiation systems help in achieving efficient agreements—examples, to mention a few, include the business trend toward agent-based supply chain management, the pivotal role that electronic commerce is increasingly assuming in many organizations, and the industrial trend toward virtual enterprises. This chapter discusses and analyses some of the key negotiation techniques for software agents, placing emphasis on both the early stages of negotiation and the process of moving toward agreement.

Argumentation-based negotiation (ABN) is a prevailing approach for automated negotiation. It is based on the exchange of arguments that allow an agent to acquire additional information about the other agents and the particular circumstances of the negotiation, and can be used for attacking or justifying offers. This is an important element in resolving conflicts that very often are due to the assumptions agents have made when making decisions and which may be found to be false in the course of the negotiation. Argumentation-based negotiation can be characterized in terms of three main topics, namely a) the reasoning mechanisms the agents use for negotiating and which are based on argumentation, b) the protocols the agents use for conveying arguments and offers and, c) the strategies that determine their choices at each step of the negotiation. This chapter presents argumentationbased negotiation by discussing representative works dealing with these three topics.

In this chapter, we provide a multi-disciplinary perspective of the theory and decision support systems of argumentation-based negotiation. Based on an extensive discussion of limitations of proposalbased argumentation, we emphasize the central role of persuasive arguments in a negotiation. Then we draw insights from three theoretical perspectives of argumentation-based negotiation research: argumentation-based automated negotiation, argumentation games, and cheap-talk games. Our reflection on the extant literature leads to a conceptual framework for decision support systems, which consists of key functionality and system components. We also discuss open issues and challenges in the development of the theory and systems of argumentation-based negotiation.

To formally understand the complex behaviors of negotiating agents so as to design appropriate mechanisms to approximate optimal performance, we have constructed a unified framework to model and analyze the task allocation problem in agent societies with different objectives. This OAR framework includes three aspects: agent’s objective (O), its negotiation attitude (A) and the reward splitting (R) among agents who cooperate to accomplish tasks. An agent’s objective can span the spectrum from totally self-interested to completely cooperative, and there can be a mixture of agents with varying objectives in one agent society. This work focuses on understanding how these different aspects interact in order to achieve individual agent’s objective and to produce effective system performance as well. Using the OAR framework, we develop a closed form statistical analysis to mathematically analyze the interaction between attitude parameters and reward splitting and their relationship with different objective functions for a simple scenario. Though the scenario is simple, it does allow us to show that being able to adjust the attitude parameter and the reward splitting is important to an agent, whether self-interested or cooperative, in order to optimize its objective function. We also present a graph model and optimality graphs, which are used for visualizing the relationships among different parameters. Additionally, we discuss how agents’ expected rewards are affected by changing the local attitude parameters, varying reward splitting, and the method of calculating the relational reward. This work shows that we can create a formal model to analyze interactions among agents ranging from self-interested to fully cooperative.

Negotiation is a central process in an agent society where autonomous agents have to cooperate in order to resolve conflicting interests and yet compete to divide limited resources. A direct dialogical exchange of information between agents usually leads to competitive forms of negotiation where the most powerful agents win. Alternatively, an intelligent mediated interaction may better achieve the goal of reaching a common agreement and supporting cooperative negotiation. In both cases argumentation is the reference framework to rationally manage conflicting knowledge or objectives, a framework which provides the fundamental abstraction “argument” to exchange pieces of information. In this paper we present a novel conceptual framework for negotiation dialogues using argumentation between autonomous software agents which enables their dialogues to be automated. The framework, called SANA (Supporting Artifacts for Negotiation with Argumentation), incorporates intelligent components able to assist the agent participants to reach agreement by inferring mutuallyacceptable proposals. The framework also permits agents to engage in negotiation dialogues with each other, generating and exchanging proposed deals and arguments for and against these proposals. Acceptability of proposals is then assessed in terms of an agreed argumentation framework semantics. We present the architecture of our framework, along with the syntax, and outline denotational semantics of an associated agent interaction protocol, called SANAP.

Much has been written on the use of rhetorical argumentation to alter the beliefs of a partner agent within a particular negotiation. The problem addressed in this chapter is the measurement of the long-term value of rhetorical argumentation in repeated interactions between a pair of agents, and of the management of such argumentation to achieve strategic aims concerning the strength of the agents’ relationships. RANA is a relationshipaware negotiation agent in the context of information-based agents [1] that have embedded tools from information theory enabling them to measure and manage strategic information.

In this chapter we elaborate on the specification and exploitation of a software agent-based Electronic Institution, embedding both a Normative Environment and a Computational Trust service which, when used in tandem, lead to an enhanced process of selection of potential business partners and enable automatic contract negotiation. We introduce a formalization of a Normative Environment, which accommodates the establishment of e-contracts and provides a contract monitoring facility. Contracts are established and enacted by contractual partners previously selected through an automatic negotiation process. While monitoring contracts at run-time, the Normative Environment makes use of a reporting mechanism to inform relevant contract enactment events to interested parties. In our work, we benefit from this reporting function by exploiting it as an input to a computational trust mechanism. We also present the built-in Computational Trust service, a key element of the Electronic Institution. This service includes two main components: the Contractual Evidences Manager, which generates contractual evidences from contract enactment events; and the Trust Aggregation Engine, a situation-aware trust aggregator that takes into account properties of the dynamics of trust and the contractual context under assessment. We then discuss and propose the potential exploitation of trustworthiness estimations in B2B negotiation processes, including the stages of preselection of partners and contract drafting. Using our computational trust approach, we have implemented a trust-based preselection mechanism included in an agent-based automatic negotiation process. We performed an empirical evaluation of our proposal, by running a set of experiments in an experimental setting enriched with realistic negotiation elements. The results obtained allow us to point to specific conditions under which the preselection of partners based on trust is beneficial.

In this chapter we present an application and a framework aiming at the automation of bilateral negotiation on multiple issue in e-markets. We address several challenges of a typical negotiation in an online marketplace, such as (i) how to elicit preferences from users; (ii) how to formally represent preferences that at the same time allow human users to express both qualitative and quantitative preferences; (iii) how to compute agreements which are mutual beneficial for both buyer and seller, i.e., outcome enjoying economics properties as Pareto-efficiency. The issue of preference elicitation is addressed with the help of an easy-to-use graphical interface hiding all the technicalities of the underlying framework. Preferences are then mapped to a logic language, that allows one to express preferences on both numerical and non-numerical features. We build a utility function on top of this logic language in order to permit the representation of relative importance among preferences, to evaluate the possible agreements and finally choose the one(s) enjoying the Pareto-efficiency property.

Negotiation is a fundamental tool for reaching understandings that allow each involved party to gain an advantage for themselves by the end of the process. In recent years, with the increasing of competitiveness in most sectors, negotiation procedures become present in practically all of them. One particular environment in which the competitiveness has been increasing exponentially is the electricity markets sector. This work is directed to the study of electricity markets’ participating entities interaction, namely in what concerns the formation, management and operation of aggregating entities—Virtual Power Players (VPPs). VPPs are responsible for managing coalitions of market players with small market negotiating influence, which take strategic advantage in entering such aggregations, to increase their negotiating power. This chapter presents a negotiation method to create and manage players’ coalitions. This approach is tested using MASCEM, using this simulator’s capability of providing an adequate framework to model and simulate VPPs. VPPs represent agents’ coalitions, capable of negotiating in the electricity market, and internally, with their members, combining and managing their individual characteristics and specific goals, with the objectives and strategy of the VPP itself.

Research in Multi-Agent Planning (MAP) has traditionally been concerned with the design of coordination mechanisms such that the resulting joint plan meets the global goals of a problem. In contrast to most MAP techniques, in this paper we present a novel argumentation-based approach for multiple agents that plan cooperatively while having different capabilities, knowledge about the world and even contradictory information. Our aim is to enhance the role of argumentation as a means to attain a collective behaviour when devising a joint plan. Since agents’ decisions are influenced by the other agents’ plans, the use of mechanisms becomes relevant for persuading an agent to adopt a certain course of action, or negotiating on the use of scarce resources. Through a dialectical process, agents will discuss the different choices put forward by the others thus reaching a commonly agreed solution plan.

Pervasive services applications often employ networked sensors, devices and appliances to build intelligent and adaptable environments, such as Smart Homes. One of the most significant emergent problems in the deployment of such applications is conflicting sensors information. The system is required to decipher the true context of ambiguous or conflicting data in order to efficiently assimilate context-awareness and subsequently ensure accurate adaptability to suit the application space. To-date, there has been speculation as to the optimal method to disambiguate conflicting data; citing the use of ”argumentation” based reasoning to resolve conflict situations as a theoretical solution. This chapter presents the first known implementation of argumentation based conflict resolution for pervasive services computing. It proves that the concept is feasible, accurate and efficient, through simulated deployment on a range of conflict scenarios. The prototype is based on SOA4D built upon the OSGi platform and implements DPWS; and is capable of resolving conflicting data gathered from up to 10 sensors in approximately 2.5 seconds. In effect, this work realises the potential of argumentation theory to solve real-world problems in services computing.