Negotiation Among Autonomous Computational Agents

From HLT@INESC-ID

Fernando Lopes
Fernando Lopes
Fernando Lopes is currently a researcher at the National Research Institute (INETI). He has received a PhD in Computer Science from the Technical University of Lisbon (IST). He has done a post-doc at the University of Liverpool, under the supervision of Mike Wooldridge and in collaboration with S. Fatima.

His main research interests concern “autonomous agents” and “multi-agent systems”, particularly “automated negotiation”. He is the main author of several articles published in conference proceedings and technical journals.

Addresses: www mail

Date

  • 15:00, Friday, May 30th, 2008
  • 3rd floor meeting room, INESC-ID

Speaker

  • Fernando Lopes, INETI

Abstract

Automated negotiation systems with software agents representing individuals or organizations and capable of reaching mutually beneficial agreements are becoming increasingly important and pervasive. Examples, to mention a few, include the business trend toward agent-based supply chain management, the industrial trend toward virtual enterprises, and the pivotal role that electronic commerce is increasingly assuming in many organizations.

Artificial intelligence researchers have investigated the design of autonomous computational agents with negotiation competence from two main perspectives: a theoretical or formal perspective and a practical or computational perspective. Researchers following the theoretical perspective attempt mainly to develop formal models of negotiation, i.e., models for describing, specifying, and reasoning about the key features of negotiating agents. By contrast, researchers following the practical perspective attempt mainly to develop computational models of negotiation, i.e., models for specifying the key data structures of the agents and the processes operating on these structures.

The majority of formal and computational models primarily focus on the problem-solving phase of negotiation. Most models mainly address the issues associated with the design of negotiation protocols and negotiation strategies. Few models account for systematic preparation and planning for negotiation and manage “difficult” negotiations that can end in impasse. Against this background, this presentation describes:

  • a pre-negotiation model – the model defines the main tasks that each party should attend to in order to prepare and plan for negotiation;
  • a procedure for assisting agents to avoid and resolve impasses – the procedure is based on the addition of issues during the course of negotiation, increasing the parties' willingness to settlement and facilitating the resolution of impasses. It also allows the parties to reach Pareto optimal outcomes.

Furthermore, for the bilateral multi-issue bargaining game of alternating offers, in which the parties have different evaluations of the issues, we describe equilibrium strategies for different negotiation situations. The strategies are formalized by computationally tractable functions, which means that agents are able to compute them in a reasonable amount of time. The outcome is Pareto optimal and reached with no delay.

Finally, we describe an experiment conducted to: (i) assess the feasibility of building agents equipped with the pre-negotiation model and the impasse avoidance procedure, and (ii) empirically evaluate the core elements of the agents, particularly the impasse avoidance procedure. The experimental results shown the importance of the procedure in managing "difficult" negotiations.

Keywords

  • Multi-agent systems
  • Autonomous agents
  • Automated negotiation
  • Game theory
  • Bargaining
  • Pre-negotiation
  • Impasse
  • Efficiency

Note

Team work with Mike Wooldridge and S. Fatima, Dep. of Comp. Science, Univ. of Liverpool.