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.

Automated Markets and Trading Agents (Download full paper)

Jeffrey K. MacKie-Mason and Michael P. Wellman

Published on: April, 2005

Abstract: Computer automation has the potential, just starting to be realized, of transforming the design and operation of markets, and the behaviors of agents trading in them. We discuss the possibilities for automating markets, presenting a broad conceptual framework covering resource allocation as well as enabling marketplace services such as search and transaction execution. One of the most intriguing opportunities is provided by markets implementing computationally sophisticated negotiation mechanisms, for example combinatorial auctions. An important theme that emerges from the literature is the centrality of design decisions about matching the domain of goods over which a mechanism operates to the domain over which agents have preferences. When the match is imperfect (as is almost inevitable), the market game induced by the mechanism is analytically intractable, and the literature provides an incomplete characterization of rational bidding policies. A review of the literature suggests that much of our existing knowledge comes from computational simulations, including controlled studies of abstract market designs (e.g., simultaneous ascending auctions), and research tournaments comparing agent strategies in a variety of market scenarios. An empirical game-theoretic methodology combines the advantages of simulation, agent-based modeling, and statistical and game-theoretic analysis.

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.

Price Prediction Strategies for Market-Based Scheduling (Download full paper)

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

Published on: June, 2004

Abstract: In a market-based scheduling mechanism, the allocation of time-specific resources to tasks is governed by a competitive bidding process. Agents bidding for multiple, separately allocated time slots face the risk that they will succeed in obtaining only part of their requirement, incurring expenses for potentially worthless slots. We investigate the use of price prediction strategies to manage such risk. Given an uncertain price forecast, agents follow simple rules for choosing whether and on which time slots to bid. We find that employing price predictions can indeed improve performance over a straightforward baseline in some settings. Using an empirical game-theoretic methodology, we establish Nash equilibrium profiles for restricted strategy sets. This allows us to con- firm the stability of price-predicting strategies, and measure overall efficiency. We further experiment with variant strategies to analyze the source of prediction's power, demonstrate the existence of self-confirming predictions, and compare the performance of alternative prediction 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.

Some Economics of Market-Based Distributed Scheduling (Download full paper)

MacKie-Mason, Jeffrey K. Walsh, William E. Wellman, Michael P. Wurman, Peter

Published on: May, 1998

Abstract: Market mechanisms solve distributed scheduling problems by allocating the scheduled resources according to market prices. We model distributed scheduling as a discrete resource allocation problem, and demonstrate the applicability of economic analysis to this framework. 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. We then present two protocols for implementing market solutions, and analyze their computational and economic properties.