The page you are looking for has moved. You will be redirected to the new location in 5 seconds. Please update your links to use the new location at http://longhorizon.org/trey/pubs/b2hd-smith02elicit.html

Trey Smith's Publications

Sorted by Date   Sorted by Publication Type   Sorted by Topic   

Constructing and Clearing Combinatorial Auctions Using Preference Elicitation.

Trey Smith, Tuomas Sandholm, and Reid G. Simmons. In Proc. Nat. Conf on Artificial Intelligence (AAAI) Workshop on Preferences in AI and CP, 2002.

Download

[PDF]   

Abstract

Combinatorial exchanges arise naturally in multi-agent systems that execute hierarchically decomposed tasks, when the agents have uncertainty about each other's tasks and each other's capability of handling tasks. In a combinatorial exchange, the information is aggregated to one party who then decides the task allocation among the agents. Unfortunately, such exchanges can require that bidders calculate and communicate an exponential number of bids, each of which may involve solving a hard planning problem. We present a design for an auctioneer agent that can construct and clear a combinatorial exchange using preference elicitation. This design extends existing analyses of elicitation in the combinatorial auction to the combinatorial exchange. We also introduce the concept of item discovery that uses elicitation to construct the exchange when there is uncertainty about what items should be considered in the market. Our experimental results, in a multi-robot exploration domain, show that elicitation significantly reduces the number of bids that must be evaluated in order to clear the market. More important, the proportion of bids that must be evaluated decreases as we scale to larger problem instances. We also present experimental results for an anytime version of the elicitation algorithm.

BibTeX Entry

@InProceedings{smith02:elicit,
  author = 	 {Trey Smith and Tuomas Sandholm and Reid G. Simmons},
  title = 	 {Constructing and Clearing Combinatorial Auctions Using Preference Elicitation},
  booktitle = 	 {Proc. Nat. Conf on Artificial Intelligence (AAAI) Workshop on Preferences in AI and CP},
  year =	 2002,
}

Generated by bib2html.pl (written by Patrick Riley ). About this theme. Last modified: Fri May 17, 2013 12:44:57