Craig Boutilier
Department of Computer Science
University of British Columbia
Vancouver, BC, CANADA, V6T 1Z4
email: cebly@cs.ubc.ca
Moises Goldszmidt and Bikash Sabata
SRI International
333 Ravenswood Avenue
Menlo Park, CA 94025, USA
email: {moises,sabata}@erg.sri.com
Abstract
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