Auction Protocols for Decentralized Scheduling

Abstract

Scheduling is the problem of allocating resources to alternate possible uses over designated periods of time. Several have proposed (and some have tried) market-based approaches to decentralized versions of the problem, where the competing uses are represented by autonomous agents. Market mechanisms use prices derived through distributed bidding protocols to determine an allocation, and thus solve the scheduling problem. To analyze the behavior of market schemes, we formalize decentralized scheduling as a discrete resource allocation problem, and bring to bear some relevant economic concepts. Drawing on results from the literature, we discuss the existence of equilibrium prices for some general classes of scheduling problems, and the quality of equilibrium solutions. To remedy the potential nonexistence of price equilibria due to complementarity in preference, we introduce additional markets in combinations of basic goods. We present some auction mechanisms and bidding protocols corresponding to the two market structures, and analyze their computational and economic properties. Finally, we consider direct revelation mechanisms, and compare to the market-based approach.