Sequential Auctions for the Allocation of Resources with Complementarities

Abstract

Market-based mechanisms such as auctions are being studied as an appropriate means for reso urce allocation in distributed and multiagen t decision problems. When agents value reso urces in combination rather than in iso la ti on, one ge nerally relies on combinatorial auctions where agents bid for resource bundles, or simultaneous auctions for all resources. We deve lop a diffe rent model , where age nts 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 di stributions over price s. We also describe how these distributions are updated to provide a learning model for bidding behavior.