DOC PREVIEW
Effectiveness of preference elicitation in combinatorial auctions

This preview shows page 1-2-3-4-5 out of 16 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Effectiveness of preference elicitation in combinatorialauctionsBenoˆıt Hudson and Tuomas SandholmCarnegie Mellon UniversityComputer Science Department5000 Forbes AvenuePittsburgh, PA 15213{bhudson,sandholm}@cs.cmu.eduAbstract. Combinatorial auctions where agents can bid on bundles of items aredesirable because they allow the agents to express complementarity and substi-tutability between the items. However, expressing one’s preferences can requirebidding on all bundles. Selective incremental preference elicitation by the auc-tioneer was recently proposed to address this problem [4], but the idea was notevaluated. In this paper we show, experimentally and theoretically, that automatedelicitation provides a large benefit. In all of the elicitation schemes under study,as the number of items for sale increases, the amount of information elicited isa vanishing fraction of the information collected in traditional “direct revelationmechanisms” where bidders reveal all their valuation information. Most of theelicitation schemes also maintain the benefit as the number of agents increases.We develop more effective elicitation policies for existing query types. We alsopresent a new query type that takes the incremental nature of elicitation to a newlevel by allowing agents to give approximate answers that are refined only on anas-needed basis. In the process, we present methods for evaluating different typesof elicitation policies.1 IntroductionCombinatorial auctions, where agents can submit bids on bundles of items, are eco-nomically efficient mechanisms for selling k items to n bidders, and are attractive whenthe bidders’ valuations on bundles exhibit complementarity (a bundle of items is worthmore than the sum of its parts) and/or substitutability (a bundle is worth less than thesum of its parts). Determining the winners in such auctions is a complex optimizationproblem that has recently received considerable attention (e.g., [1,7,11,15,19,20]).An equally important problem, which has received much less attention, is that ofbidding. There are 2k− 1 bundles, and each agent may need to bid on all of themto fully express its preferences. This can be undesirable for any of several reasons:determining one’s valuation for any given bundle can be computationally intractable [9,13,17]; there is a huge number of bundles to evaluate; communicating the bids can incurprohibitive overhead (e.g., network traffic); and agents may prefer not to reveal all oftheir valuation information due to reasons of privacy or long-term competitiveness [16].Appropriate bidding languages [7,8,11,18,19] can solve the communication overheadin some cases (when the bidder’s utility function is compressible). However, they stillrequire the agents to completely determine and transmit their valuation functions andas such do not solve all the issues. So in practice, when the number of items for sale iseven moderate, the bidders will not bid on all bundles. Instead, they may wastefully bidon bundles which they will not win, and they may suffer reduced economic efficiencyby failing to bid on bundles they would have won.Selective incremental preference elicitation by the auctioneer was recently proposedto address these problems [4], but the idea was not evaluated. We implemented themost promising elicitation schemes from that paper, starting from a rigid search-basedscheme and continuing to a general flexible elicitation framework. We evaluated theprevious schemes, and also developed a host of new elicitation policies. Our experi-ments show that elicitation reduces revelation drastically, and that this benefit increaseswith problem size. We also provide theoretical results on elicitation policies. Finally, weintroduce and evaluate a new query type that takes the incremental nature of elicitationto a new level by allowing agents to give approximate answers that are refined only onan as-needed basis.Smith, Sandholm, and Simmons [21] have examined elicitation in a combinatorialexchange used for multi-robot planning. Their work concentrates on the generalizationto an exchange setting, whereas the present work concentrates on elicitation policiesand query types.2 Auction and elicitation settingWe model the auction as having a single auctioneer selling a set K of items to n bidderagents (let k = |K|). Each agent i has a valuation function vi: 2K7→ R+that deter-mines a positive, finite, and private value vi(b) for each bundle b ⊆ K. We make theusual assumption that the agents have free disposal, that is, adding items to an agent’sbundle never makes the agent worse off because, at worst, the agent can dispose of extraitems for free. Formally, ∀b ⊆ K, b0⊆ b, vi(b) ≥ vi(b0). The techniques of the papercould also be used without free disposal, although more elicitation would be requireddue to less a priori structure.At the start of the auction, the auctioneer knows the items and the agents, but has noinformation about the agents’ value functions over the bundles—except that the agentshave free disposal. The auction proceeds by having the auctioneer incrementally elicitvalue function information from the agents one query at a time until the auctioneer hasenough information to determine an optimal allocation of items to agents. Therefore,we also call the auctioneer the elicitor. An allocation is optimal if it maximizes socialwelfarePni=1vi(bi), where biis the bundle that agent i receives in the allocation.1The goal of the elicitor is to determine an optimal allocation with as little elicitation aspossible.21Social welfare can only be maximized meaningfully if bidders’ valuations can be compared toeach other. We make the usual assumption that the valuations are measured in money (dollars)and thus can be directly compared.2A recent theoretical result shows that even with free disposal, in the worst case, finding an(even only approximately) optimal allocation requires exponential communication [12].3 Inference and constraint networkThe elicitor, as we designed it, never asks a query whose answer could be inferred fromthe answers to previous queries. To support the storing and propagation of informationreceived from the agents, we have the elicitor store its information in a constraint net-work.3Specifically, the elicitor stores a graph for each agent. In each graph, there is onenode for each bundle b. Each node is labeled by an interval [LBi(b), UBi(b)]. The lowerbound LBi(b) is the highest lower bound the


Effectiveness of preference elicitation in combinatorial auctions

Download Effectiveness of preference elicitation in combinatorial auctions
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Effectiveness of preference elicitation in combinatorial auctions and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Effectiveness of preference elicitation in combinatorial auctions 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?