Auction Protocols for Decentralized Scheduling

MP Wellman, WE Walsh, PR Wurman, and JK MacKie-Mason

Games and Economic Behavior 35:271-303, 2001.
Copyright © 2001 by Academic Press.

ERRATUM: Theorem 7.2 in this article is false. Thanks to Zhixin Liu for bringing this error to our attention (personal communication, July 2007). NG Hall & Z Liu explain the problem in a research note published by GEB in 2011.

Abstract

Decentralized scheduling is the problem of allocating resources to alternative possible uses over time, where competing uses are represented by autonomous agents. Market mechanisms use prices derived through distributing bidding protocols to determine schedules. We investigate the existence of equilibrium prices for some general classes of scheduling problems, the quality of equilibrium solutions, and the behavior of an ascending auction mechanism and bidding protocol. To remedy the potential nonexistence of price equilibria due to complementarities in preference, we introduce additional markets in combinations of basic goods. Finally, we consider direct revelation mechanisms and compare to the market-based approach.

Revised and extended version of “Some economics of market-based distributed scheduling”, Eighteenth International Conference on Distributed Computing Systems, May 1998.

Downloads

ScienceDirect