Preference Elicitation in Combinatorial Auctions ― Poster Abstract

摘要

Combinatorial auctions where bidders can bid on bundles of items can be desirable market mechanisms when the items exhibit complementarity or substitutability, so the bidder's valuations for bundles are not additive. One of the problems with these otherwise desirable mechanisms is that determining the winners is computationally complex. There has been a recent surge of interest in winner determination algorithms for such markets. Another problem, which has received less attention, is that there are an exponential number (2~(#items) ― 1) of bundles to bid on. This is complex for the bidder because she may need to invest effort or computation into determining each of her valuations (see, e.g.,). If the bidder evaluates bundles that she does not win, evaluation effort is wasted. Bidding on too many bundles can also be undesirable from the perspective of revealing unnecessary private information and from the perspective of causing unnecessary communication overhead. If the bidder omits evaluating (or bidding on) some bundles on which she would have been competitive, economic efficiency and revenue are generally compromised. A bidder could try to evaluate (more accurately) only those bundles on which she would be competitive. However, in general it is difficult for the bidder to know on which bundles she would be competitive before evaluating the bundles. To address these problems, in the full length paper corresponding to this poster, we present a design for a software agent (an elicitor) for the auctioneer that will intelligently ask the bidders the right questions for determining good allocations without asking unnecessary questions. Each of our algorithms is incremental in that it requests information, optimally propagates the implications of the answer, and does this again until it has received enough information. The key observation is that topological structure that is inherent in the problem can be used to intelligently ask only relevant questions about the bidders' preferences while still provably finding the optimal allocation(s) of the goods to the bidders.