View Full Document

Effectiveness of preference elicitation in combinatorial auctions



View the full content.
View Full Document
View Full Document

18 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



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?