Skip to main content

Towards a characterization of polynomial preference elicitation with value queries in combinatorial auctions

Publication ,  Journal Article
Santi, P; Conitzer, V; Sandholm, T
Published in: Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)
January 1, 2004

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".

Duke Scholars

Published In

Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)

DOI

ISSN

0302-9743

Publication Date

January 1, 2004

Volume

3120

Start / End Page

1 / 16

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Santi, P., Conitzer, V., & Sandholm, T. (2004). 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), 3120, 1–16. https://doi.org/10.1007/978-3-540-27819-1_1
Santi, P., V. Conitzer, and T. Sandholm. “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) 3120 (January 1, 2004): 1–16. https://doi.org/10.1007/978-3-540-27819-1_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). 2004 Jan 1;3120:1–16.
Santi, P., et al. “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, Jan. 2004, pp. 1–16. Scopus, doi:10.1007/978-3-540-27819-1_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). 2004 Jan 1;3120:1–16.

Published In

Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)

DOI

ISSN

0302-9743

Publication Date

January 1, 2004

Volume

3120

Start / End Page

1 / 16

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences