Qualitative One-to-Many Multi-Issue Negotiation: Approximating the QVA

When there is one buyer interested in obtaining a service from one of a set of sellers, multi-attribute or multi-issue auctions can ensure an allocation that is efficient. Even when there is no transferable utility (e.g., money), a recent qualitative version of the Vickrey auction may be used, the QVA, to obtain a Pareto-efficient outcome where the best seller wins. However, auctions generally require that the preferences of at least one party participating in the auction are publicly known, while often making this information public is costly, undesirable, or even impossible. It would therefore be useful to have a method that does not impose such a requirement, but is still able to approximate the outcome of such an auction. The main question addressed here is whether the Pareto-efficient best-seller outcome in multi-issue settings without transferable utility (such as determined by the QVA) can be reasonably approximated by multi-bilateral closed negotiation between a buyer and multiple sellers. In these closed negotiations parties do not reveal their preferences explicitly, but make alternating offers. The main idea is to have multiple rounds of such negotiations. We study three different variants of such a protocol: one that restricts the set of allowed offers for both the buyer and the seller, one where the winning offer is announced after every round, and one where the sellers are only told whether they have won or not after every round. It is shown experimentally that this protocol enables agents that can learn preferences to obtain agreements that approximate the Pareto-efficient best-seller outcome as defined by the auction mechanism. We also show that the strategy that exploits such a learning capability in negotiation is robust against and dominates a Zero Intelligence strategy. It thus follows that the requirement to publicly announce preferences can be removed when negotiating parties are equipped with the proper learning capabilities and negotiate using the proposed multi-round multi-bilateral negotiation protocol.