Sequential Auctions for the Allocation of Resources with Complementarities

Craig Boutilier
Department of Computer Science
University of British Columbia
Vancouver, BC, CANADA, V6T 1Z4

Moises Goldszmidt and Bikash Sabata
SRI International 333 Ravenswood Avenue
Menlo Park, CA 94025, USA
email: {moises,sabata}

Market-based mechanisms such as auctions are being studied as an appropriate means for resource allocation in distributed and multiagent decision problems. When agents value resources in combination rather than in isolation, one generally relies on combinatorial auctions where agents bid for resource bundles, or simultaneous auctions for all resources. We develop a different model, where agents bid for required resources sequentially. This has the advantage over combinatorial models of not requiring revelation of preferences for bundles and removing the computational burden of allocation from the auctioneer; and compared to simultaneous models, agents limit their exposure when bids cannot be retracted. We develop a dynamic programming model for agents to compute bidding policies based on estimated distributions over winning bids. We also describe how these distributions are updated over time to provide a learning model for bidding behavior, suitable when access to resources is required repeatedly.

To appear, 16th International Joint Conference on Artificial Intelligence (IJCAI-99), Stockholm, August, 1999

Return to List of Papers