A Market–Driven Model for Designing Negotiation Agents

Although there are many extant agent–based systems for negotiation in e–commerce, the negotiation strategies of agents in these systems are mostly static. This article presents a model for designing negotiation agents that make adjustable rates of concession by reacting to changing market situations. To determine the amount of concession for each trading cycle, these market–driven agents are guided by four mathematical functions of eagerness, trading time, trading opportunity , and competition . Trading opportunity is determined by considering: (i) number of trading partners, (ii) spreads —differences in utilities between an agent and its trading partners, and (iii) probability of completing a deal. Competition is determined by the probability that an agent is not considered the most preferred trader by other negotiating parties. Motivated by factors such as corporate policies and resource needs, eagerness represents an agent's desire to complete a deal. Agents with different time sensitivity to deadlines employ different trading strategies by making different rates of concession at different stages of negotiation. In this article, three classes of strategies with respect to remaining trading time are discussed. Theoretical analyses show that market–driven agents are designed to make prudent and appropriate amounts of concession for a given market situation.     

KEMNAD: A KNOWLEDGE ENGINEERING METHODOLOGY FOR NEGOTIATING AGENT DEVELOPMENT

Automated negotiation is widely applied in various domains. However, the development of such systems is a complex knowledge and software engineering task. So, a methodology there will be helpful. Unfortunately, none of existing methodologies can offer sufficient, detailed support for such system development. To remove this limitation, this paper develops a new methodology made up of (1) a generic framework (architectural pattern) for the main task, and (2) a library of modular and reusable design pattern (templates) of subtasks. Thus, it is much easier to build a negotiating agent by assembling these standardized components rather than reinventing the wheel each time. Moreover, because these patterns are identified from a wide variety of existing negotiating agents (especially high impact ones), they can also improve the quality of the final systems developed. In addition, our methodology reveals what types of domain knowledge need to be input into the negotiating agents. This in turn provides a basis for developing techniques to acquire the domain knowledge from human users. This is important because negotiation agents act faithfully on the behalf of their human users and thus the relevant domain knowledge must be acquired from the human users. Finally, our methodology is validated with one high impact system.     

A two-step approach to building bilateral consensus between agents based on relationship learning theory

Researchers are increasingly focusing on the agent based approach to transaction support in ubiquitous commerce. These agents work autonomously to maximize utility on the user’s behalf. In the case of a cooperative game, rather than a win–lose zero-sum game, agents may negotiate with each other or have a negotiating agent provide a suggestion that can be reasonably accepted by the dyad to build a consensus. In this paper we propose a novel methodology that increases agent performance in terms of costs associated with building consensus and successful negotiation rates. To do so, we develop a two-step approach: joint learning and negotiation to consensus building. We also conduct an experimental study to show the feasibility of the methodology.     

A protocol for multi-agent negotiation in a group-choice decision making process

Negotiation is one of the most important features of agent interactions found in multi-agent systems, because it provides the basis for managing the expectations of the individual negotiating agents, and it enables selecting solutions that satisfy all the agents as much as possible. In order for negotiation to take place between two or more agents there is need for a negotiation protocol that defines the rules of the game; consequently, a variety of agent negotiation protocols have been proposed in literature. However, most of them are inappropriate for Group-Choice Decision Making (GCDM) because they do not explicitly exploit tradeoff to achieve social optimality, and their main focus is solving two-agent negotiation problems such as buyer–seller negotiation. In this paper we present an agent negotiation protocol that facilitates the solving of GCDM problems. The protocol is based on a hybrid of analytic and artificial intelligence techniques. The analytic component of the protocol utilizes a Game Theory model of an n-person general-sum game with complete information to determine the agreement options, while the knowledge-based (artificial intelligence) component of the protocol is similar to the strategic negotiation protocol. Moreover, this paper presents a tradeoff algorithm based on Qualitative Reasoning, which the agents employ to determine the ‘amount’ of tradeoff associated with various agreement options. Finally, the paper presents simulation results that illustrate the operational effectiveness of our agent negotiation protocol.     

Addressing stability issues in mediated complex contract negotiations for constraint-based, non-monotonic utility spaces

Negotiating contracts with multiple interdependent issues may yield non- monotonic, highly uncorrelated preference spaces for the participating agents. These scenarios are specially challenging because the complexity of the agents’ utility functions makes traditional negotiation mechanisms not applicable. There is a number of recent research lines addressing complex negotiations in uncorrelated utility spaces. However, most of them focus on overcoming the problems imposed by the complexity of the scenario, without analyzing the potential consequences of the strategic behavior of the negotiating agents in the models they propose. Analyzing the dynamics of the negotiation process when agents with different strategies interact is necessary to apply these models to real, competitive environments. Specially problematic are high price of anarchy situations, which imply that individual rationality drives the agents towards strategies which yield low individual and social welfares. In scenarios involving highly uncorrelated utility spaces, “low social welfare” usually means that the negotiations fail, and therefore high price of anarchy situations should be avoided in the negotiation mechanisms. In our previous work, we proposed an auction-based negotiation model designed for negotiations about complex contracts when highly uncorrelated, constraint-based utility spaces are involved. This paper performs a strategy analysis of this model, revealing that the approach raises stability concerns, leading to situations with a high (or even infinite) price of anarchy. In addition, a set of techniques to solve this problem are proposed, and an experimental evaluation is performed to validate the adequacy of the proposed approaches to improve the strategic stability of the negotiation process. Finally, incentive-compatibility of the model is studied.     

Continuous-Time Negotiation Mechanism for Software Agents

While there are several existing mechanisms and systems addressing the crucial and difficult issues of automated one-to-many negotiation, this paper develops a flexible one-to-many negotiation mechanism for software agents. Unlike the existing general one-to-many negotiation mechanism, in which an agent should wait until it has received proposals from all its trading partners before generating counterproposals, in the flexible one-to-many negotiation mechanism, an agent can make a proposal in a flexible way during negotiation, i.e., negotiation is conducted in continuous time. To decide when to make a proposal, two strategies based on fixed waiting time and a fixed waiting ratio is proposed. Results from a series of experiments suggest that, guided by the two strategies for deciding when to make a proposal, the flexible negotiation mechanism achieved more favorable trading outcomes as compared with the general one-to-many negotiation mechanism. To determine the amount of concession, negotiation agents are guided by four mathematical functions based on factors such as time, trading partners' strategies, negotiation situations of other threads, and competition. Experimental results show that agents guided by the four functions react to changing market situations by making prudent and appropriate rates of concession and achieve generally favorable negotiation outcomes     

Compromising Adjustment Strategy Based on TKI Conflict Mode for Multi‐Times Bilateral Closed Negotiations

Bilateral multi‐issue closed negotiation is an important class for real‐life negotiations. Usually, negotiation problems have constraints such as a complex and unknown opponent's utility in real time, or time discounting. In the class of negotiation with some constraints, the effective automated negotiation agents can adjust their behavior depending on the characteristics of their opponents and negotiation scenarios. Recently, the attention of this study has focused on the interleaving learning with negotiation strategies from the past negotiation sessions. By analyzing the past negotiation sessions, agents can estimate the opponent's utility function based on exchanging bids. In this article, we propose a negotiation strategy that estimates the opponent's strategies based on the past negotiation sessions. Our agent tries to compromise to the estimated maximum utility of the opponent by the end of the negotiation. In addition, our agent can adjust the speed of compromise by judging the opponent's Thomas–Kilmann conflict mode and search for the Pareto frontier using past negotiation sessions. In the experiments, we demonstrate that the proposed agent has better outcomes and greater search technique for the Pareto frontier than existing agents in the linear and nonlinear utility functions.     

基于时间约束的不完全信息的战略协商模型

在实证的一对一协商中，协商Agent不仅要面临自己的最后期限的压力，同时又要预测协商对手的最后期限和其类型，协商Agent的协商战略必须满足理性与均衡的要求。提出了通过形式化的方法建立轮流出价协商模型，给出了轮流出价协商战略均衡的条件定义，求出了基于时间限制的不完全信息环境下满足均衡组合的协商战略，建立了依据均衡战略的实用化协商算法，最后分析了该算法产生的实验数据，并在相同环境下与Zeus协商模型比较显示，依从本模型的均衡战略的协商Agent能根据对对手的不确定信息的信念动态地采取行动，以获得最大的期望收益。     

DynamiCS: An Actor-Based Framework for Negotiating Mobile Agents

In this article, a framework to integrate negotiation capabilities—particularly, components implementing a negotiation strategy—into mobile agents is described. This approach is conceptually based on the notion of an actor system which decomposes an application component into autonomously executing subcomponents cooperating with each other. Technically, the framework is based on a plug-in mechanism enabling a dynamic composition of negotiating agents. Additionally, this contribution describes how interaction-oriented rule mechanisms can be deployed to control the behavior of strategy actors.     

An experts approach to strategy selection in multiagent meeting scheduling

In the multiagent meeting scheduling problem, agents negotiate with each other on behalf of their users to schedule meetings. While a number of negotiation approaches have been proposed for scheduling meetings, it is not well understood how agents can negotiate strategically in order to maximize their users’ utility. To negotiate strategically, agents need to learn to pick good strategies for negotiating with other agents. In this paper, we show how agents can learn online to negotiate strategically in order to better satisfy their users’ preferences. We outline the applicability of experts algorithms to the problem of learning to select negotiation strategies. In particular, we show how two different experts approaches, plays [3] and Exploration–Exploitation Experts (EEE) [10] can be adapted to the task. We show experimentally the effectiveness of our approach for learning to negotiate strategically.     

Reward and Penalty Functions in Automated Negotiation

Automated negotiation is very important for organizing decentralized systems such as e‐business, p2p systems, cloud computing, and so on. During the course of a negotiation, reward and penalty can be used to increase the chance of reaching agreements between negotiating agents, but have not been applied into automated negotiation systems well, especially integrating both in a single negotiation system. Thus, in this work we make an effort to reveal how the reward increases the acceptability of an offer and how the penalty decreases the deniability of an offer. More specifically, our study shows that the degree, to which a reward and a penalty influence the outcome, depends on the greedy degree for the reward and the creditable degree on the penalty. Therefore, if we know an offeree's utilities of accepting and denying an offer, the greedy degree for reward and the creditable degree on penalty, we can calculate how much reward and penalty the offerer agent needs to change the offeree's mind (i.e., from denying to accepting).     

A Negotiation Enabling Agent Based Infrastructure: Composition and Behavior

Software agent-based negotiation is a major method to automate the interactions in electronic marketplaces and Internet enabled communities. The traditional approach is to let the agents to interact directly. In this paper it has been investigated how a mediator agent can improve the chances to reach the agreement via bargaining. Although the ideal mathematical model was proposed in the seventies, this was never implemented as a working mechanism, due to the fact that the mediator needed information that was difficult to gather and the usual environment was not repetitive enough to consolidate this information for a fair mediation. The agent-based infrastructure proposed collects continuously data about the negotiating parties and the mediator agents use this data to reduce the exaggeration of the parties. The paper includes a mediation example and the major conclusion is that negotiation is improved by a mediator which has historical data about the negotiating parties.     

Strategic agents for multi-resource negotiation

In electronic commerce markets where selfish agents behave individually, agents often have to acquire multiple resources in order to accomplish a high level task with each resource acquisition requiring negotiations with multiple resource providers. Thus, it is crucial to efficiently coordinate these interrelated negotiations. This paper presents the design and implementation of agents that concurrently negotiate with other entities for acquiring multiple resources. Negotiation agents in this paper are designed to adjust (1) the number of tentative agreements for each resource and (2) the amount of concession they are willing to make in response to changing market conditions and negotiation situations. In our approach, agents utilize a time-dependent negotiation strategy in which the reserve price of each resource is dynamically determined by (1) the likelihood that negotiation will not be successfully completed (conflict probability), (2) the expected agreement price of the resource, and (3) the expected number of final agreements. The negotiation deadline of each resource is determined by its relative scarcity. Agents are permitted to decommit from agreements by paying a time-dependent penalty, and a buyer can make more than one tentative agreement for each resource. The maximum number of tentative agreements for each resource made by an agent is constrained by the market situation. Experimental results show that our negotiation strategy achieved significantly more utilities than simpler strategies.     

Cooperative-Competitive Healthcare Service Negotiation

Service negotiation is a complex activity, especially in complex domains such as healthcare. The provision of healthcare services typically involves the coordination of several professionals with different skills and locations. There is usually negotiation between healthcare service providers as different services have specific constraints, variables, and features (scheduling, waiting lists, availability of resources, etc.), which may conflict with each other. While automating the negotiation processes by using software can improve the effciency and quality of healthcare services, most of the existing negotiation automations are positional bargaining in nature, and are not suitable for complex scenarios in healthcare services. This paper proposes a cooperative-competitive negotiation model that enables negotiating parties to share their knowledge and work toward optimal solutions. In this model, patients and healthcare providers work together to develop a patient-centered treatment plan. We further automate the new negotiation model with software agents.     

一种用于软件过程建模的适应性Agent 协商

大多软件过程模型是预定义的.在变化的应用环境中,需要由相应人员进行适应性调整.提出一种用于软件过程建模的适应性多边协商模型—— AMNM-PA,其采用Agent 封装软件过程中所涉及的个体,包含组织、团队、个人等,通过Agent 间的协商动态、适应地建立针对给定软件项目的软件过程模型.AMNM-PA 基于非静态有限阶段Markov 决策过程,采用模型无关的Q 学习算法选取协商策略,因此能够支持动态、非预知环境下的适应性协商,从而满足软件过程建模对环境的适应性需求.AMNM-PA 已经实施于软件过程管理系统——SoftPM.     

Unanimously acceptable agreements for negotiation teams in unpredictable domains

A negotiation team is a set of agents with common and possibly also conflicting preferences that forms one of the parties of a negotiation. A negotiation team is involved in two decision making processes simultaneously, a negotiation with the opponents, and an intra-team process to decide on the moves to make in the negotiation. This article focuses on negotiation team decision making for circumstances that require unanimity of team decisions. Existing agent-based approaches only guarantee unanimity in teams negotiating in domains exclusively composed of predictable and compatible issues. This article presents a model for negotiation teams that guarantees unanimous team decisions in domains consisting of predictable and compatible, and alsounpredictable issues. Moreover, the article explores the influence of using opponent, and team member models in the proposing strategies that team members use. Experimental results show that the team benefits if team members employ Bayesian learning to model their teammates’ preferences.     

A context-aware approach to automated negotiation using reinforcement learning

Agents negotiate depending on individual perceptions of facts, events, trends and special circumstances that define the negotiation context. The negotiation context affects in different ways each agent’s preferences, bargaining strategies and resulting benefits, given the possible negotiation outcomes. Despite the relevance of the context, the existing literature on automated negotiation is scarce about how to account for it in learning and adapting negotiation strategies. In this paper, a novel contextual representation of the negotiation setting is proposed, where an agent resorts to private and public data to negotiate using an individual perception of its necessity and risk. A context-aware negotiation agent that learns through Self-Play and Reinforcement Learning (RL) how to use key contextual information to gain a competitive edge over its opponents is discussed in two levels of temporal abstraction. Learning to negotiate in an Eco-Industrial Park (EIP) is presented as a case study. In the Peer-to-Peer (P2P) market of an EIP, two instances of context-aware agents, in the roles of a buyer and a seller, are set to bilaterally negotiate exchanges of electrical energy surpluses over a discrete timeline to demonstrate that they can profit from learning to choose a negotiation strategy while selfishly accounting for contextual information under different circumstances in a data-driven way. Furthermore, several negotiation episodes are conducted in the proposed EIP between a context-aware agent and other types of agents proposed in the existing literature. Results obtained highlight that context-aware agents do not only reap selfishly higher benefits, but also promote social welfare as they resort to contextual information while learning to negotiate.     

Methodological design and comparative evaluation of a MAS providing AmI

Researches on Ambient Intelligent and Ubiquitous Computing using wireless technologies have increased in the last years. In this work, we review several scenarios to define a multi-agent architecture that support the information needs of these new technologies, for heterogeneous domain. Our contribution consists of designing in a methodological way a Context Aware System (involving location services) using agents that can be used in very different domains. We describe all the steps followed in the design of the agent system. We apply a hybridizing methodology between GAIA and AUML. Additionally we propose a way to compare different agent architectures for Context Aware System using agent interactions. So, in this paper, we describe the assignment of weight values to agents interaction in two different MAS architectures for Context Aware problems solving different scenarios inspired in FIPA standard negotiation protocols.     

Equilibria, prudent compromises, and the "waiting" game.

While evaluation of many e-negotiation agents are carried out through empirical studies, this work supplements and complements existing literature by analyzing the problem of designing market-driven agents (MDAs) in terms of equilibrium points and stable strategies. MDAs are negotiation agents designed to make prudent compromises taking into account factors such as time preference, outside option, and rivalry. This work shows that 1) in a given market situation, an MDA negotiates optimally because it makes minimally sufficient concession, and 2) by modeling negotiation of MDAs as a game gamma of incomplete information, it is shown that the strategies adopted by MDAs are stable. In a bilateral negotiation, it is proven that the strategy pair of two MDAs forms a sequential equilibrium for gamma. In a multilateral negotiation, it is shown that the strategy profile of MDAs forms a market equilibrium for gamma.     

Acquiring user tradeoff strategies and preferences for negotiating agents: A default-then-adjust method

A wide range of algorithms have been developed for various types of negotiating agents. In developing such algorithms the main focus has been on their efficiency and their effectiveness. However, this is only a part of the picture. Typically, agents negotiate on behalf of their owners and for this to be effective the agents must be able to adequately represent their owners’ strategies and preferences for negotiation. However, the process by which such knowledge is acquired is typically left unspecified. To address this problem, we undertook a study of how user information about negotiation tradeoff strategies and preferences can be captured. Specifically, we devised a novel default-then-adjust acquisition technique. In this, the system firstly does a structured interview with the user to suggest the attributes that the tradeoff could be made between, then it asks the user to adjust the suggested default tradeoff strategy by improving some attribute to see how much worse the attribute being traded off can be made while still being acceptable, and, finally, it asks the user to adjust the default preference on the tradeoff alternatives. This method is consistent with the principles of standard negotiation theory and to demonstrate its effectiveness we implemented a prototype system and performed an empirical evaluation in an accommodation renting scenario. The result of this evaluation indicates the proposed technique is helpful and efficient in accurately acquiring the users’ tradeoff strategies and preferences.