Optimal Incremental Preference Elicitation during Negotiation

Tim Baarslag, Enrico H. GerdingIJCAI 2015

Automated negotiation agents typically require a complete profile of user preferences before they begin their task. However, in complex real-world scenarios, asking too many questions leads to "elicitation fatigue" or "user bother." This research introduces an $O(n \log n)$ optimal strategy that allows agents to incrementally ask the user for preferences during the negotiation process. This approach perfectly balances the cost of bothering the user against the potential utility gained from securing a better deal.

The Challenge of User Bother

In automated negotiation, an agent acts as a proxy for a human user. To perform effectively, the agent must understand the user's utility for various potential outcomes. Traditionally, this preference elicitation occurs in a separate, exhaustive phase before negotiation starts.

However, real-world outcome spaces are often too large to explore entirely. Furthermore, human users find constant questioning—such as "Would you prefer outcome A or B?"—stressful and arduous. This creates a classic exploration-exploitation tradeoff: how can an agent decide which preferences are actually worth asking about during a negotiation, and when should it simply settle for the information it already possesses?

Methods: Interleaving Negotiation and Elicitation

The key innovation of this work is treating preference elicitation as a sequential decision problem integrated directly into the negotiation loop. The authors map this challenge to Pandora’s Problem, a classic result from search theory regarding the optimal way to open boxes with uncertain rewards and search costs.

The framework for interleaving negotiation and elicitation strategies.

The Index Strategy

The agent maintains a model of the user and the opponent. It calculates a "negotiation value" for every possible offer based on an aspiration value ($\alpha_j$), which represents the expected reward of continuing the negotiation if a current offer is rejected.

To decide whether to elicit a preference, the algorithm calculates an index ($z^v_\omega$) for each unknown offer. This index represents the "reservation price" of the information—the value at which the agent would be indifferent between taking a known reward and paying the cost to "open the box" (ask the user). The strategy follows an elegantly simple $O(n \log n)$ process:

  1. Calculate the index for all unknown offers.
  2. Sort the offers by their index.
  3. Elicit the offer with the highest index, provided that index is higher than the best value currently available.
  4. Repeat until the highest index is lower than the current best value or all offers are known.

Experimental Evaluation

The researchers evaluated their strategy using 200 simulated negotiation scenarios with an outcome space of 10 possible outcomes ($|\Omega| = 10$). User utilities were drawn from Uniform and Beta distributions to simulate different types of uncertainty. Opponents were modeled with fixed sets of acceptable offers, which the agent learned incrementally.

Key Results

The optimal policy was compared against several benchmarks, including random elicitation and a "highest expected value minus cost" heuristic.

Comparison of the optimal policy against benchmarks in (a) myopic and (b) time-dependent scenarios.

As shown in the results, the optimal policy (red line) significantly outperformed all benchmarks, particularly when elicitation costs were in the "crucial interval" of 0.1 to 0.7 on a 0-1 utility scale. The strategy proved robust across different bidding tactics, such as "Boulware" or "Conceder" tactics. By interleaving questions with bidding, the agent only asks about outcomes that are relevant to the current state of the deal, maximizing efficiency.

Limitations and Future Directions

While highly effective, the current model assumes that the utility of one offer is independent of another. In reality, preferences often have structure (e.g., preference for a specific feature across multiple outcomes). Future work could apply these rules to linear additive utility functions to elicit "issue weights" rather than individual outcome utilities. Additionally, while the "cost" of bother is currently a fixed parameter, future versions could use HCI research to dynamically determine a user's bother tolerance based on real-time interaction data.

Summary updated

BibTeX
@inproceedings{baarslag2015optimal,
  author = {Tim Baarslag and Enrico H. Gerding},
  title = {{Optimal Incremental Preference Elicitation during Negotiation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure