Automated Negotiation: Challenges and Tools

• Why Automated Negotiation 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 Define the negotiation problem, negotiation protocols, and articulate the main differences between negotiations and auctions.
• Why not auctions? Describes situations in which auctions are superior to negotiations and vice-versa, using arguments based on both theoretical and practical industrial considerations.
• Utility Functions 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 Introduces the most common metrics for analyzing negotiation outcomes, including the Pareto-frontier, welfare, fairness, the Nash bargaining solution.
• Classic Results 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.

Break 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 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 Introduces the most widely used mediated and unmediated negotiation protocols with a focus on the Stacked Alternating Offers Protocol.
• Negotiation Strategies 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 Introduces a few of the more widely used negotiation platforms, such as Genius, GeniusWeb, and NegMAS.
• NegMAS Describes the design and philosophical principles underlying NegMAS, and walks the audience through the installation process.
  • NegMAS: Developing a Negotiation Protocol Demonstrates developing a new protocol on NegMAS.
  • NegMAS: Developing a Negotiation Strategy Walks through the process of developing an automated negotiation strategy for the Stacked Alternating Offers Protocol on NegMAS.

Break 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.

3. Case Study: Automated Negotiations in Supply Chain Management Describes supply chain management (SCM), a real-world domain of automated negotiation in an industrial context.

• SCM: The heart of modern industry 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 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 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 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 Walks through the process of developing an
  agent for SCML using ideas introduced in the previous segment of the tutorial

Break Now, that the audience has been introduced to automated negotiation and had some hands-on experience, we turn our attention to recent advances.

4. Recent Advances in Automated Negotiation Describes recent advances in automated negotiation:

• Negotiation in the Presence of Incomplete Information: Explains the difficulties introduced by incomplete information, either about the user or the opponent’s utility function.
• Recent Decision-Theoretic Results: Describes recent algorithmic results on optimal offering strategies, including GCA, QGCA, and heuristic extensions.
• Reinforcement Learning in Automated Negotiation: Describes recent results in applying reinforcement learning to different parts of negotiation strategies, including the offering strategy and acceptance strategy.

Break 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: 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 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 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 We will wrap up the tutorial by inviting the audience to participate in extending the state of the art in this exciting domain