New Trends in Agent-Based Complex Automated Negotiations

In online and dynamic e-commerce environments, it is beneficial for parties to consider each other’s preferences in carrying out transactions. This is especially important when parties are negotiating, since considering preferences will lead to faster closing of deals. However, in general may not be possible to know other participants’ preferences. Thus, learning others’ preferences from the bids exchanged during the negotiation becomes an important task. To achieve this, the producer agent may need to make assumptions about the consumer’s preferences and even its negotiation strategy. Nevertheless, these assumptions may become inconsistent with a variety of preference representations. Therefore, it is more desired to develop a learning algorithm, which is independent from the participants’ preference representations and negotiation strategies. This study presents a negotiation framework in which the producer agent learns an approximate model of the consumer’s preferences regardless of the consumer’s preference representation. For this purpose, we study our previously proposed inductive learning algorithm, namely Revisable Candidate Elimination Algorithm (RCEA). Our experimental results show that a producer agent can learn the consumer’s preferences via RCEA when the consumer represents its preferences using constraints or CP-nets. Further, in both cases, learning speeds up the negotiation considerably.

Bilateral single-issue negotiation is studied a lot by researchers as a fundamental research issue in agent negotiation. During a negotiation with time constraint, a negotiation decision function is usually predefined by negotiators to express their expectations on negotiation outcomes in different rounds. By combining the negotiation decision function with negotiators’ utility functions, offers can be generated accurately and efficiently to satisfy negotiators expectations in each round. However, such a negotiation procedure may not work well when negotiators’ utility functions are nonlinear. For example, if negotiators’ utility functions are non-monotonic, negotiators may find several offers that come with the same utility; and if negotiators’ utility functions are discrete, negotiators may not find an offer to satisfy their expected utility exactly. In order to solve such a problem caused by nonlinear utility functions, we propose a novel negotiation approach in this paper. Firstly, a 3D model is introduced to illustrate the relationships among utility functions, time constraints and counter-offers. Then two negotiation mechanisms are proposed to handle two types of nonlinear utility functions respectively, ie. a multiple offers mechanism is introduced to handle non-monotonic utility functions, and an approximating offer mechanism is introduced to handle discrete utility functions. Lastly, a combined negotiation mechanism is proposed to handle nonlinear utility functions in general situations. The experimental results demonstrate the success of the proposed approach. By employing the proposed approach, negotiators with nonlinear utility functions can also perform negotiations efficiently.

Most real-world negotiation involves multiple interdependent issues, which create agent utility functions that are nonlinear. In this paper, we employ utility functions based on “cone-constraints,” which is more realistic than previous formulations. Cone-constraints capture the intuition that agents’ utilities for a contract usually decline gradually, rather than step-wise, with distance from their ideal contract. In addition, one of the main challenges in developing effective nonlinear negotiation protocols is scalability; they can produce excessively high failure rates, when there are many issues, due to computational intractability. In this paper, we propose the scalable and efficient protocols by grouping Issues. Our protocols can reduce computational cost, while maintaining good quality outcomes, with decomposing the utility space into several largely independent sub-spaces. We also demonstrate that our proposed protocol is highly scalable when compared to previous efforts in a realistic experimental setting.

Research on automated negotiators has flourished in recent years. Among the important issues considered is how these automated negotiators can proficiently negotiate with people. To validate this, many experimentations with people are required. Nonetheless, conducting experiments with people is timely and costly, making the evaluation of these automated negotiators a very difficult process. Moreover, each revision of the agent’s strategies requires to gather an additional set of people for the experiments. In this paper we investigate the use of Peer Designed Agents (PDAs) – computer agents developed by human subjects – as a method for evaluating automated negotiators. We have examined the negotiation results and its dynamics in extensive simulations with more than 300 human negotiators and more than 50 PDAs in two distinct negotiation environments. Results show that computer agents perform better than PDAs in the same negotiation contexts in which they perform better than people, and that on average, they exhibit the same measure of generosity towards their negotiation partners. Thus, we found that using the method of peer designed negotiators embodies the promise of relieving some of the need for people when evaluating automated negotiators.

An electronic market platform usually requires buyers and sellers to exchange offers-to-buy and offers-to-sell. The goal of this exchange is to reach an agreement on the suitability of closing transactions between buyers and sellers. This paper investigates multi-attribute auctions, and in particular the matchmaking of multiple buyers and sellers based on five attributes. The proposed approaches are based on a Genetic Algorithm (GA) and a Particle Swarm Optimization (PSO) approach to match buyers with sellers based on five attributes as closely as possible. Our approaches are compared with an optimal assignment algorithm called the Munkres algorithm, as well as with a simple random approach. Measurements are performed to quantify the overall match score and the execution time. Both, the GA as well as the PSO approach show good performance, as even though not being optimal algorithms, they yield a high match score when matching the buyers with the sellers. Furthermore, both algorithms take less time to execute than the Munkres algorithm, and therefore, are very attractive for matchmaking in the electronic market place, especially in cases where large numbers of buyers and sellers need to be matched efficiently.

This paper proposes a new B2B electronic commerce model by using bidding information in double auctions. In B2B electronic commerce, buyers try to purchase in multiple items at the same time, since a buyer develops something products by using purchased items. Also suppliers have an incentive of making coalitions, since buyers want to purchase in multiple items. A mechanism designer has to consider an optimal mechanism which calculates an optimal matching between buyers and suppliers. But to find an optimal matching is very hard, since a mechanism calculates all combinations between buyers and suppliers. Consequently, we propose a calculation method which has two steps, first a mechanism determines winners of buyers’ side, then, determines coalitions and winners of suppliers by using the result of buyers’ side. This paper also discusses the improved method with dynamical mechanism design by using the bidding information. The auction protocol trees are expressed by all possible results of auctions. The result of each auction is recorded and stored with bidding data and conditions for subsequent auctions. Advantages of this paper are that each developer can procure the components to develop a certain item and tasks are allocated to suppliers effectively. The previous result of auction data can be available to shorten the period of winner determinations.

Motivated by the challenges of bilateral negotiations between people and automated agents we organized the first automated negotiating agents competition (ANAC 2010). The purpose of the competition is to facilitate the research in the area bilateral multi-issue closed negotiation. The competition was based on the Genius environment, which is a General Environment for Negotiation with Intelligent multi-purpose Usage Simulation. The first competition was held in conjunction with the Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS-10) and was comprised of seven teams. This paper presents an overview of the competition, as well as general and contrasting approaches towards negotiation strategies that were adopted by the participants of the competition. Based on analysis in post–tournament experiments, the paper also attempts to provide some insights with regard to effective approaches towards the design of negotiation strategies.

The Automated Negotiation Agents Competition (ANAC-10) was held and our agent won the tournament. Our agent estimates the alternatives the opponent will offer based on the history of the opponent’s offers. In addition, our agent tries to compromise to the estimated maximum utility of the opponent by the end of the negotiation. Also, we modify the basic strategy to not exceed the limit of compromise when the opponent is uncooperative. We can adjust the speed of compromise depending on the negotiation. We introduce the new ratio(t) to control our agent’s actions at the final phase. With this improvement, our agents try to reach agreement when the opponent’s proposal is closer to our estimated maximum values. The main reason our agent outperforms the others is its ability to reach a last-minute agreement as often as possible.

This article analyzes important issues regarding the design of a successful negotiation agent for ANAC and presents the design of Yushu, one of the top-scoring agents in the first Automated Negotiating Agents Competition (ANAC). Yushu uses simple heuristics to implement a conservative concession strategy based on a dynamically computed measure of competitiveness and number of negotiations rounds left before the deadline.

We describe the strategy used by our agent, IAMhaggler, which finished in third place in the 2010 Automated Negotiating Agent Competition. It uses a concession strategy to determine the utility level at which to make offers. This concession strategy uses a principled approach which considers the offers made by the opponent. It then uses a Pareto-search algorithm combined with Bayesian learning in order to generate a multi-issue offer with a specific utility as given by its concession strategy.

This paper presents AgentFSEGA experience at the Automated Negotiation Agents Competition 2010. AgentFSEGA is a time-constrained negotiation strategy that learns the opponent’s profile out of its moves. Having at the baseline the Bayesian negotiation strategy [3], AgentFSEGA considers the negotiation time as a resource, being prepared to concede more as time passes. While AgentFSEGA performs well on relatively large domains, we prove that the performance of the negotiation strategy does not downgrade significantly even for small, engineered, domains not suited for a learning strategy.

In many situations, a form of negotiation can be used to resolve a problem between multiple parties. However, one of the biggest problems is not knowing the intentions and true interests of the opponent. Such a user profile can be learned or estimated using biddings as evidence that reveal some of the underlying interests. In this paper we present a model for online learning of an opponent model in a closed bilateral negotiation session. We studied the obtained utility during several negotiation sessions. Results show a significant improvement in utility when the agent negotiates against a state-of-the-art Bayesian agent, but also that results are very domain-dependent.