Auction Protocols for Decentralized Scheduling
(Download full paper)Filed under research category: Online market design
Tagged as: market-based_scheduling trading_agents auctions automated_markets e-commerce market_design empirical_game_analysis bidding_strategies online_markets incentive-centered_design
Authors
Wellman, M. P., W. E. Walsh, P. R. Wurman and Jeffrey K. MacKie-Mason
Publication date
January, 2001
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.
Citation
Games and Economic Behavior vol 35, 2001.