Publications [#236212] of Vincent Conitzer

Journal articles or Book chapters PUBLISHED

1. Santi, P; Conitzer, V; Sandholm, T, Towards a characterization of polynomial preference elicitation with value queries in combinatorial auctions, Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science), vol. 3120 (January, 2004), pp. 1-16, Springer Berlin Heidelberg, ISSN 0302-9743 [doi]
   (last updated on 2024/04/24)

   Abstract:
   Communication complexity has recently been recognized as a major obstacle in the implementation of combinatorial auctions. In this paper, we consider a setting in which the auctioneer (elicitor), instead of passively waiting for the bids presented by the bidders, elicits the bidders' preferences (or valuations) by asking value queries. It is known that in the more general case (no restrictions on the bidders' preferences) this approach requires the exchange of an exponential amount of information. However, in practical economic scenarios we might expect that bidders' valuations are somewhat structured. In this paper, we consider several such scenarios, and we show that polynomial elicitation in these cases is often sufficient. We also prove that the family of "easy to elicit" classes of valuations is closed under union. This suggests that efficient preference elicitation is possible in a scenario in which the elicitor, contrary to what it is commonly assumed in the literature on preference elicitation, does not exactly know the class to which the function to elicit belongs. Finally, we discuss what renders a certain class of valuations "easy to elicit with value queries".