Automating Negotiation

When computer scientist Tim Baarslag had to negotiate the purchase of his new house, he developed an algorithm to help him. Thanks to the algorithm, he managed to buy his favorite house for only $1,500 more than the bid of the next-highest bidder.

Baarslag works at the Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands, where he studies how computers can help humans to negotiate better deals. He also is co-organizer of the Automated Negotiating Agents Competition (ANAC), a contest that has been held annually since 2010; this year, it took place in July during the International Joint Conference on Artificial Intelligence (IJCAI) in Stockholm, Sweden.

At IJCAI, Baarslag answered some questions for Bennie Mols.

What is the purpose of the Automated Negotiating Agents Competition?

For humans, negotiations are often very complex and stressful; think about buying a house, or negotiating about a job. What if computers can help us with this? That would be great, but then we have to know how well computers perform. With ANAC, we want in the first place to compare negotiating computers in the same domain. The competition is also a way to collect a state of the art repository of negotiating agents and their results. Finally, the competition is a way to steer the academic research.

In which aspects of negotiating are computers typically good or bad?

Computers are much better than humans in rapidly exploring the vast space of potential deals, sometimes consisting of millions of possibilities. They can send thousands of bids back and forth within fractions of a second, and they can use machine learning to understand the preferences of the other party.

However, we humans still have to specify what the relevant issues of the negotiation are. If certain aspects are not specified, then they are beyond the computer's horizon. Humans also often use creativity in negotiations; if we can't find a deal on a certain set of issues, we can think out of the box and suggest a deal by including a new issue that previously has not been considered.

Which competitions do you organize within ANAC?

This year, we have three competitions.

We have the so-called Genius League, in which computers negotiate with other computers. Genius is an open source platform that I helped to develop for general negotiations. The idea is that from a mathematical point of view, all negotiations can be specified by the relevant issues of negotiation, by values of outcomes, and by preferences of bidding agents.

Second, we organize a Human-Agent League in which computers negotiate with humans. And third, we have a Diplomacy League, in which computers play the game of Diplomacy, a board game in which seven players try to conquer Europe. Players have to negotiate with each other, but it is not clear beforehand what players will get out of a deal.

What have you learned from this year's results?

The general conclusion is that it looks like the negotiation agents focus too much on the short term, whereas they should think more steps ahead if they want to find successful deals.

In the Human-Agent League, we saw that we are now at the point where computers beat the average human, although probably not yet the expert. Last year, we had agents that were either nice and making bad deals, or winning and behaving very unpleasantly. This year, we looked at repeated negotiation for reputation-building. Computers are now getting better at this. Humans do return favors over time, but they are not necessarily good at estimating the size of the favor.

Diplomacy is also still very hard for computers. We currently do not have any negotiation algorithm that is intelligent enough to really improve the performance of a Diplomacy player.

Where do you hope to see applications of negotiating computers?

Imagine self-driving cars that negotiate automatically about who will get priority at a crossing. Or, imagine a smart electricity grid in which agents negotiate on behalf of homeowners who can use the solar power of a neighbor who goes on holiday.

I can also see applications in the Internet of Things. Agents can negotiate on our behalf about a balance between privacy and functionality. Some people are willing to trade privacy for functionality, while others are not.

How do you see the future of negotiating computers?

Next year, we want to organize a new league in which humans can be represented by computers in a negotiation. In the beginning, the computer does not yet know very well what you want, but by asking you questions, the machine develops a better picture of your preferences. This new league builds on the idea of a synergy between human and machine: some aspects of the negotiation can be better done by humans, and other aspects better by machines.

Scientifically, this is very challenging. Computers should learn to ask the right question at the right moment, but at the same time, should not bother you too much.

Bennie Mols is a science and technology writer based in Amsterdam, the Netherlands.