Automated Negotiating Agents Competition (ANAC)
- 1 Motivation and Introduction
- 2 Competition Overview
- 3 Evaluation, Development and Tournaments in GENIUS
- 4 Organization Team
- 5 References and Publications on ANAC
Motivation and Introduction
The International Automated Negotiating Agents Competition (ANAC) is an annual event, held in conjunction with the International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), or the International Joint Conference on Artificial Intelligence (IJCAI). The ANAC competition brings together researchers from the negotiation community and provides unique benchmarks for evaluating practical negotiation strategies in multi-issue domains. The competitions have spawned novel research in AI in the field of autonomous agent design which are available to the wider research community.
ANAC challenges researchers to develop successful automated negotiators for scenarios where there is incomplete information about the opponent. With this competition the research community into automated negotiation steers the research its researchers, encourages the design of generic negotiating agents that are able to operate in a variety of scenarios, and provides benchmarkes of performance.
The automated negotiating agents competition has the following aims:
- Exploring and testing protocols for
- bilateral negotiations
- multilateral negotiations
- multi-threaded negotiations
- Design of efficient negotiating agents, in particular for the exploration and testing of
- preference elicitation strategies when playing against humans
- emotion exchange strategies when playing againts humans
- bidding strategies
- acceptance strategies, and
- opponent modelling strategies
- Collecting benchmark negotiation materials
- negotiating agents,
- negotiation domains (additive linear, non-linear, and so on), and
- preference profiles
Originially, the competition focussed on the area bilateral multi-issue closed negotiation. Over the years the competition addresses various topics: varying the number of negotiators, varying the complexity of the negotiation domains (additive linear versus non-linear), multi-thread and iterated negotiations with the same set of opponents, specialised negotiations for the Diplomacy Game, and negotiating against humans. The topics of upcoming challenges is determined by the research community. The meeting during which the results are presented is used to gather opinions, decisions on the topics are finalised through emails and polls.
To support the competition and our research aims, we developed GENIUS, which enables comparison over the years, and provides a repository of negotiating agents, negotiation protocols, negotiation domains and preference profiles.
The results of past competitions can be found on their respective pages, and are reported and discussed in publications. Unless explicitly mentioned otherwise, all competitions use the GENIUS framework.
- ANAC 2017, IJCAI 2017,
- League 1: repeated multilateral, deadline, discount.
- League 2: Diplomacy, multilateral, Notary, BANDANA framework.
- League 3: human opponent, bilateral, retreatable and partial offers, emotion exchange, favors and ledgers behavior, IAGO framework.
- ANAC 2016, AAMAS 2016, multilateral, domain: smart energy grid,
- ANAC 2015, AAMAS 2015, multilateral
- ANAC 2014, AAMAS 2014, non-linear utilities and very big domains
- ANAC 2013, AAMAS 2013, learning over multiple domains
- ANAC 2012, AAMAS 2012, bilateral, deadline, discount factor, private reservation value
- ANAC 2011, AAMAS 2011, bilateral, deadline, discount factor
- ANAC 2010, AAMAS 2010, bilateral, 3 minutes per agent
Information Sharing and Information Dynamics
Closed negotiation, when opponents do not reveal their preferences to each other, is an important class of real-life negotiations. As the game-theoretic approaches cannot be directly applied to design efficient negotiating agents due to the lack of information about opponent, instead, heuristic approaches are used to design negotiating agents. However, when humans are at the negotiating table, they typically prefer to share more than just bids. Negotiators can share some information of what issues are important to them, can indicate that they like one offer better than another, and so on. Per competition the type of information that is shared is indicated. So far, we never chose to go for completely open negotiations, i.e., where the negotiators share their full preference profiles.
Note that humans typically don't fully know their own preference profiles when they start negotiating (which is described as the constructive nature of preferences). This can be modelled by changing the preference profiles during the negotiations and requiring that the agents adequately adapt their behaviour.
Number of Negotiating Parties
The negotiations studied are classified into bilateral and multilateral (also known as multi party). The bilateral negotiations have been studied extensively already before the start of the ANAC competition. However, each paper presented basically its own solutions, claiming improvements over other approaches on the basis of performing well in specific example domains. The construction of GENIUS was done with aim of addressing this problem and immediately opened the possibility of organizing ANAC. This brought the research community together and led to significant improvements on the agents for automated bilateral negotiations on linear additive domains. In just a few years the improvements were getting smaller and the community realised that it was time to tackle new challenges. Increasing the number of negotiating parties inspired new inspirations as the protocols for bilateral negotiations don't easily lead to efficient approaches, and also the strategies for bidding, accepting and opponent modeling need to be changed.
In all competitions we use a deadline. The reasons for doing so are both pragmatic and to make the competition more interesting from a theoretical perspective. Without a deadline, the negotiation might go on forever, especially without any discount factors. Also, with unlimited time an agent may simply try a large number of proposals to learn the opponent’s preferences. In addition, as opposed to having a fixed number of rounds, the competition runs in real time. This introduces yet another factor of uncertainty since it is now unclear how many negotiation rounds there will be, and how much time an opponent requires to compute a counter offer. Note that this computational time will typically change depending on the size of the outcome space.
In ANAC 2010 the agents had three minutes each to deliberate. This means agents have to keep track of both their own time and the time the opponent has left. From ANAC2011 XXX check and onwards ??? XXXX, we have chosen a simpler protocol where both agents have a shared time window of three minutes.
Discount Factors and Private Reservalues
ANAC 2011 has domains that have discount factors. In ANAC 2010, almost every negotiation between the agents took the entire negotiation time of three minutes each to reach an agreement. Adding discount factors provides an incentive to the agents to reach deals faster.
In all competitions (except the Diplomacy domain) we vary the size of the domain, e.g., small domains of some dozens of outcomes, thousands, and hundreds of thousands (or worse) possible outcomes. Furthermore, in some competitions we use relatively simply structured domains for which the preference profiles can be modelled using additive linear utility functions, but in others we rectilinear hypercubes to model domains where non-linear interdependencies can exist between issues.
For the bilateral negotiation the Alternating Offers Protocol (AOP) is used. For the multilateral negotiations, two protocols are in use: the Stacked Alternating Offers Protocol (SAOP), and the Offer When You Like protocol with a Notary (NOWyL). For the IAGO framework an extension of the AOP has been developed that allows the negotiators to besides offers and a message that the agent is still working on an offer, also exchange preference statements and emotional utterances through limited natural language utterances and visual displays.
In all the GENIUS-based competitions, the agents are evaluated with respect to the utilities they achieve, but also how good the outcomes are with respect to social welfare.
- Highest average utility: the agent with highest average of the utilities it scored in all sessions is the winner.
- Highest Social welfare: the agent that has the highest average sum of the utilities of the agents and its opponents is the winner.
- (for the Human league) Agent Likeability Category. The winner will be determined by the agent that, following the conclusion of the negotiation and a subsequent survey, rates highest on user feedback questions, such as, I would use the system again in the future, I cannot recommend this system to others, I think that I would like to use this system frequently, I liked my negotiation partner, I felt like I could trust my negotiation partner.
Evaluation, Development and Tournaments in GENIUS
Negotiating agents designed using heuristic approaches need extensive evaluation, typically through simulations and empirical analysis, since it is usually impossible to predict precisely how the system and the constituent agents will behave in a wide variety of circumstances. Furthermore, there is a need for the development of a best practice repository for negotiation techniques. That is, a coherent resource that describes which negotiation techniques are best suited to a given type of problem or domain. To facilitate research in the area of negotiation the GENIUS system was introduced and is continuously further developed. It allows easy development and integration of existing negotiating agents. GENIUS can be used to simulate individual negotiation sessions as well as tournaments between negotiating agents in various negotiation scenarios. It allows the specification of negotiation protocols, negotiation domains and preference profiles. Furthermore, GENIUS can be used to train human negotiators by means of negotiations against automated agents or other humans. And for all these purposes, as a meta-purpose, it can be used to teach the design of generic automated negotiating agents.
The standing organization team consists of
- Prof. Dr. Catholijn Jonker
- Prof. Dr. Takayuki Ito
- Assoc. Prof. Katsuhide Fujita
- Asst. Prof. Reyhan Aydogan
- Dr. Tim Baarslag
For the leagues of 2017:
- Dr. Dave de Jonge: ANAC Diplomacy Strategy Game League
- MSc. Jonathna Mell: ANAC Human Agent Negotiation League
- Assoc. Prof. Katsuhide Fujita and Asst. Prof. Reyhan Aydogan: ANAC Repeated Multilateral Negotiation League
- Prof. Dr. Sarit Kraus
- Assoc. Prof Koen Hindriks
- Assoc Prof. Enrico Gerding
- Dr. Raz Lin
References and Publications on ANAC
We published several papers about the setup and results of the ANAC competitions:
- Evaluating Practical Negotiating Agents: Results and Analysis of the 2011 International Competition (link) (BibTeX) (ext. link)
- A Baseline for Non-Linear Bilateral Negotiations: The full results of the agents competing in ANAC 2014 (link) (ext. link)
In case of any irregularities on this site, please contact either Catholijn Jonker (firstname.lastname@example.org) or Reyhan Aydogan (email@example.com).