Jeffrey K. MacKie-Mason

Self-Confirming Price Prediction for Bidding in Simultaneous Ascending Auctions (Download full paper)

Anna Osepayshvili, Michael P. Wellman, Daniel M. Reeves, and Jeffrey K. MacKie-Mason

Published on: July, 2005

Abstract: Simultaneous ascending auctions present agents with the exposure problem: bidding to acquire a bundle risks the possibility of obtaining an undesired subset of the goods. Auction theory provides little guidance for dealing with this problem. We present a new family of decisiontheoretic bidding strategies that use probabilistic predictions of final prices. We focus on selfconfirming price distribution predictions, which by definition turn out to be correct when all agents bid decision-theoretically based on them. Bidding based on these is provably not optimal in general, but our experimental evidence indicates the strategy can be quite effective compared to other known methods.

Exploring bidding strategies for market-based scheduling (Download full paper)

Daniel M. Reeves, Michael. P. Wellman, Jeffrey K. MacKie-Mason, and Anna Osepayshvili

Published on: March, 2005

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 complementarity 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.

Auction Protocols for Decentralized Scheduling (Download full paper)

Wellman, M. P., W. E. Walsh, P. R. Wurman and Jeffrey K. MacKie-Mason

Published on: 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.