Grid commerce, market-driven G-negotiation, and Grid resource management.

Although the management of resources is essential for realizing a computational grid, providing an efficient resource allocation mechanism is a complex undertaking. Since Grid providers and consumers may be independent bodies, negotiation among them is necessary. The contribution of this paper is showing that market-driven agents (MDAs) are appropriate tools for Grid resource negotiation. MDAs are e-negotiation agents designed with the flexibility of: 1) making adjustable amounts of concession taking into account market rivalry, outside options, and time preferences and 2) relaxing bargaining terms in the face of intense pressure. A heterogeneous testbed consisting of several types of e-negotiation agents to simulate a Grid computing environment was developed. It compares the performance of MDAs against other e-negotiation agents (e.g., Kasbah) in a Grid-commerce environment. Empirical results show that MDAs generally achieve: 1) higher budget efficiencies in many market situations than other e-negotiation agents in the testbed and 2) higher success rates in acquiring Grid resources under high Grid loadings.     

Evolving Fuzzy Rules for Relaxed-Criteria Negotiation

In the literature on automated negotiation, very few negotiation agents are designed with the flexibility to slightly relax their negotiation criteria to reach a consensus more rapidly and with more certainty. Furthermore, these relaxed-criteria negotiation agents were not equipped with the ability to enhance their performance by learning and evolving their relaxed-criteria negotiation rules. The impetus of this work is designing market-driven negotiation agents (MDAs) that not only have the flexibility of relaxing bargaining criteria using fuzzy rules, but can also evolve their structures by learning new relaxed-criteria fuzzy rules to improve their negotiation outcomes as they participate in negotiations in more e-markets. To this end, an evolutionary algorithm for adapting and evolving relaxed-criteria fuzzy rules was developed. Implementing the idea in a testbed, two kinds of experiments for evaluating and comparing EvEMDAs (MDAs with relaxed-criteria rules that are evolved using the evolutionary algorithm) and EMDAs (MDAs with relaxed-criteria rules that are manually constructed) were carried out through stochastic simulations. Empirical results show that: 1) EvEMDAs generally outperformed EMDAs in different types of e-markets and 2) the negotiation outcomes of EvEMDAs generally improved as they negotiated in more e-markets.      

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

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

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.     

Toward market-driven agents for electronic auction

While there are several existing agent-based systems addressing the crucial and difficult issues of automated negotiation and auction, this research has designed and engineered a society of trading agents with two distinguishing features: 1) a market-driven negotiation strategy and 2) a deal optimizing auction protocol. Unlike some of the existing systems where users manually select predefined trading strategies, in the market-driven approach, trading agents automatically select the appropriate strategies by examining the changing market situations. Results from a series of experiments suggest that the market-driven approach generally achieved more favorable outcomes as compared to the fixed strategy approach. Furthermore, it provides a more intuitive simulation of trading because trading agents are able to respond to different market situations with appropriate strategies. By augmenting the auction protocol with a deal optimization stage, trading agents can be programmed to optimize transaction deals by delaying the finalization of deals in search of better deals. Experimental results showed that by having a deal optimization stage, the auction protocol produced generally optimistic outcomes     

一种基于市场驱动的Multi-agent自动谈判策略

针对当前电子商务中基于Agent的谈判系统的谈判策略的静态性问题,提出基于市场驱动的谈判策略。Agent在谈判中能根据变化的市场情况做出可以调整比率的让步,帮助用户做出最优的交易决策,且自动地选择合适的策略。实验结果表明,采用基于市场驱动的策略比采用固定的策略的谈判结果更让用户感到满意。     

Negotiation strategies considering market, time and behavior functions for resource allocation in computational grid

Providing an efficient resource allocation mechanism is a challenge to computational grid due to large-scale resource sharing and the fact that Grid Resource Owners (GROs) and Grid Resource Consumers (GRCs) may have different goals, policies, and preferences. In a real world market, various economic models exist for setting the price of grid resources, based on supply-and-demand and their value to the consumers. In this paper, we discuss the use of multiagent-based negotiation model for interaction between GROs and GRCs. For realizing this approach, we designed the Market- and Behavior-driven Negotiation Agents (MBDNAs). Negotiation strategies that adopt MBDNAs take into account the following factors: Competition, Opportunity, Deadline and Negotiator’s Trading Partner’s Previous Concession Behavior. In our experiments, we compare MBDNAs with MDAs (Market-Driven Agent), NDF (Negotiation Decision Function) and Kasbah in terms of the following metrics: total tasks complementation and budget spent. The results show that by taking the proposed negotiation model into account, MBDNAs outperform MDAs, NDF and Kasbah.     

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.     

Evolutionary asymmetric games for modeling systems of partially cooperative agents

Based on the tenet of Darwinism, we propose a general mechanism that guides agents (which can be partially cooperative) in selecting appropriate strategies in situations of complex interactions, in which agents do not have complete information about other agents. In the mechanism, each participating agent generates many instances of itself to help it find an appropriate strategy. The generated instances adopt alternative strategies from the agent's strategy set. While all instances generated by different agents meet randomly to complete a task, every instance adapts its strategy according to the difference between the average utilities of its current strategy and all its strategies. We give a complete analysis of the mechanism for the case with two agents when each agent has two strategies, and show that by the tenet of Darwinism, agents can find their appropriate strategies through evolution and adaptation: 1) if dominant strategies exist, then the proposed mechanism is guaranteed to find them; 2) if there are two or more strict Nash equilibrium strategies, the proposed mechanism is guaranteed to find them by using different initial strategy distributions; and 3) if there is no dominant strategy and no strict Nash equilibrium, then agents will oscillate periodically. Nevertheless, the mechanism allows agent designers to derive the appropriate strategies from the oscillation by integration. For cases with two agents when each agent has two or more strategies, it is shown that agents can reach a steady state where social welfare is 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.     

Solving coalitional resource games

Coalitional Resource Games (crgs) are a form of Non-Transferable Utility (ntu) game, which provide a natural formal framework for modelling scenarios in which agents must pool scarce resources in order to achieve mutually satisfying sets of goals. Although a number of computational questions surrounding crgs have been studied, there has to date been no attempt to develop solution concepts for crgs, or techniques for constructing solutions. In this paper, we rectify this omission. Following a review of the crg framework and a discussion of related work, we formalise notions of coalition structures and the core for crgs, and investigate the complexity of questions such as determining nonemptiness of the core. We show that, while such questions are in general computationally hard, it is possible to check the stability of a coalition structure in time exponential in the number of goals in the system, but polynomial in the number of agents and resources. As a consequence, checking stability is feasible for systems with small or bounded numbers of goals. We then consider constructive approaches to generating coalition structures. We present a negotiation protocol for crgs, give an associated negotiation strategy, and prove that this strategy forms a subgame perfect equilibrium. We then show that coalition structures produced by the protocol satisfy several desirable properties: Pareto optimality, dummy player, and pseudo-symmetry.     

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.     

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.     

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     

BLGAN: Bayesian Learning and Genetic Algorithm for Supporting Negotiation With Incomplete Information

Automated negotiation provides a means for resolving differences among interacting agents. For negotiation with complete information, this paper provides mathematical proofs to show that an agent's optimal strategy can be computed using its opponent's reserve price (RP) and deadline. The impetus of this work is using the synergy of Bayesian learning (BL) and genetic algorithm (GA) to determine an agent's optimal strategy in negotiation (N) with incomplete information. BLGAN adopts: (1) BL and a deadline-estimation process for estimating an opponent's RP and deadline and (2) GA for generating a proposal at each negotiation round. Learning the RP and deadline of an opponent enables the GA in BLGAN to reduce the size of its search space (SP) by adaptively focusing its search on a specific region in the space of all possible proposals. SP is dynamically defined as a region around an agent's proposal P at each negotiation round. P is generated using the agent's optimal strategy determined using its estimations of its opponent's RP and deadline. Hence, the GA in BLGAN is more likely to generate proposals that are closer to the proposal generated by the optimal strategy. Using GA to search around a proposal generated by its current strategy, an agent in BLGAN compensates for possible errors in estimating its opponent's RP and deadline. Empirical results show that agents adopting BLGAN reached agreements successfully, and achieved: (1) higher utilities and better combined negotiation outcomes (CNOs) than agents that only adopt GA to generate their proposals, (2) higher utilities than agents that adopt BL to learn only RP, and (3) higher utilities and better CNOs than agents that do not learn their opponents' RPs and deadlines.     

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.     

A novel method for coevolving PS-optimizing negotiation strategies using improved diversity controlling EDAs

In agent-mediated negotiation systems, the majority of the research focused on finding negotiation strategies for optimizing price only. However, in negotiation systems with time constraints (e.g., resource negotiations for Grid and Cloud computing), it is crucial to optimize either or both price and negotiation speed based on preferences of participants for improving efficiency and increasing utilization. To this end, this work presents the design and implementation of negotiation agents that can optimize both price and negotiation speed (for the given preference settings of these parameters) under a negotiation setting of complete information. Then, to support negotiations with incomplete information, this work deals with the problem of finding effective negotiation strategies of agents by using coevolutionary learning, which results in optimal negotiation outcomes. In the coevolutionary learning method used here, two types of estimation of distribution algorithms (EDAs) such as conventional EDAs (S-EDAs) and novel improved dynamic diversity controlling EDAs (ID²C-EDAs) were adopted for comparative studies. A series of experiments were conducted to evaluate the performance for coevolving effective negotiation strategies using the EDAs. In the experiments, each agent adopts three representative preference criteria: (1) placing more emphasis on optimizing more price, (2) placing equal emphasis on optimizing exact price and speed and (3) placing more emphasis on optimizing more speed. Experimental results demonstrate the effectiveness of the coevolutionary learning adopting ID²C-EDAs because it generally coevolved effective converged negotiation strategies (close to the optimum) while the coevolutionary learning adopting S-EDAs often failed to coevolve such strategies within a reasonable number of generations.     

The case of the lying postman: Decoys and deception in negotiation

Much research in negotiation assumes complete knowledge among the interacting agents and/or truthful agents. These assumptions in many domains will not be realistic, and this paper extends our previous work in dealing with the case of inter-agent negotiation with incomplete information. A discussion of our existing negotiation framework sets out the rules by which agents operate during this phase of their interaction. The concept of a solution within this framework is presented; the same solution concept serves for interactions between agents with incomplete information as it does for complete information interactions. The possibility of incomplete information among agents opens up the possibility of deception as part of the negotiation strategy of an agent. Deception during negotiation among autonomous agents is thus analyzed in the Postmen Domain, which was introduced by us in a previous paper. New results regarding the non-beneficial nature of lies is presented. It is shown that hiding letters can be beneficial when negotiation is conducted over mixed deals. When the Postmen Domain is restricted to graphs having a tree topology, then it is shown that decoy letters (manufactured by a lying agent) cannever be beneficial, and that no combination of types of lies is beneficial when negotiation is conducted over all-or-nothing deals.     

Agents that react to changing market situations

Market-driven agents are negotiation agents that react to changing market situations by making adjustable rates of concession. This paper presents 1) the foundations for designing market-driven strategies of agents, 2) a testbed of market-driven agents, 3) experimental results in simulating the market-driven approach, and 4) theoretical analyses of agents' performance in extremely large markets. In determining the amount of concession for each trading cycle, market-driven agents in this research are guided by four mathematical functions of eagerness, remaining trading time, trading opportunity , and competition. At different stages of trading, agents may adopt different trading strategies, and make different rates of concession. Four classes of strategies with respect to remaining trading time are discussed. Trading opportunity is determined by considering: 1) number of trading partners, 2) spreads-differences in utilities between an agent and its trading partners, and 3) probability of completing a deal. While eagerness represents an agent's desire to trade, trading competition is determined by the probability that it is not considered as the most preferred trader by its trading partners. Experimental results and theoretical analyses showed that agents guided by market-driven strategies 1) react to changing market situations by making prudent and appropriate rates of concession, and 2) achieve trading outcomes that correspond to intuitions in real-life trading.