Constructing and Clearing Combinatorial Exchanges Using Preference Elicitation

July 2002

Constructing and Clearing Combinatorial Exchanges Using Preference Elicitation

Authors:

Trey Smith, Tuomas Sandholm, and Reid Simmons

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 which 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.
@workshop{Smith-2002-122391,
author = {Trey Smith And Tuomas Sandholm And Reid Simmons},
title = {Constructing and Clearing Combinatorial Exchanges Using Preference Elicitation},
booktitle = {Proceedings of AAAI '02 Workshop 16: Preferences in AI and CP: Symbolic Approaches},
year = {2002},
month = {July},
pages = {87 - 93},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.