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 model has the advantage that it can be applied in settings where combinatorial and simultaneous models are infeasible
(e.g., when resources are made available at different points in time by different parties), as well as certain benefits in
settings where combinatorial models are applicable. We develop a dynamic programming model for agents to compute bidding policies based on estimated distributions over prices. We also describe how these distributions are updated to provide a learning
model for bidding behavior.
Parts of this paper appeared in C. Boutilier, M. Goldszmidt, B. Sabata, “Sequential Auctions for the Allocation of Resources
with Complementarities,” Proc. Sixteenth Intl. Joint Conf. on AI, Stockholm, pp.527-534 (1999).