Constructing and Clearing Combinatorial Exchanges Using Preference Elicitation

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.