基于遗传算法的多边多议题自动协商模型

协商是MAS实现协同、协作和冲突消解的关键环节。在虚拟组织建立的背景之下,讨论了现有的多agent协商技术,提出了一个基于遗传算法的多边多议题自动协商模型,并且给出了相应的协议和算法。该模型能够迅速求出协商解,且agent能保持较高的效用,因此具有一定的通用性,适宜在动态的、时间约束强的开放网络环境下工作。     

An augmented EDA with dynamic diversity control and local neighborhood search for coevolution of optimal negotiation strategies

In this paper, we present an estimation of distribution algorithm (EDA) augmented with enhanced dynamic diversity controlling and local improvement methods to solve competitive coevolution problems for agent-based automated negotiations. Since optimal negotiation strategies ensure that interacting agents negotiate optimally, finding such strategies—particularly, for the agents having incomplete information about their opponents—is an important and challenging issue to support agent-based automated negotiation systems. To address this issue, we consider the problem of finding optimal negotiation strategies for a bilateral negotiation between self-interested agents with incomplete information through an EDA-based coevolution mechanism. Due to the competitive nature of the agents, EDAs should be able to deal with competitive coevolution based on two asymmetric populations each consisting of self-interested agents. However, finding optimal negotiation solutions via coevolutionary learning using conventional EDAs is difficult because the EDAs suffer from premature convergence and their search capability deteriorates during coevolution. To solve these problems, even though we have previously devised the dynamic diversity controlling EDA (D²C-EDA), which is mainly characterized by a diversification and refinement (DR) procedure, D²C-EDA suffers from the population reinitialization problem that leads to a computational overhead. To reduce the computational overhead and to achieve further improvements in terms of solution accuracy, we have devised an improved D²C-EDA (ID²C-EDA) by adopting an enhanced DR procedure and a local neighborhood search (LNS) method. Favorable empirical results support the effectiveness of the proposed ID²C-EDA compared to conventional and the other proposed EDAs. Furthermore, ID²C-EDA finds solutions very close to the optimum.     

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.     

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 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.     

Negotiating with bounded rational agents in environments with incomplete information using an automated agent

Many tasks in day-to-day life involve interactions among several people. Many of these interactions involve negotiating over a desired outcome. Negotiation in and of itself is not an easy task, and it becomes more complex under conditions of incomplete information. For example, the parties do not know in advance the exact tradeoff of their counterparts between different outcomes. Furthermore information regarding the preferences of counterparts might only be elicited during the negotiation process itself. In this paper we propose a model for an automated negotiation agent capable of negotiating with bounded rational agents under conditions of incomplete information. We test this agent against people in two distinct domains, in order to verify that its model is generic, and thus can be adapted to any domain as long as the negotiators' preferences can be expressed in additive utilities. Our results indicate that the automated agent reaches more agreements and plays more effectively than its human counterparts. Moreover, in most of the cases, the automated agent achieves significantly better agreements, in terms of individual utility, than the human counterparts playing the same role.     

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     

基于TD3算法的自动协商策略

协商是人们就某些议题进行交流寻求一致协议的过程.而自动协商旨在通过协商智能体的使用降低协商成本、提高协商效率并且优化协商结果.近年来深度强化学习技术开始被运用于自动协商领域并取得了良好的效果,然而依然存在智能体训练时间较长、特定协商领域依赖、协商信息利用不充分等问题.为此,本文提出了一种基于TD3深度强化学习算法的协商策略,通过预训练降低训练过程的探索成本,通过优化状态和动作定义提高协商策略的鲁棒性从而适应不同的协商场景,通过多头语义神经网络和对手偏好预测模块充分利用协商的交互信息.实验结果表明,该策略在不同协商环境下都可以很好地完成协商任务.     

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.     

Automatic negotiation: playing the domain instead of the opponent

An automated negotiator is an intelligent agent whose task is to reach the best possible agreement. We explore a novel approach to developing a negotiation strategy, a ‘domain-based approach’. Specifically, we use two domain parameters, reservation value and discount factor, to cluster the domain into different regions, in each of which we employ a heuristic strategy based on the notions of temporal flexibility and bargaining strength. Following the presentation of our cognitive and formal models, we show in an extensive experimental study that an agent based on that approach wins against the top agents of the automated negotiation competition of 2012 and 2013, and attained the second place in 2014.     

Social decisions and fairness change when people’s interests are represented by autonomous agents

There has been growing interest on agents that represent people’s interests or act on their behalf such as automated negotiators, self-driving cars, or drones. Even though people will interact often with others via these agent representatives, little is known about whether people’s behavior changes when acting through these agents, when compared to direct interaction with others. Here we show that people’s decisions will change in important ways because of these agents; specifically, we showed that interacting via agents is likely to lead people to behave more fairly, when compared to direct interaction with others. We argue this occurs because programming an agent leads people to adopt a broader perspective, consider the other side’s position, and rely on social norms—such as fairness—to guide their decision making. To support this argument, we present four experiments: in Experiment 1 we show that people made fairer offers in the ultimatum and impunity games when interacting via agent representatives, when compared to direct interaction; in Experiment 2, participants were less likely to accept unfair offers in these games when agent representatives were involved; in Experiment 3, we show that the act of thinking about the decisions ahead of time—i.e., under the so-called “strategy method”—can also lead to increased fairness, even when no agents are involved; and, finally, in Experiment 4 we show that participants were less likely to reach an agreement with unfair counterparts in a negotiation setting. We discuss theoretical implications for our understanding of the nature of people’s social behavior with agent representatives, as well as practical implications for the design of agents that have the potential to increase fairness in society.     

Alternating-offers bargaining in one-to-many and many-to-many settings

Automating negotiations in markets where multiple buyers and sellers operate is a scientific challenge of extraordinary importance. One-to-one negotiations are classically studied as bilateral bargaining problems, while one-to-many and many-to-many negotiations are studied as auctioning problems. This paper aims at bridging together these two approaches, analyzing agents’ strategic behavior in one-to-many and many-to-many negotiations when agents follow the alternating-offers bargaining protocol (Rubinstein Econometrica 50(1), 97–109, 33). First, we extend this protocol, proposing a novel mechanism that captures the peculiarities of these settings. Then, we analyze agents’ equilibrium strategies in complete information bargaining and we find that for a large subset of the space of the parameters, the equilibrium outcome depends on the values of a narrow number of parameters. Finally, we study incomplete information bargaining with one-sided uncertainty regarding agents’ reserve prices and we provide an algorithm based on the combination of game theoretic analysis and search techniques which finds agents’ equilibrium in pure strategies when they exist.     

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.     

Ontologies for supporting negotiation in e-commerce

In this paper we present our experience in applying Semantic Web technology to automated negotiation. This result is a novel approach to automated negotiation, that is particularly suitable to open environments such as the Internet. In this approach, agents can negotiate in any type of marketplace regardless of the negotiation mechanism in use. In order to support a wide variety of negotiation mechanisms, protocols are not hard-coded in the agents participating to negotiations, but are expressed in terms of a shared ontology, thus making this approach particularly suitable for applications such as electronic commerce. The paper describes a novel approach to negotiation, where the negotiation protocol does not need to be hard-coded in agents, but it is represented by an ontology: an explicit and declarative representation of the negotiation protocol. In this approach, agents need very little prior knowledge of the protocol, and acquire this knowledge directly from the marketplace. The ontology is also used to tune agents’ strategies to the specific protocol used. The paper presents this novel approach and describes the experience gained in implementing the ontology and the learning mechanism to tune the strategy.     

Negotiation among autonomous computational agents: principles,analysis and challenges

Automated negotiation systems with software agents representing individuals or organizations and capable of reaching agreements through negotiation are becoming increasingly important and pervasive. Examples, to mention a few, include the industrial trend toward agent-based supply chain management, the business trend toward virtual enterprises, and the pivotal role that electronic commerce is increasingly assuming in many organizations. Artificial intelligence (AI) researchers have paid a great deal of attention to automated negotiation over the past decade and a number of prominent models have been proposed in the literature. These models exhibit fairly different features, make use of a diverse range of concepts, and show performance characteristics that vary significantly depending on the negotiation context. As a consequence, assessing and relating individual research contributions is a difficult task. Currently, there is a need to build a framework to define and characterize the essential features that are necessary to conduct automated negotiation and to compare the usage of key concepts in different publications. Furthermore, the development of such a framework can be an important step to identify the core elements of autonomous negotiating agents, to provide a coherent set of concepts related to automated negotiation, to assess progress in the field, and to highlight new research directions. Accordingly, this paper introduces a generic framework for automated negotiation. It describes, in detail, the components of the framework, assesses the sophistication of the majority of work in the AI literature on these components, and discusses a number of prominent models of negotiation. This paper also highlights some of the major challenges for future automated negotiation research.