Efficient Search Techniques for Multi-Attribute Bilateral Negotiation Strategies

This paper proposes a principled and practical algorithm for computing optimal strategies in multi-attribute bilateral negotiations, based on Bayesian inference and combinatorial search. The algorithm estimates expected value of the negotiation, using conditional probabilities of opponent responses that are updated based on observed offers and responses. Optimal offer sequences are then computed that maximize expected value. Generally this requires combinatorial search of depth equal to the expected number of rounds, with branching ratio given by the number of possible offers times the number of possible responses. In some cases the branching ratio can be greatly reduced using local search. Also, for certain types of conditional probabilities, the combinatorial search can be eliminated, so that computation of optimal offers is only linear in search depth. The algorithm is tested for seller agents in an asymmetric protocol, in which the seller makes sequential offers, and the buyer either accepts or rejects each offer. Using local search and fast incremental computation of conditional probabilities, sellers can compute optimal policies of depth 8 in real time, and up to depth 12 in reasonable off-line CPU time. This approach may be useful both for real-time on-line planning, and for extensive off-line planning for the initial stages of a negotiation, analogous to the use of an opening book in chess.