Automated Negotiation with Gaussian Process-based Utility Models

Haralambie Leahu, Michael Kaisers, Tim BaarslagIJCAI 2019 · DOI

TL;DR

This paper introduces a novel approach to automated negotiation by using Gaussian Processes (GPs) to model user preferences. This allows agents to learn user utilities efficiently, even with incomplete information and noisy feedback, by focusing on comparative preferences and minimizing costly explicit queries. The proposed method outperforms a baseline random strategy in simulations, demonstrating its effectiveness in achieving better negotiation outcomes with fewer elicitation costs.

What Problem Does This Paper Address?

Automated negotiation agents are crucial for various applications, from financial trading to cloud computing. A key challenge is equipping these agents with accurate knowledge of user preferences to make optimal decisions. However, directly eliciting this information can be inconvenient and costly for users. Existing methods often struggle with incomplete information, noisy user feedback, and the combinatorial explosion of possible outcomes in multi-issue negotiations. This paper tackles the problem of designing agents that can efficiently learn user preferences and strike a balance between negotiation and preference elicitation, minimizing the cost of learning while maximizing the negotiation outcome.

Methods

The core of this paper lies in its novel utility model and its integration into a belief Markov Decision Process (MDP) framework.

  • Gaussian Process (GP)-based Utility Model: The authors propose a stochastic, inverse-ranking utility model that leverages Gaussian Processes. GPs are powerful for modeling functions with uncertainty, and here they are used to represent a user's utility function. The "inverse-ranking" aspect means the utility is derived from the rank of an outcome within the set of all possible outcomes, based on the GP's prediction. This approach naturally handles ordinal preferences (comparisons like "A is better than B") and allows for uncertainty quantification.
  • Handling Ties and Online Updates: The model extends existing GP preference learning by explicitly handling "ties" (indifference between two options), which is more realistic. It also derives sequential update rules for the GP, enabling real-time integration of new preference data.
  • Belief MDP Framework: The negotiation process is framed as a belief MDP. The agent maintains beliefs (represented by GPs) about the user's utility and the opponent's acceptance probability. Actions include making offers or posing comparative queries to the user.
  • Myopic Elicitation Strategy: The paper proposes a myopic (one-step lookahead) strategy for deciding when to elicit more information versus when to make an offer. This strategy evaluates the potential gain from a query against the cost of the query and the immediate reward from making an offer. It aims to maximize the expected immediate reward by strategically choosing queries that reduce uncertainty in relevant areas.

Datasets

Not discussed in the paper. The experiments are based on simulated negotiation scenarios with predefined ground truth utility functions.

Key Insights and Ideas

  • Ordinal Preferences are Key: The paper emphasizes that users often express preferences ordinally (comparisons) rather than by assigning precise numerical utilities. The proposed model effectively leverages this by using GPs to learn from these comparative judgments.
  • Balancing Elicitation and Negotiation: The core challenge is finding the sweet spot between asking for more information and making a deal. The myopic strategy provides a principled way to do this by evaluating the expected utility gain from a query against its cost.
  • GP's Flexibility: Gaussian Processes are well-suited for this task due to their ability to model complex functions, quantify uncertainty, and be updated efficiently with new data. The inverse-ranking formulation provides a data-measurable utility that remains within a fixed range.
  • Myopic vs. Random Elicitation: The experimental results highlight that a strategic, myopic approach to elicitation significantly outperforms a random strategy, leading to higher expected discounted utility even when considering query costs.

Key Results

The paper presents simulation results comparing their myopic elicitation strategy against a randomized elicitation strategy.

  • Outperformance: The myopic strategy consistently achieved higher expected discounted utility across various query cost factors (γ). For instance, with a cost factor of γ=1 (cost-free), the myopic strategy yielded a utility of 7.66, while the random strategy achieved 4.80.
  • Query Efficiency: The myopic strategy generally required fewer queries to achieve comparable or better results, especially as the cost of queries increased. The number of queries for the myopic strategy increased with decreasing cost (increasing γ), indicating it leverages lower costs to gather more information.
  • Impact of Cost: As the query cost factor γ decreased (meaning queries became more expensive), the myopic agent made fewer queries, demonstrating its cost-awareness.

Limitations and Future Work

  • Myopic Nature: The current elicitation strategy is myopic (one-step lookahead). The authors acknowledge that a more sophisticated, multi-step lookahead strategy could potentially yield even better results but would require more complex modeling and optimization.
  • Opponent Modeling: The current model primarily focuses on user preference elicitation. While it uses an opponent acceptance probability, more advanced opponent modeling could further improve negotiation outcomes.
  • Scalability: While the approach is theoretically applicable to complex, multi-issue negotiation spaces, the numerical experiments were conducted on a small, one-dimensional space. Further work is needed to explore scalability and computational efficiency for larger problems.
  • Generalization: The authors suggest adapting the GP covariance function for multi-issue negotiation spaces and exploring different types of queries with varying costs.

Summary updated

BibTeX
@inproceedings{leahu2019automated,
  author = {Haralambie Leahu and Michael Kaisers and Tim Baarslag},
  title = {{Automated Negotiation with Gaussian Process-based Utility Models}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/60},
}
Figure