Approximating the Qualitative Vickrey Auction by a Negotiation Protocol

A result of Bulow and Klemperer has suggested that auctions may be a better tool to obtain an efficient outcome than negotiation. For example, some auction mechanisms can be shown to be efficient and strategy-proof. However, they generally also require that additional constraints are met which are not always easy to guarantee in practice. It thus is interesting to find methods that do not impose such constraints but still approximate the theoretically predicted outcome of the mechanism. In this paper we show that a negotiation protocol may be used to this end if the negotiating agents are capable of learning opponent preferences. The latter condition can be met by current state of the art negotiation technology. We present a protocol that approximates the theoretical outcome predicted by a so-called Qualitative Vickrey auction mechanism.Electrical Engineering, Mathematics and Computer Scienc