Recent Advances in Agent-based Complex Automated Negotiation

In multi-issue negotiation, agents’ preferences are extremely important factors for reaching mutual beneficial agreements. However, agents would usually keeping their preferences in secret in order to avoid be exploited by their opponents during a negotiation. Thus, preference modelling has become an important research direction in the area of agent-based negotiation. In this paper, a bilateral multi-issue negotiation approach is proposed to help both negotiation agents to maximise their utilities under a setting that the opponent agent’s preference is private information. In the proposed approach, Bayesian learning is employed to analyse the opponent’s historical offers and approximately predicate the opponent’s preference over negotiation issues. Besides, a counter-offer proposition algorithm is integrated in our approach to help agents to generate mutual beneficial offers based on the preference learning result. Also, the experimental results indicate the good performance of the proposed approach in aspects of utility gain and negotiation efficiency.

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 paper, we propose an automated agent 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 (TKI) Mode and search for the pareto frontier using past negotiation sessions. In the experiments, we demonstrate that our agent won the ANAC-2013 qualifying round regarding as the mean score of all negotiation sessions. We also demonstrate that the proposed agent has better outcomes and greater search technique for the pareto frontier than existing agents.

Coalition formation is a problem of great interest in AI, allowing groups of autonomous rational agents to form suitable teams. Our work specially focuses on agents which are self-interested and want to negotiate for executing actions in their plans. Depending on its capabilities, an agent may not be able to perform actions alone. Then the agent needs to find partners, interested in the same actions, and agree to put their resources in common, in order to perform these actions all together. We propose in this paper a coalition formation mechanism based on: (1) an action selection algorithm, which allows an agent to select the actions to propose and deal with the incomplete information about other agents in the system and (2) a coalition evaluation algorithm, which allows an agent to select a group of agents to perform with these actions. Our coalition evaluation algorithm is designed for structured-preference context, based on the use of the information gathered in the previous interactions with other agents. It allows the agents to select partners, which are more likely interested in the actions. These algorithms are detailed and exemplified. We have studied the quality of the solution, we have implemented and tested them, and we provide the results of their evaluation.

We tackle the problem of multilateral negotiation where a group of agents has to make a joint decision. The protocol we propose guides the agents in efficiently coordinating their interrelated negotiations and to coming to an agreement especially when convergence is difficult to obtain in multiagent settings. Negotiation illocutions are formalised to allow interactions between the agents. In addition rules are provided for the agents to manage their interactions. We introduce an illustrative scenario and detail the properties of our protocol. Experimental results show that our protocol guides the agents towards an agreement with reasonable communication and computational complexity.

We provide a new representation for nonlinear utility spaces by adopting a modular decomposition of the issues and the constraints. This is based on the intuition that constraint-based utility spaces are nonlinear with respect to issues, but linear with respect to the constraints. The result is a mapping from a utility space into an issue-constraint hypergraph with the underling interdependencies. Exploring the utility space reduces then to a message passing mechanism along the hyperedges by means of utility propagation. The optimal contracts are efficiently found using a variation of the Max-Sum algorithm. We experimentally evaluate the model using parameterized random nonlinear utility spaces, showing that it can handle a large family of complex utility spaces using several exploration strategies. We also evaluate the complexity of the generated utility spaces using the entropy and establish an optimal search strategy allowing a better scaling of the model.

Against the problem of group task allocation with time constraints in open and dynamic grid environments, this paper proposes a decentralised indicator-based combinatorial auction strategy for group task allocation. In the proposed strategy, both resource providers and consumers are modeled as intelligent agents. All the agents are limited to communicating with their neighbour agents, therefore, the proposed strategy is decentralised. In addition, the proposed strategy allow agents to enter and leave the grid environments freely, and is robust to the dynamism and openness of the grid environments. Tasks in the proposed strategy have deadlines and might need the collaboration of a group of self-interested providers to be executed. The experimental results demonstrate that the proposed strategy outperforms a well-known decentralised task allocation strategy in terms of success rate, individual utility of the involved agents and the speed of task allocation.

To realize a simulation which can handle hundreds of thousands of negotiating agents keeping their detailed behaviors, massive amount of computational power is required. Also having good programmability of agents’ codes to realize complex behaviors is essential to realize it. On deploying such negotiating agents on an agent simulation, it is important to be able to handle detailed behaviors of them, as well as having a large scale simulation to cover important phenomenon that should be observed. There are strong demands to utilize GPU-based computing resources to handle large-scale but very detailed simulations. However, it is not easy task for developers to configure the sufficient parameters to be set on its compilation or execution time, analyzing their performance characteristics on various execution settings. In this paper, we present a framework to assist the coding process of negotiating agents on a traffic simulation, as well as its parameter tuning process on GPU-based programming for simulation developers to utilize GPGPU-based many parallel cores in their simulation programs efficiently. We show how our implemented prototype framework helps simulation developers optimize various parameters and coding-level optimizations to be run on various hardware and software settings.

Recon is an experimental simulation platform that supports the development of software agents interacting concurrently with other agents in negotiation domains. Unlike existing simulation toolkits that support only imperative negotiation strategies, Recon also supports declarative strategies, for applications where logic-based agents need to explain their negotiation decisions to a user. Recon is built on top of the GOLEM agent platform, specialized with a set of infrastructure agents that can manage an electronic market and extract statistics from the negotiations that take place. We evaluate the performance of Recon by showing how by increasing the number of agents in a simulation affects the agents’ time to make an offer during negotiation.

Modeling unknown opponents is known as a key factor for the efficiency of automated negotiations. The learning processes are however challenging because of (1) the indirect way the target function can be observed, and (2) the limited amount of experience available to learn from an unknown opponent at a single session. To address these difficulties we propose to adopt two approaches from transfer learning. Both approaches transfer knowledge from previous tasks to the current negotiation of an agent to aid learn the latent behavior model of an opposing agent. The first approach achieves knowledge transfer by weighting the encounter offers of previous tasks and the ongoing task, while the second one by weighting the models learnt from the previous negotiation tasks and the model learnt from the current negotiation session. Extensive experimental results show the applicability and effectiveness of both approaches. Moreover, the robustness of the proposed approaches is evaluated using empirical game theoretic analysis.

Service composition plays a crucial role in service–oriented computing allowing to deliver complex distributed applications obtained by aggregating autonomous and independent component services characterized by a given functionality and a Quality of Service. Automated negotiation is a viable approach to select component services according to their QoS values so to meet the end–to–end quality requirements of users requesting the application. This paper discusses the use of Gaussian probability functions to model negotiation strategies of service providers, and how the properties of these functions can be used to model multiple negotiations necessary for service composition as a single multi–issue negotiation. A numerical analysis shows comparable negotiation trends for the different representations of the service composition problem.

In May 2014, we organized the Fifth International Automated Negotiating Agents Competition (ANAC 2014) in conjunction with AAMAS 2014. ANAC is an international competition that challenges researchers to develop a successful automated negotiator for scenarios where there is incomplete information about the opponent. One of the goals of this competition is to help steer the research in the area of bilateral multi-issue negotiations, and to encourage the design of generic negotiating agents that are able to operate in a variety of scenarios. 21 teams from 13 different institutes competed in ANAC 2014. This chapter describes the participating agents and the setup of the tournament, including the different negotiation scenarios that were used in the competition. We report on the results of the qualifying and final round of the tournament.

Negotiation is an essential skill for agents in a multiagent system. Much work has been published on this subject, but traditional approaches assume negotiators are able to evaluate all possible deals and pick the one that is best according to some negotiation strategy. Such an approach fails when the set of possible deals is too large to analyze exhaustively. For this reason the Annual Negotiating Agents Competition of 2014 has focused on negotiations over very large agreement spaces. In this paper we present a negotiating agent that explores the search space by means of a Genetic Algorithm. It has participated in the competition successfully and finished in 2nd and 3rd place in the two categories of the competition respectively.

The Automated Negotiation Agents Competition (ANAC2014) was organized [1]. Automated agents can reduce efforts required of people during negotiations and help people for agreeing in negotiations. Therefore, development of automated agents is one of important issues. We developed AgentM based on a heuristic for the ANAC2014 competition. AgentM has three characteristics described as following:

In this paper, we show AgentM how to compromise, how to improve utility of each other and how to bid.

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. Recently, the attention of this study has focused on the nonlinear utility functions. In nonlinear utility functions, most of the negotiation strategies for linear utility functions can’t adopt to the scenarios of nonlinear utility functions. In this chapter, we propose the estimating method for the pareto frontier based on the opponent’s bids. In the proposed method, the opponent’s bid is divided into small elements considering the combinations between issues, and counted the number of the opponent’s proposing to estimated the opponent’s utility function. In addition, the genetic algorithm is employed to the proposed method to search the pareto optimal bids based on the opponent’s estimated utility and own utility. Experimental results demonstrate that our proposed method considering the interdependency between issues can search the pareto optimal bids.

Automated negotiation is a rapidly growing topic in the field of artificial intelligence. Most of the research has been dedicated to linear preferences. Approaching real life negotiations requires more realistic preference profiles to be taken into account. To address this need, nonlinear high-dimensional domains with interdependent issues were introduced. They have however posed a struggle for automated negotiation agents. The difficulty is that fast, linear models can no longer be used in such domains, and there is no time to consider all possible bids in huge spaces. This paper proposes Group2Agent (G2A), an agent that copes with these complex domains and tries to find high Social Welfare outcomes. G2A uses a variant of the Greedy Coordinate Descent (GCD) algorithm, which can scale linearly with the number of issues and is shown to be effective in locating a meaningful middle ground between negotiating parties. Our results show that G2A reaches an average Social Welfare of 1.79, being only 0.03 below the optimal Social Welfare solution and found the optimal solution itself 3 out of 25 times on pre-competition domains. In conclusion, G2A performs among the top ranking agents when it comes to Social Welfare. Furthermore its search algorithm, GCD, scales better than algorithms such as Simulated Annealing used in other agents.

Negotiation is an important skill when interacting actors might have misaligned interests. In order to support automated negotiators research the Automated Negotiation Agent Competition (ANAC) was founded to evaluate automated agents in a bilateral negotiation setting across multiple domains. An analysis of various agents’ strategies from past competitions show that most of them used an explicit opponent modeling component. While it is well known that in repeated interactions, learning the opponent and developing reciprocity become of prominent importance to achieve one’s goal, when the interactions with the same partner are not repeated, focusing on complex opponent modeling might not be the right approach. With that in mind, we explore a domain-based approach in which we form strategies based solely on two domain parameters: the reservation value and the discount factor. Following the presentation of our cognitive model, we present DoNA, a Domain-based Negotiation Agent that exemplifies our approach.

The Automated Negotiation Agents Competition (ANAC2014) was organized. Previous works proposed agents that had various strategies. In this paper, we developed a negotiation agent (WhaleAgent) for ANAC2014. WhaleAgent has two searching bid strategies and two bidding strategies. The searching bid strategies use Simulated Annealing and Hill Climbing. The bidding strategies are Hardheaded strategy and Conceder strategy. We describe these strategies based on the heuristics.

On my agent, I heavily focused on this efficiency issue to realize a great scalability for the estimation of opponents’ preferences. Naturally, to realize it, we should consider some approximation approaches. In my agent, I rather utilized a local-search based approach for searching good bid alternatives with a limited approximate estimation of the opponent’s utility space. This heuristic offering approach could also be effective to produce a better outcome as well as a better social welfare when the opponent has a mechanism which tries to sense the degree of intention for a cooperation. However, due to its nature of approximation, it may not always be sensed as a cooperative even when the agent has been tried to be cooperative to the opponent. Especially, on the nearly ending phase of the negotiation, both the agent and the opponent may stick their best compromised proposals together due to this issue. To overcome such a situation, I introduced a special gimmick named “Hotoke no kao mo sandomade”, that allows more compromised proposals at most three times. This gimmick was named that the agent will “forgive” the uncooperative reactions of the opponent when the opponent stops such uncooperative reactions after a compromised proposal from the agent was received. The approach is based on my own analysis of the possible behaviors of the agents to be submitted as well as the domains, and of course respect the same proverb that is popular in Japan.

In this study, we propose BraveCat agent, one of the ANAC 2014 finalists. The main challenge of ANAC 2014 was dealing with nonlinear utility scenarios and ultra large-size domains. Since the conventional frequency and Bayesian opponent models cannot be used to model the unknown complex nonlinear utility space or preference profile of the opponent in ultra large domains, we design a new distance based opponent model to estimate the utility of a candidate bid to be sent to the opponent in each round of the negotiation. Moreover, by using iterative deepening search, BraveCat overcomes the limitations imposed by the huge amount of memory needed in the ultra large domains. It also uses a hybrid bidding strategy that combines behaviors of time dependent, random, and imitative strategies.