DM Reeves, MP Wellman, JK MacKie-Mason, and A Osepayshvili

Decision Support Systems 39:67-85, 2005
Copyright © 2004 Published by Elsevier B.V.

Abstract

A market-based scheduling mechanism allocates resources indexed by time to alternative uses based on the bids of participating agents. Agents are typically interested in multiple time slots of the schedulable resource, with value determined by the earliest deadline by which they can complete their corresponding tasks. Despite the strong complementarities among slots induced by such preferences, it is often infeasible to deploy a mechanism that coordinates allocation across all time slots. We explore the case of separate, simultaneous markets for individual time slots, and the strategic problem it poses for bidding agents. Investigation of the straightforward bidding policy and its variants indicates that the efficacy of particular strategies depends critically on preferences and strategies of other agents, and that the strategy space is far too complex to yield to general game-theoretic analysis. For particular environments, however, it is often possible to derive constrained equilibria through evolutionary search methods.

An earlier version appeared (with co-author S Swaminathan) in Fourth ACM Conference on Electronic Commerce, pages 115-124, San Diego, June 2003.

See Self-confirming price prediction for bidding in simultaneous ascending auctions, by the same authors, for follow-up research on this topic.