Optimal Value of Information Based Elicitation During Negotiation

Autonomous agents engaging in automatic negotiations on behalf of humans or institutions are usually assumed to have full knowledge of the utility function for the actors they represent. In many cases, these utility functions are difficult to know apriori for every possible outcome of the negotiation. Moreover, it may not be necessary for the agent to know the utility of outcomes that are never offered or considered during the negotiation. State-of-the-art approaches to utility elicitation during negotiation assume that the agent can ask questions from a predefined countable set to reduce its uncertainty about the utility function. This paper extends that body of work by lifting the countability assumption providing an optimal algorithm for selecting the best outcome and utility level about which to ask the actor. The paper reports the results of comparing the proposed algorithm with state-of-the-art algorithms using both synthetic and realistic negotiation scenarios. These evaluations support the applicability of the proposed approach.