Automated Negotiation: Challenges and Tools
AAAI 2022 Tutorial
Date and Time: February 23rd, 2022 8:30 AM to 12:30 PM (PST) = 16:30AM to 20:30AM (GMT) = 2.24 1:30 AM to 5:30 AM (JST)
Location: Online (AAAI is virtual this year) | Vancouver, Canada
Tutorial Code: MH1
Duration: 3h 30min (+ 30min breaks)
This tutorial will introduce the audience to the field of automated negotiation, providing an overview of existing results and open challenges.
Moreover, the tutorial will describe various software platforms that are being used to tackle these challenges, such as Genius and NegMAS with a focus on the latter.
Our main goal is to provide enough of the basics so that an interested listener with little past experience building negotiation software can get started developing automated negotiating agents.
More experienced listeners will benefit from a comprehensive overview of the area, as well as hands-on experience with platforms that are widely used by researchers in automated negotiation.
Who should Attend?
The target audience are postgraduate students and researchers in the fields of multi-agent systems, game theory, simulation, and practical applications of MAS.
The tutorial will introduce the concepts it needs and is a beginner-level tutorial so the prerequisites are minimal. Knowledge of basic game-theoretic concepts are advantageous but not required.
We try to cover both theoretical foundations and practical development issues.
The tutorial will alternate between theoretical and hands-on treatments of automated negotiations.
It is divided into four parts.
- The first part motivates and introduces the negotiation problem and its history, detailing some of the classic game-theoretic results in bargaining.
- The second part presents recent advances and cutting-edge challenges in the field.
- The third part presents a case study focused on automated negotiations in supply chain management, which is one of the more popular ANAC leagues.
- The final part discusses open challenges in the field
- Why Automated Negotiation (5 min) Motivates the tutorial by presenting real-world examples of applications of automated negotiation, as well as the exciting research problems it raises.
- The Negotiation Problem (5 min) Define the negotiation problem, negotiation protocols, and articulate the main differences between negotiations and auctions.
- Why not auctions? (5 min)Describes situations in which auctions are superior to negotiations and vice-versa, using arguments based on both theoretical and practical industrial considerations.
- Utility Functions (5 min) Gives a taxonomy of utility functions for single-issue and multi-issue negotiations, as well as the different types of relationships between the negotiators’ utility functions.
- Outcome Metrics (5 min) Introduces the most common metrics for analyzing negotiation outcomes, including the Pareto-frontier, welfare, fairness, the Nash bargaining solution.
- Classic Results (20 min) Presents game-theoretic analyses of negotiations and provides some of the classic results including the prefect equilibrium result of Rubinstein.
- Nash Bargaining Game: Introduces Nash’s bargaining game and his axiomatic solution.
- Other Solutions: Describes alternative solutions, i.e., other ways to reason about bargaining outcomes.
- Rubinstein’s Game: Explains Rubinstein’s solution to the extended bargaining game.
At this point, the audience has been introduced to the core problems in automated negotiation and has some appreciation for classic game-theoretic results in bargaining. We next augment that knowledge with real-time demos and hands-on experience.
2. Automated Negotiation Protocols and Strategies (45 min) The next part of the tutorial is part demonstration and part hands-on experience of applying the techniques introduced so far using the NegMAS platform.
- Negotiation Protocols (5 min) Introduces the most widely used mediated and unmediated negotiation protocols with a focus on the Stacked Alternating Offers Protocol.
- Negotiation Strategies (10 min) Describes the basic structure of a negotiating agent and the simplest heuristic strategies—which are, at the same time, the most widely used. These include time-based strategies, tit-for-tat, and nice tit-for-tat.
- Negotiation Platforms (5 min) Introduces a few of the more widely used negotiation platforms, such as Genius, GeniusWeb, and NegMAS.
- NegMAS (5 min) Describes the design and philosophical principles underlying NegMAS, and walks the audience through the installation process.
- NegMAS: Developing a Negotiation Protocol (5 min) Demonstrates developing a new protocol on NegMAS.
- NegMAS: Developing a Negotiation Strategy (10 min) Walks through the process of developing an automated negotiation strategy for the Stacked Alternating Offers Protocol on NegMAS.
- NegMAS: Running a tournament (5 min) Demonstrates running a tournament on NegMAS to compare different automated negotiation strategies.
BREAK (30 min)
Now, that the audience has been introduced to the state-of-the-art in automated negotiation, we turn our attention to recent advances.
3. Recent Advances in Automated Negotiation (45 min) Describes recent advances in automated negotiation:
- Negotiation in the Presence of Incomplete Information (10 min): Explains the difficulties introduced by incomplete information, either about the user or the opponent’s utility function.
- Recent Decision-Theoretic Results (15 min): Describes recent algorithmic results on optimal offer-ing strategies, including GCA, QGCA, and heuristic extensions.
- Supervised Learning in Automated Negotiation (10 min): Describes different applications of supervised machine learning techniques to automated negotiation for user and opponent modeling.
- Reinforcement Learning in Automated Negotiation (10 min): Describes recent results in applying reinforcement learning to different parts of negotiation strategies, including the offering strategy and acceptance strategy.
Now, that the audience is ready to develop a very basic negotiation agent, we walk them through this development in the SCML world which ties together everything we considered so far.
4. Case Study: Automated Negotiations in Supply Chain Management (40 min) Describes supply chain management (SCM), a real-world domain of automated negotiation in an industrial context.
- SCM: The heart of modern industry (5 min) Describes the core problems in SCM, and explains why is it essential to use AI to improve the efficacy of automated negotiating agents for this domain.
- Automated Negotiation in SCM in the real world (5 min) Describes the success story of Pactum, a company based almost completely on automated negotiation in the SCM space. Also touches upon other newer players like mysupply.
- SCM League (10 min) Describes the SCM League (SCML), which has been running as part of ANAC since 2019 and is organized by the presenters (among others).
- Successful SCML Strategies (10 min) Describes two of the most successful SCML agents: Godfather (winner of the innovation award at ANAC SCML 2021) and Gentle (second-place winner of the competition).
- NegMAS: Building a simple agent for SCML (10 min) [yasser] Walks through the process of developing an agent for SCML using ideas introduced in the previous segment of the tutorial.
We now turn our attention to open challenges whose solutions we believe are crucial for the field to advance.
5. Research Challenges in Automated Negotiation (30 min): Describes the major challenges inhibiting the widespread deployment of real-world automated negotiating agents, all of which offer fruitful directions for future research:
- Utility Elicitation during Negotiation (15 min) Defines the problem of negotiation under uncertainty and motivates research on utility elicitation during negotiation. Several approaches to utility elicitation during negotiation will be discussed, all of which were proposed in the past three years.
- Pandora’s Box Formulation A formulation of the problem as an instance of the famous Pandora’s box problem, showing how to adapt the solution into various elicitation strategies.
- Value of Information Formulation A value-of-information formulation of the problem, with examples of solutions in discrete and continuous search spaces.
- Situated Negotiations (15 min) This part of the tutorial deals with an open area of research in automated negotiation and is thus less focused on results than the rest of the tutorial. We introduce situated negotiations and describe some early attempts to solve problems in this space.
- Negotiation with Outside Options Presents Liet al.’s auction-theory-inspired solution to the negotiation with outside options problem, as a special case of situated negotiation.
- Concurrent Negotiations Describes a principled way of handling concurrent negotiations and relates it to earlier work in auction theory.
Conclusion (5 min) We will wrap up the tutorial by inviting the audience to participate in extending the state of the art in this exciting domain