A negotiation framework for linked combinatorial optimization problems

We tackle the challenge of applying automated negotiation to self-interested agents with local but linked combinatorial optimization problems. Using a distributed production scheduling problem, we propose two negotiation strategies for making concessions in a joint search space of agreements. In the first strategy, building on Lai and Sycara (Group Decis Negot 18(2):169–187, 2009), an agent concedes on local utility in order to achieve an agreement. In the second strategy, an agent concedes on the distance in an attribute space while maximizing its local utility. Lastly, we introduce a Pareto improvement phase to bring the final agreement closer to the Pareto frontier. Experimental results show that the new attribute-space negotiation strategy outperforms its utility-based counterpart on the quality of the agreements and the Pareto improvement phase is effective in approaching the Pareto frontier. This article presents the first study of applying automated negotiation to self-interested agents each with a local, but linked, combinatorial optimization problem.     

A win–win method for multi‐party negotiation support

In this paper, we introduce an interactive multi‐party negotiation support method for decision problems that involve multiple, conflicting linear criteria and linear constraints. Most previous methods for this type of problem have relied on decision alternatives located on the Pareto frontier; in other words, during the negotiation process the parties are presented with new Pareto optimal solutions, requiring the parties to sacrifice the achievement of some criteria in order to secure improvements with respect to other criteria. Such a process may be vulnerable to stalemate situations where none of the parties is willing to move to a potentially better solution, e.g., because they perceive – rightly or wrongly ? that they have to give up more than their fair share. Our method relies on “win–win” scenarios in which each party will be presented with “better” solutions at each stage of the negotiations. Each party starts the negotiation process at some inferior initial solution, for instance the best starting point that can be achieved without negotiation with the other parties, such as BATNA (best alternative to a negotiated agreement). In subsequent iterations, the process gravitates closer to the Pareto frontier by suggesting an improved solution to each party, based on the preference information (e.g., aspiration levels) provided by all parties at the previous iteration. The preference information that each party needs to provide is limited to aspiration levels for the objectives, and a party's revealed preference information is not shared with the opposing parties. Therefore, our method may represent a more natural negotiation environment than previous methods that rely on tradeoffs and sacrifice, and provides a positive decision support framework in which each party may be more comfortable with, and more readily accept, the proposed compromise solution. The current paper focuses on the concept, the algorithmic development, and uses an example to illustrate the nature and capabilities of our method. In a subsequent paper, we will use experiments with real users to explore issues such as whether our proposed “win–win” method tends to result in better decisions or just better negotiations, or both; and how users will react in practice to using an inferior starting point in the negotiations.     

一种基于多目标优化的Agent多议题协商模型

Agent多议题协商研究是多Agent合作求解的核心内容之一,一般基于对策论的方法实现Pareto最优的协商结果。由于很多学者将其转化为单目标约束满足问题,因而只能满足一方的效用最大化要求。Nash指出在理想情况下Agent应追求自身效用最大和对手效用最大的多目标优化,以达到快速达成一致并能最优化自身效用的目的。针对该问题,本文给出一种用指数型功效系数法求解的一揽子交易多议题协商模型NMMOP,该模型能够实现双方Agent的效用最优,提高协商双方的总效用。实验结果验证了该模型的优化效率优于Fatima和Faratin等人的工作。     

A REGION‐BASED MULTI‐ISSUE NEGOTIATION PROTOCOL FOR NONMONOTONIC UTILITY SPACES

Nonmonotonic utility spaces are found in multi‐issue negotiations where the preferences on the issues yield multiple local optima. These negotiations are specially challenging because of the inherent complexity of the search space and the difficulty of learning the opponent’s preferences. Most current solutions successfully address moderately complex preference scenarios, while solutions intended to operate in highly complex spaces are constrained by very specific preference structures. To overcome these problems, we propose the Region‐Based Multi‐issue Negotiation Protocol (RBNP) for bilateral automated negotiation. RBNP is built upon a nonmediated recursive bargaining mechanism which efficiently modulates a region‐based joint exploration of the solution space. We empirically show that RBNP produces outcomes close to the Pareto frontier in reasonable negotiation times, and show that it provides a significantly better performance when compared to a generic Similarity‐Based Multi‐issue Negotiation Protocol (SBNP), which has been successfully used in many negotiation models. We have paid attention to the strategic issues, proposing and evaluating several concession mechanisms, and analyzing the equilibrium conditions. Results suggest that RBNP may be used as a basis to develop negotiation mechanisms in nonmonotonic utility spaces.     

Multi-Dimensional,MultiStep Negotiation

We present a multi-dimensional, multi-step negotiation mechanism for task allocation among cooperative agents based on distributed search. This mechanism uses marginal utility gain and marginal utility cost to structure this search process, so as to find a solution that maximizes the agents’ combined utility. These two utility values together with temporal constraints summarize the agents’ local information and reduce the communication load. This mechanism is anytime in character: by investing more time, the agents increase the likelihood of getting a better solution. We also introduce a multiple attribute utility function into negotiations. This allows agents to negotiate over the multiple attributes of the commitment, which produces more options, making it more likely for agents to find a solution that increases the global utility. A set of protocols are constructed and the experimental result shows a phase transition phenomenon as the complexity of negotiation situation changes. A measure of negotiation complexity is developed that can be used by an agent to choose an appropriate protocol, allowing the agents to explicitly balance the gain from the negotiation and the resource usage of the negotiation.This revised version was published online in August 2005 with a corrected cover date.     

基于GAI多属性依赖的协商模型

多属性之间的依赖关系增加协商Agent效用函数的复杂性,从而也增加多属性协商问题的复杂度.本文提出一种基于GAI多属性依赖的协商模型.该模型使用GAI分解将协商Agent的非线性效用函数表示为依赖属性子集的子效用之和.在协商过程中,协商双方采用不同的让步策略和提议策略来改变提议的内容.卖方Agent利用本文提出的GAI网合并算法将协商双方的GAI网合并,并利用生成的GAI树产生使社会福利评估值最大的提议.实验表明当买方Agent采用局部让步策略且卖方Agent采用全局让步策略时,协商双方能够在有限的协商步内达到接近Pareto最优的协商结局.     

Bargaining with incomplete information

This paper analyses the process and outcomes of competitive bilateral negotiation for a model based on negotiation decision functions. Each agent has time constraints in the form of a deadline and a discounting factor. The importance of information possessed by participants is highlighted by exploring all possible incomplete information scenarios – both symmetric and asymmetric. In particular, we examine a range of negotiation scenarios in which the amount of information that agents have about their opponent’s parameters is systematically varied. For each scenario, we determine the equilibrium solution and study its properties. The main results of our study are as follows. Firstly, in some scenarios agreement takes place at the earlier deadline, while in others it takes place near the beginning of negotiation. Secondly, in some scenarios the price surplus is split equally between the agents while in others the entire price surplus goes to a single agent. Thirdly, for each possible scenario, the equilibrium outcome possesses the properties of uniqueness and symmetry – although it is not always Pareto optimal. Finally, we also show the relative impacts of the opponent’s parameters on the bargaining outcome.     

STRATUM: A METHODOLOGY FOR DESIGNING HEURISTIC AGENT NEGOTIATION STRATEGIES

Automated negotiation is a powerful (and sometimes essential) means for allocating resources among self-interested autonomous software agents. A key problem in building negotiating agents is the design of the negotiation strategy, which is used by an agent to decide its negotiation behavior. In complex domains, there is no single, obvious optimal strategy. This has led to much work on designing heuristic strategies, where agent designers usually rely on intuition and experience. In this article, we introduce STRATUM, a methodology for designing strategies for negotiating agents. The methodology provides a disciplined approach to analyzing the negotiation environment and designing strategies in light of agent capabilities and acts as a bridge between theoretical studies of automated negotiation and the software engineering of negotiation applications. We illustrate the application of the methodology by characterizing some strategies for the Trading Agent Competition and for argumentation-based negotiation.     

A Reluctance-Based Cost Distribution Strategy for Multiagent Planning

In this paper we present CODMAPS, a COst Distribution Method for Agent Planning Systems. The strategy is based on individual distribution of cost and competitive behavior.Our model emulates how human agents work in expert groups. They all share a common objective, however, they also have individual interests and try to steer the planning process towards their own goals. Two opposing trends coexist within the set: global co-operation and individual utility maximization. External evaluation must guarantee the validity of the final plan at global level, but a negotiation and cost distribution strategy must ensure that cost is adequately shared throughout the agent set. We introduce the concept of reluctance as a regulation mechanism to facilitate it. A statistical model allows agents to adapt their attitude towards negotiation depending on their negotiation state vector , which encompasses all history of previous negotiations by the agent.Previous research into this problem had taken the rational approach. A group of agents choose the best alternative given the current possibilities. This not only forces the agents to exchange and understand other agents' proposals (which is computationally expensive), but also neglects the past negotiation history of each individual agent.Our approach facilitates distribution of cost across the agent set given the agents' past history and the importance of their constraints. The more taxed an agent becomes the more reluctant it will be to relax, thus pushing other agents less taxed to accept to compromise. It does not need explicit constraint information exchange, thus simplifying the negotiation process.     

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

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

An evolutionary compensatory negotiation model for distributed dynamic scheduling

Although a considerable amount of efforts has been devoted to developing optimum negotiation for dynamic scheduling, most of them are inappropriate for the non-cooperative, self-interested participants in a distributed project for practical purpose. In this paper, an agent-based approach with a mutual influencing, many-issue, one-to-many-party, compensatory negotiation model is proposed. In the model, the activity agents possess various negotiation tactics and strategies formed by respective self-interested owner's subjective preference, aim to find the contracts of schedule adjustment mutually acceptable to respective participant's acquaintance while encountering conflicts over rescheduling settlement. In order to find the fitting negotiation strategies that are optimally adapted for each activity agent, an evolutionary computation approach that encodes the parameters of tactics and strategies of an agent as genes in GAs is also addressed. In the final, a prototype with a case discussed in researches is evaluated to validate the feasibility and applicability of the model, and some characteristics and future works are also exhibited.     

STRATEGIC NEGOTIATION FOR SHARING A RESOURCE BETWEEN TWO AGENTS*

In this article, we propose a strategic negotiation model that enables self‐motivated rational agents to share resources. The strategic negotiation model takes the passage of time during the negotiation process itself into account. The model considers bilateral negotiations in situations characterized by complete information, in which one agent loses over time whereas the other gains over time. Using this negotiation mechanism, autonomous agents apply simple and stable negotiation strategies that result in efficient agreements without delay, even when there are dynamic changes in the environment. Simulation results show that our mechanism performs as well as a centralized scheduler and also has the property of balancing the resources' usage.     

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.     

An agent architecture for multi-attribute negotiation using incomplete preference information

A component-based generic agent architecture for multi-attribute (integrative) negotiation is introduced and its application is described in a prototype system for negotiation about cars, developed in cooperation with, among others, Dutch Telecom KPN. The approach can be characterized as cooperative one-to-one multi-criteria negotiation in which the privacy of both parties is protected as much as desired. We model a mechanism in which agents are able to use any amount of incomplete preference information revealed by the negotiation partner in order to improve the efficiency of the reached agreements. Moreover, we show that the outcome of such a negotiation can be further improved by incorporating a “guessing” heuristic, by which an agent uses the history of the opponent’s bids to predict his preferences. Experimental evaluation shows that the combination of these two strategies leads to agreement points close to or on the Pareto-efficient frontier. The main original contribution of this paper is that it shows that it is possible for parties in a cooperative negotiation to reveal only a limited amount of preference information to each other, but still obtain significant joint gains in the outcome.     

Automated agents for reward determination for human work in crowdsourcing applications

Crowdsourcing applications frequently employ many individual workers, each performing a small amount of work. In such settings, individually determining the reward for each assignment and worker may seem economically beneficial, but is inapplicable if manually performed. We thus consider the problem of designing automated agents for automatic reward determination and negotiation in such settings. We formally describe this problem and show that it is NP-hard. We therefore present two automated agents for the problem, based on two different models of human behavior. The first, the Reservation Price Based Agent (RPBA), is based on the concept of a RP, and the second, the No Bargaining Agent (NBA) which tries to avoid any negotiation. The performance of the agents is tested in extensive experiments with real human subjects, where both NBA and RPBA outperform strategies developed by human experts.     

Visualization-based multi-objective improvement of environmental decision-making using linearization of response surfaces

This study presents a new interactive procedure for supporting Decision Makers (DMs) in environmental planning problems involving large, process-based, dynamic models and many (more than two) conflicting objectives. Because of such features of the model, computationally-onerous simulations are the only feasible way of analysis, while the multi-objective nature of the problem entails the combined use of optimization techniques and appropriate tools for the visualization of the associated Pareto frontier. The procedure proposed is based on the iterative improvement of the current best compromise alternative based on interactions with the DM. At each iteration, the DM is informed about the Pareto frontier of a local multi-objective optimization problem, which is generated by linearizing the response surfaces that describe the objectives and constraints of the original planning problem. Interactive visualization of the multi-dimensional Pareto frontier is used to support the DM in choosing the new best compromise alternative. The procedure terminates when the DM is fully satisfied with the current best compromise alternative. The approach is demonstrated in Googong Reservoir (Australia), which is periodically affected by high concentrations of Manganese and Cyanobacteria. Results indicate that substantial improvements could be observed by simply changing the location of the two mixers installed in 2007 and adding another pair of mixers.     

Cover2

Electronic negotiation systems have been devised to create an electronic marketplace for bargaining, auctions, reverse auctions, and exchanges between multiple buyers and sellers. Most studies of negotiation systems concentrate on negotiation process modeling and data modeling - rather than on strategies and efficiency - for a multiple-criteria decision making (MCDM) problem in which many criteria are taken into account as attributes for decision making. This study proposes an active collaboration and negotiation framework (ACNF), which is a negotiation support system that uses active documents with embedded business logics or business rules that can adapt to different collaborative strategies in a business-to-business (B2B) environment. The risk preferences of negotiators are modeled and measured by utility functions that provide mathematical tools to compute the relative value of different courses of action. The system is demonstrated, and three experiments are conducted to validate its performance. The experiments show that the negotiation process is very efficient, and the results are both close to the efficient point - and the Pareto frontier - and are fair to both negotiating parties. The framework can be used to efficiently and effectively achieve a settlement in various multiple-criteria bargaining schemes in the electronic marketplace     

A cooperative exchanging mechanism among seller agents for group-based sales

Agent-mediated electronic markets have been a growing area in intelligent agent research and development in recent years. Agents can act autonomously and cooperatively in an electronic market on behalf of their users. In such an electronic market, if a seller agent does not have enough of a particular item, it misses the opportunity to sell the item. Buyers also miss the opportunity to purchase the item. Namely, the overall negotiation utility is decreased. Thus, we propose a new cooperation mechanism among seller agents based on exchanging their goods in our agent-mediated electronic market system, G-Commerce. In G-Commerce, seller agents and buyer agents negotiate with each other. In our model, seller agents cooperatively negotiate in order to sell goods in stock. Buyer agents cooperatively form coalitions in order to buy goods based on discount prices. Seller agents’ negotiations are completed by using an exchanging mechanism for selling goods. Our experiments show that this exchanging mechanism enables seller agents to sell goods in stock effectively. We also demonstrate how our exchanging mechanism satisfies Pareto optimality.     

Building a Multiple-Criteria Negotiation Support System

Electronic negotiation systems have been devised to create an electronic marketplace for bargaining, auctions, reverse auctions, and exchanges between multiple buyers and sellers. Most studies of negotiation systems concentrate on negotiation process modeling and data modeling?rather than on strategies and efficiency?for a multiple-criteria decision making (MCDM) problem in which many criteria are taken into account as attributes for decision making. This study proposes an active collaboration and negotiation framework (ACNF), which is a negotiation support system that uses active documents with embedded business logics or business rules that can adapt to different collaborative strategies in a business-to-business (B2B) environment. The risk preferences of negotiators are modeled and measured by utility functions that provide mathematical tools to compute the relative value of different courses of action. The system is demonstrated, and three experiments are conducted to validate its performance. The experiments show that the negotiation process is very efficient, and the results are both close to the efficient point?or the Pareto frontier?and are fair to both negotiating parties. The framework can be used to efficiently and effectively achieve a settlement in various multiple-criteria bargaining schemes in the electronic marketplace.