View Full Document

Effectiveness of preference elicitation in combinatorial auctions



View the full content.
View Full Document
View Full Document

23 views

Unformatted text preview:

Effectiveness of preference elicitation in combinatorial auctions Beno t Hudson and Tuomas Sandholm Carnegie Mellon University Computer Science Department 5000 Forbes Avenue Pittsburgh PA 15213 bhudson sandholm cs cmu edu Abstract Combinatorial auctions where agents can bid on bundles of items are desirable because they allow the agents to express complementarity and substitutability between the items However expressing one s preferences can require bidding on all bundles Selective incremental preference elicitation by the auctioneer was recently proposed to address this problem 4 but the idea was not evaluated In this paper we show experimentally and theoretically that automated elicitation 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 is a vanishing fraction of the information collected in traditional direct revelation mechanisms where bidders reveal all their valuation information Most of the elicitation schemes also maintain the benefit as the number of agents increases We develop more effective elicitation policies for existing query types We also present a new query type that takes the incremental nature of elicitation to a new level by allowing agents to give approximate answers that are refined only on an as needed basis In the process we present methods for evaluating different types of elicitation policies 1 Introduction Combinatorial auctions where agents can submit bids on bundles of items are economically efficient mechanisms for selling k items to n bidders and are attractive when the bidders valuations on bundles exhibit complementarity a bundle of items is worth more than the sum of its parts and or substitutability a bundle is worth less than the sum of its parts Determining the winners in such auctions is a complex optimization problem 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 of bidding There are 2k 1 bundles and each agent may need to bid on all of them to 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 incur prohibitive overhead e g network traffic and agents may prefer not to reveal all of their valuation information due to reasons of privacy or long term competitiveness 16 Appropriate bidding languages 7 8 11 18 19 can solve the communication overhead in some cases when the bidder s utility function is compressible However they still require the agents to completely determine and transmit their valuation functions and as such do not solve all the issues So in practice when the number of items for sale is even moderate the bidders will not bid on all bundles Instead they may wastefully bid on bundles which they will not win and they may suffer reduced economic efficiency by failing to bid on bundles they would have won Selective incremental preference elicitation by the auctioneer was recently proposed to address these problems 4 but the idea was not evaluated We implemented the most promising elicitation schemes from that paper starting from a rigid search based scheme and continuing to a general flexible elicitation framework We evaluated the previous schemes and also developed a host of new elicitation policies Our experiments show that elicitation reduces revelation drastically and that this benefit increases with problem size We also provide theoretical results on elicitation policies Finally we introduce and evaluate a new query type that takes the incremental nature of elicitation to a new level by allowing agents to give approximate answers that are refined only on an as needed basis Smith Sandholm and Simmons 21 have examined elicitation in a combinatorial exchange used for multi robot planning Their work concentrates on the generalization to an exchange setting whereas the present work concentrates on elicitation policies and query types 2 Auction and elicitation setting We model the auction as having a single auctioneer selling a set K of items to n bidder agents let k K Each agent i has a valuation function vi 2K 7 R that determines a positive finite and private value vi b for each bundle b K We make the usual assumption that the agents have free disposal that is adding items to an agent s bundle never makes the agent worse off because at worst the agent can dispose of extra items for free Formally b K b0 b vi b vi b0 The techniques of the paper could also be used without free disposal although more elicitation would be required due to less a priori structure At the start of the auction the auctioneer knows the items and the agents but has no information about the agents value functions over the bundles except that the agents have free disposal The auction proceeds by having the auctioneer incrementally elicit value function information from the agents one query at a time until the auctioneer has enough information to determine an optimal allocation of items to agents Therefore we also call Pn the auctioneer the elicitor An allocation is optimal if it maximizes social welfare i 1 vi bi where bi is the bundle that agent i receives in the allocation 1 The goal of the elicitor is to determine an optimal allocation with as little elicitation as possible 2 1 2 Social welfare can only be maximized meaningfully if bidders valuations can be compared to each other We make the usual assumption that the valuations are measured in money dollars and thus can be directly compared A 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 network The elicitor as we designed it never asks a query whose answer could be inferred from the answers to previous queries To support the storing and propagation of information received from the agents we have the elicitor store its information in a constraint network 3 Specifically the elicitor stores a graph for each agent In each graph there is one node for each bundle b Each node is labeled by an interval LBi b UBi b The lower bound LBi b is the highest lower bound the elicitor can prove on the true vi b given the answers received to queries so far Analogously UBi b is the lowest


Access the best Study Guides, Lecture Notes and Practice Exams

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 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?