Using Similarity Criteria to Make Negotiation Trade-Offs

Automated negotiation is a key form of interaction in systems that are composed of multiple autonomous agents. The aim of such interactions is to reach agreements through an iterative process of making offers. The content of such proposals are, however, a function of the strategy of the agents. Here we present a strategy called the {\it{trade-off}} strategy where multiple negotiation decision variables are traded-off against one another (e.g., paying a higher price in order to obtain an earlier delivery date or waiting longer in order to obtain a higher quality service). Such a strategy is commonly known to increase the social welfare of agents. Yet, to date, most computational work in this area has ignored the issue of trade-offs, instead aiming to increase social welfare through mechanism design. The aim of this paper is to develop a heuristic computational model of the trade-off strategy and show that it can lead to an increased social welfare of the system. A novel linear algorithm is presented that enables software agents to make trade-offs for multi-dimensional goods for the problem of distributed resource allocation. Our algorithm is motivated by a number of real-world negotiation applications that we have developed and can operate in the presence of varying degrees of uncertainty. Moreover, we show that on average the total time used by the algorithm is linearly proportional to the number of negotiation issues under consideration. This formal analysis is complemented by an empirical evaluation that highlights the operational effectiveness of the algorithm in a range of negotiation scenarios. The algorithm itself operates by using the notion of fuzzy similarity to approximate the preference structure of the other negotiator and then uses a hill-climbing technique to explore the space of possible trade-offs for the one that is most likely to be acceptable.[.ps][.pdf]

Socially Intelligent Agents Abstract: Multi-Agent Contract Negotiation

Two computational decision models are presented for the problem of de-centralized contracting of multi-dimensional services and goods between autonomous agents. The assumption of the models is that agents are bounded in both information and computation. Heuristic and approximate solution techniques from Artificial Intelligence are used for the design of decision mechanism that approach mutual selection of efficient contracts.[.ps][.pdf]

ATAL-01 Abstract: Simple Negotiating Agents in Complex Games: Emergent Equilibria and Dominance of Strategies

We present a simple model of distributed multi-agent multi-issued contract negotiation for open systems where interactions are competitive and information is private and not shared. We then investigate via simulations two different approximate optimization strategies and quantify the contribution and costs of each towards the quality of the solutions reached. To evaluate the role of knowledge the obtained results are compared to more cooperative strategies where agents share more information. Interesting social dilemmas emerge that suggest the design of incentive mechanisms.[.ps][.pdf]

IJCAI-01 Abstract: Automated Contract Negotiation and Execution as a System of Constraints

A classification of constraints is proposed that represents not only the individual and negotiated decisions of multiple agents as constraints, but also the exceptions that can occur at execution time. A design of an exception mechanism is then proposed based on task-environment constraints. This mechanism is composed of an informative and a normative component. The informative component functions to update the beliefs of agents about possible exceptions during the negotiation or execution stages of a joint activity. The normative component, on the other hand, places requirements on the agent to reason about such exceptions. The interaction of such an informative mechanism on a bargaining mechanism is elaborated in this paper. A simple additive model of future events is assumed to reasonably model this information. Different agent bargaining strategies, characterized as different attitudes towards the original constraints of the local problem given this belief, are then evaluated for a concession solver in an alternating sequential protocol. [.ps][.pdf]

PhD Thesis Abstract: Automated Service Negotiation between Autonomous Computational Agents

Multi-agent systems are a new computational approach for solving real world, dynamic and open system problems. Problems are conceptualized as a collection of decentralised autonomous agents that collaborate to reach the overall solution. Because of the agents autonomy, their limited rationality, and the distributed nature of most real world problems, the key issue in multi-agent system research is how to model interactions between agents. Negotiation models have emerged as suitable candidates to solve this interaction problem due to their decentralised nature, emphasis on mutual selection of an action, and the prevalence of negotiation in real social systems. The central problem addressed in this thesis is the design and engineering of a negotiation model for autonomous agents for sharing tasks and/or resources. To solve this problem a negotiation protocol and a set of deliberation mechanisms are presented which together coordinate the actions of a multiple agent system. In more detail, the negotiation protocol constrains the action selection problem solving of the agents through the use of normative rules of interaction. These rules temporally order, according to the agents' roles, communication utterances by specifying both who can say what, as well as when. Specifically, the presented protocol is a repeated, sequential model where offers are iteratively exchanged. Under this protocol, agents are assumed to be fully committed to their utterances and utterances are private between the two agents. The protocol is distributed, symmetric, supports bi and/or multi-agent negotiation as well as distributive and integrative negotiation. In addition to coordinating the agent interactions through normative rules, a set of mechanisms are presented that coordinate the deliberation process of the agents during the ongoing negotiation. Whereas the protocol normatively describes the orderings of actions, the mechanisms describe the possible set of agent strategies in using the protocol. These strategies are captured by a negotiation architecture that is composed of responsive and deliberative decision mechanisms. Decision making with the former mechanism is based on a linear combination of simple functions called tactics, which manipulate the utility of deals. The latter mechanisms are subdivided into trade-off and issue manipulation mechanisms. The trade-off mechanism generates offers that manipulate the value, rather than the overall utility, of the offer. The issue manipulation mechanism aims to increase the likelihood of an agreement by adding and removing issues into the negotiation set. When taken together, these mechanisms represent a continuum of possible decision making capabilities: ranging from behaviours that exhibit greater awareness of environmental resources and less to solution quality, to behaviours that attempt to acquire a given solution quality independently of the resource consumption. The protocol and mechanisms are empirically evaluated and have been applied to real world task distribution problems in the domains of business process management and telecommunication management. The main contribution and novelty of this research are: i) a domain independent computational model of negotiation that agents can use to support a wide variety of decision making strategies, ii) an empirical evaluation of the negotiation model for a given agent architecture in a number of different negotiation environments, and iii) the application of the developed model to a number of target domains. An increased strategy set is needed because the developed protocol is less restrictive and less constrained than the traditional ones, thus supporting development of strategic interaction models that belong more to open systems. Furthermore, because of the combination of the large number of environmental possibilities and the size of the set of possible strategies, the model has been empirically investigated to evaluate the success of strategies in different environments. These experiments have facilitated the development of general guidelines that can be used by designers interested in developing strategic negotiating agents. The developed model is grounded from the requirement considerations from both the business process management and telecommunication application domains. It has also been successfully applied to five other real world scenarios.

ICMAS-00 Abstract: Using Similarity Criteria to Make Negotiation Trade-Offs

This paper addresses the issues involved in software agents making trade-offs during automated negotiations in which they have information uncertainty and resource limitations. In particular, the importance of being able to make trade-offs in real-world applications is highlighted and a novel algorithm for performing trade-offs for multi-dimensional goods is developed. The algorithm uses the notion of fuzzy similarity in order to find negotiation solutions that are beneficial to both parties. Empirical results indicate the benefits and effectiveness of the trade-off algorithm in a range of negotiation situations.

PAAM-00 Abstract: A Service-Oreinted Negotiation Model between Autonomous Agents

This paper describes the design and implementation of negotiating agents for the task of provisioning virtual private networks. The agents and their interactions comply with the FIPA specification and they are implemented using the FIPA-OS agent framework. Particular attention is focused on the design and implementation of the negotiation algorithms.