Research in Computational Markets
Michael Wellman
University of Michigan, Artificial Intelligence Laboratory
Since 1992, my research group at the University of Michigan has focused on computational markets, including market-based resource allocation, market models of computation, trading strategy, and e-commerce applications. We believe that market interaction mechanisms will play a fundamental role in multiagent and distributed computing systems (Wellman and Wurman, 1998), and that informed design and deployment of computational markets can lead to significant improvements in distributed resource allocation and robust decentralization of large-scale systems. The following outlines some of our past contributions and current research in this area.
Starting with our early work on Òmarket-oriented programmingÓ (Wellman, 1993), we have continuously investigated the potential of competitive markets for solving resource-allocation problems in a distributed manner. We developed a methodology for constructing computational markets in the framework of general-equilibrium theory (Wellman, 1996), and demonstrated the approach through a series of models of simplified domains (Mullen and Wellman, 1995, Wellman, 1995, Yamaki et al., 1996). This paved the way for subsequent investigation of discrete allocation problems, applied to canonical problems such as scheduling (Wellman et al., 2001a) and supply-chain formation (Walsh and Wellman, 2003). We continue to study market-based allocation scenarios in domains such as manufacturing scheduling, reconnaisance (Cheng et al., 2003), and dynamic information processing (Wellman and Cheng, 2003).
Economists have long invoked the metaphor of economies as analog computers, effectively solving complex distributed allocation problems. Electronic markets make the metaphor tangible, and provide the opportunity to understand market behavior in a computationally precise way. What can a market compute? In a well-defined sense, distributed bidding protocols implementing classic general equilibrium models can solve general convex-programming problems (Cheng and Wellman, 1998). Combinatorial optimization problems cannot be solved by markets in general without exploding the space of goods. Nevertheless, we have found that straightforward market mechanisms can be surprisingly reliable in solving even the NP-complete problem of propositional satisfiability (Walsh et al., 2003). Market prices can also be quite effective for aggregating information about uncertain events (Pennock and Wellman, 1997). Combinatorial betting markets are generally complex (Fortnow et al., 2003), although compact information markets can be constructed in special settings (Pennock and Wellman, 2000).
The emergence of computational markets presents new opportunities for automated trading by autonomous software agents. To spur research and focus attention on common problems, we instituted an annual Trading Agent Competition (TAC) (Wellman et al., 2001b), now operated by the Swedish Institute for Computer Science (SICS, http://www.sics.se/tac). The original (ÒclassicÓ) TAC market game presents a travel-shopping scenario, where agents compete to assemble travel packages for their clients through simultaneous interacting markets (Wellman et al., 2003b). The TAC Classic event has yielded numerous research contributions, and a steady increase of competitiveness (Wellman et al., 2003a). Our own research in that domain demonstrated a surprisingly effective approach to price prediction by competitive equilibrium analysis (Cheng et al., 2004a, Wellman et al., 2004). The newer TAC supply-chain game (designed by CMU and SICS) has also generated substantial research interest, and in the first year demonstrated a striking strategic dynamic (Estelle et al., 2004).
The trading agent competition offers a concrete environment in which to evaluate and compare trading strategies. We have also been pursuing more general techniques to apply formal game-theoretic principles to intractable games: environments featuring substantial uncertainty, dynamics, and enormous or even infinite strategy spaces. We have developed a four-step empirical game-theoretic methodology, based on abstracting the strategy space and employing simulation and statistical techniques to estimate and solve approximate versions of the game. To date we have applied this approach to problems in market-based scheduling (MacKie-Mason et al., 2004, Reeves et al., 2004), as well as the TAC domains and some of the other examples noted above. Coupled with advances in game-solving algorithms exploiting locality in agent interaction (Singh et al., 2004), symmetry (Cheng et al., 2004b), or other regularities in payoff functions (Reeves and Wellman, 2004), these methods can dramatically expand the scope of applicability of game-theoretic techniques.
Automating markets and trading fulfills a central step in the more comprehensive automation of commerce activity generally. We have therefore devoted significant effort to developing and deploying auctions and related market infrastructure (Lochner and Wellman, 2004, Wurman et al., 1998a, Wurman et al., 1998b), and to characterizing the auction design space (Wurman et al., 2001). Formalizing the available mechanisms opens the possibility of automating the formulation of customized auction mechanisms for particular contract-negotiation episodes (Reeves et al., 2002).
Bibliography
CHENG, J. Q. & WELLMAN, M. P. (1998) The WALRAS algorithm: A convergent distributed implementation of general-equilibrium outcomes. Computational Economics, 12, 1-24.
CHENG, S.-F., LEUNG, E., LOCHNER, K. M., O'MALLEY, K., REEVES, D. M., SCHVARTZMAN, L. J. & WELLMAN, M. P. (2004a) Walverine: A Walrasian trading agent. Decision Support Systems.
CHENG, S.-F., REEVES, D. M., VOROBEYCHIK, Y. & WELLMAN, M. P. (2004b) Notes on equilibria in symmetric games. University of Michigan.
CHENG, S.-F., WELLMAN, M. P. & PERRY, D. G. (2003) Market-based resource allocation for information-collection scenarios. IJCAI-03 Workshop on Multi-Agent for Mass User Support. Acapulco.
ESTELLE, J., VOROBEYCHIK, Y., WELLMAN, M. P., SINGH, S., KIEKINTVELD, C. & SONI, V. (2004) Strategic interactions in the 2003 TAC supply chain tournament. Fourth International Conference on Computers and Games.
FORTNOW, L., KILIAN, J., PENNOCK, D. M. & WELLMAN, M. P. (2003) Betting Boolean-style: A framework for trading in securities based on logical formulas. Fourth ACM Conference on Electronic Commerce. San Diego.
LOCHNER, K. M. & WELLMAN, M. P. (2004) Rule-based specification of auction mechanisms. Third International Joint Conference on Autonomous Agents and Multiagent Systems. New York.
MACKIE-MASON, J. K., OSEPAYSHVILI, A., REEVES, D. M. & WELLMAN, M. P. (2004) Price prediction strategies for market-based scheduling. Fourteenth International Conference on Automated Planning and Scheduling. Whistler, BC.
MULLEN, T. & WELLMAN, M. P. (1995) A simple computational market for network information services. First International Conference on Multiagent Systems. San Francisco, CA, MIT Press.
PENNOCK, D. M. & WELLMAN, M. P. (1997) Representing aggregate belief through the competitive equilibrium of a securities market. Thirteenth Conference on Uncertainty in Artificial Intelligence. Providence, RI.
PENNOCK, D. M. & WELLMAN, M. P. (2000) Compact securities markets for Pareto optimal reallocation of risk. Sixteenth Conference on Uncertainty in Artificial Intelligence. Stanford, CA.
REEVES, D. M. & WELLMAN, M. P. (2004) Computing best-response strategies in infinite games of incomplete information. Twentieth Conference on Uncertainty in Artificial Intelligence. Banff.
REEVES, D. M., WELLMAN, M. P. & GROSOF, B. N. (2002) Automated negotiation from declarative contract descriptions. Computational Intelligence, 18, 482-500.
REEVES, D. M., WELLMAN, M. P., MACKIE-MASON, J. K. & OSEPAYSHVILI, A. (2004) Exploring bidding strategies for market-based scheduling. Decision Support Systems.
SINGH, S., SONI, V. & WELLMAN, M. P. (2004) Computing approximate Bayes-Nash equilibria in tree-games of incomplete information. Fifth ACM Conference on Electronic Commerce. New York.
WALSH, W. E. & WELLMAN, M. P. (2003) Decentralized supply chain formation: A market protocol and competitive equilibrium analysis. Journal of Artificial Intelligence Research, 19, 513-567.
WALSH, W. E., YOKOO, M., HIRAYAMA, K. & WELLMAN, M. P. (2003) On market-inspired approaches to propositional satisfiability. Artificial Intelligence, 144, 125-156.
WELLMAN, M. P. (1993) A market-oriented programming environment and its application to distributed multicommodity flow problems. Journal of Artificial Intelligence Research, 1, 1-23.
WELLMAN, M. P. (1995) A computational market model for distributed configuration design. AI for Engineering, Design, and Manufacturing (AI EDAM), 9, 125-133.
WELLMAN, M. P. (1996) Market-oriented programming: Some early lessons. In CLEARWATER, S. (Ed.) Market-Based Control: A Paradigm for Distributed Resource Allocation. World Scientific.
WELLMAN, M. P. & CHENG, S.-F. (2003) Market-based task allocation for dynamic information processing environments. International Conference on Integration of Knowledge-Intensive Multi-Agent Systems. Cambridge, MA.
WELLMAN, M. P., CHENG, S.-F., REEVES, D. M. & LOCHNER, K. M. (2003a) Trading agents competing: Performance, progress, and market effectiveness. IEEE Intelligent Systems, 18, 48-53.
WELLMAN, M. P., GREENWALD, A., STONE, P. & WURMAN, P. R. (2003b) The 2001 Trading Agent Competition. Electronic Markets, 13, 4-12.
WELLMAN, M. P., REEVES, D. M., LOCHNER, K. M. & VOROBEYCHIK, Y. (2004) Price prediction in a trading agent competition. Journal of Artificial Intelligence Research, 21, 19-36.
WELLMAN, M. P., WALSH, W. E., WURMAN, P. R. & MACKIE-MASON, J. K. (2001a) Auction protocols for decentralized scheduling. Games and Economic Behavior, 35, 271-303.
WELLMAN, M. P. & WURMAN, P. R. (1998) Market-aware agents for a multiagent world. Robotics and Autonomous Systems, 24, 115-125.
WELLMAN, M. P., WURMAN, P. R., O'MALLEY, K., BANGERA, R., LIN, S.-D., REEVES, D. & WALSH, W. E. (2001b) Designing the market game for a trading agent competition. IEEE Internet Computing, 5, 43-51.
WURMAN, P. R., WALSH, W. E. & WELLMAN, M. P. (1998a) Flexible double auctions for electronic commerce: Theory and implementation. Decision Support Systems, 24, 17-27.
WURMAN, P. R., WELLMAN, M. P. & WALSH, W. E. (1998b) The Michigan Internet AuctionBot: A configurable auction server for human and software agents. Second International Conference on Autonomous Agents. Minneapolis.
WURMAN, P. R., WELLMAN, M. P. & WALSH, W. E. (2001) A parametrization of the auction design space. Games and Economic Behavior, 35, 304-338.
YAMAKI, H., WELLMAN, M. P. & ISHIDA, T. (1996) A market-based approach to allocating QoS for multimedia applications. Second International Conference on Multiagent Systems. Kyoto, Japan, AAAI Press.