Automated Negotiation: Can it be the next big thing?

Negotiation shares one feature with Christmas and love, it is everywhere. We negotiate our way when passing the street, businesses negotiate constantly to maximize their profits and in search for win-win agreements, and haggling over prices is a constant annoyance with which some of us have a love-hate relationship.

In this article, I will try to convince you that automated negotiation can be the next big thing in AI and invite you to participate in the leading automated negotiation competition in the world (ANAC).

Automated Negotiation

With the increased adoption of AI technologies in industrial and business applications, comes renewed interest in automated negotiation as a possible way to coordinate the behavior of a plethora of automated agents representing different players in markets and industrial applications. This can clearly be sen in the rise of startups like Pactum dedicated to AI-based automated negotiation, interest from IT giants like NEC as well as industrial organizations like the IIC industrial consortium, let alone international organizations like UN/CEFACT.

The earliest concrete result in automated negotiation I could find is the Nash solution for the bargaining problem introduced by Nash (of beautiful minds fame) in 1950. Economists, game theorists, cognitive scientists and AI researchers, all contributed to our current understanding of automated negotiation.

What is automated negotiation?

But, what is automated negotiation? Informally, it is a process by which self-interested agents try to achieve agreements that are beneficial for both of them through a process (called a negotiation protocol or mechanism) with fully defined rules. When one or more of the negotiators is a computer program (agent), the process is called automated negotiations. When one of the negotiation partners is human, psychological factors like priming effects, the availability heuristic and focus points become the bread and butter of negotiators.

We focus here in the fully automated case in which all partners are AI agents.

To make our discussion more tangible, we will use an opens-source negotiation library called NegMAS (I am a maintainer of this library so this is a plug). You can install negmas using:

pip install negmas

If you prefer to live in Java-Land, you can use the excellent Genius or GeniusWeb libraries.

Negotiation happens between self-interested agents about some pre-defined negotiation issues. A common example is a negotiation between a supplier and buyer about a contract. Negotiation issues in this case may include price, quantity, delivery schedule, penalties, quality clauses, etc. Each possible assignment of a value to each negotiation issue (from its domain) is called an outcome. The set of all possible outcomes is called the outcome-space.

In NegMAS, you can define an outcome-space by simply specifying the issues:

issues = [Issue(10, "quantity"), Issue((0.0, 1.0), name="price"),
Issue(["tomorrow", "dayafter"], "delivery")]

Outcomes are represented as either lists or dicts:

o1 = (5, 0.5, "tomorrow")
o2 = dict(quantity=5, price=0.5, delivery="tomorrow")

NegMAS provides several methods for manipulating and using outcome-spaces (e.g. sampling, enumeration, validity checks, etc).

The preferences of an agent are usually represented by a utility function which maps outcomes to real values representing how good is an outcome for the agent. Common types of utility functions are linear aggregation utility functions, hyper-rectangle nonlinear utility functions, among many others.

In NegMAS, a utility function is represented by a UtilityFunction object. It is also possible to represent other types of preferences (e.g. partial orderings over outcomes). In our running example, we can define the utility function of the seller as:

seller_util = LinearUtilityAggregationFunction(
    dict(
        price=lambda x: x, 
        quantity= lambda x: 0.5 * x, 
        delivery= dict(tomorrow= 1.0, dayafter= 0.0)
    ),
    weights = [1.0, 2.0, 0.5]
)

Agents negotiate together by following a negotiation protocol (sometimes it is called negotiation mechanism) which specifies what each agent can and cannot do at every step of the negotiation.

The simplest negotiation mechanism is the alternating offers protocol in which agents take turns offering outcomes until one gets accepted, an agent leaves the negotiation or a timeout condition is met.

For more details on how to actually implement negotiators, mechanisms and conduct negotiation sessions, check NegMAS Documentation

Why is automated negotiation interesting for AI?

Now that we have some idea about what negotiation is and how to run automated negotiations, why should anyone care?

Automated Negotiation is a game in the academic game-theoretic sense. It can be compared with Chess, Poker, or Go but it provides a somewhat unique challenge.

Most of these classic games were zero-sum games in the sense that one player’s gains are the other player’s losses. Some other games considered by game-theory experts are collaborative games that can lead to win-win situations.

Negotiation on the other hand is a game with many faces. Depending on the relationship between the utility functions of the players (partners), it can be a zero-sum game, a collaborative game or anything else. The most important point here is that the agent does not know what type of game is it in.

This means that a general automated negotiation agent should be able to maximize its expected utility (or minimize its regret) in a wide spectrum of negotiation scenarios corresponding to a wide variety of games with different competitiveness.

This challenge of playing a game with incomplete information is not unique to automated negotiation. Nevertheless, I argue that automated negotiation provides a concrete case that can be adjusted in complexity by simple modifications to the scenario constraints leading to a common workbench for developing general AI approaches.

For example, we can consider negotiations with uncertainty on the agent’s own utility function, negotiations in which the agent can reduce this uncertainty at a cost, concurrent inter-related negotiations, negotiations with non-stationary utility functions, repeated negotiations, …...

Automated negotiations provides the unique combination of a practically applicable problem that drips with opportunities for new algorithmic innovations.

The ANAC Competition

AI likes competitions. Many of the most important advances in AI came as a response of a well designed game. In 2012, deep-learning registered in everyone’s radar after it achieved super human performance in a pattern recognition competition, and won the ICDAR Chinese handwriting competition.

Some researchers have seen the potential of automated negotiations for a long time now. A small research community is thriving around the International Automated Negotiating Agents Competition (ANAC) since 2010.

The competition runs every year (for 12 incarnations now) with one of the top AI conferences in the world. It started in conjunction with AAMAS but since 2017 is running on the official competition track of IJCAI.

This year, ANAC has five different challenges:

• Automated Negotiation League, exploring strategies for building effective general purpose negotiation agents.
• Human-Agent League, exploring strategies for negotiating with people using natural interaction modalities and capable of displaying and manipulating emotions.
• Supply Chain Management League, exploring strategies for negotiation in a business-like simulation environment focusing on concurrent negotiation, long term trading and learning from repeated encounters.
• Werewolf Game League, focusing on the ability to build consensus, identify agents of opposing teams and coordinating voting them out of the game.
• HUMAINE League, exploring competitive negotiation in an immersive environment.

Consider automated negotiation for your next project. It may be where we get the next big thing in AI, business or both.