Gerald J. Tesauro and Jeffrey O. Kephart
IBM T. J. Watson Research Center
30 Saw Mill River Rd., Hawthorne NY, 10532
e-mail: tesauro@watson.ibm.com, kephart@watson.ibm.com
We propose several heuristic approaches to the development of pricing algorithms for software agents that incorporate foresight, i.e., an ability to model and predict responses by competitors. In the absence of foresight, prior work has shown that, in an economy of myopic software agents, undesirable system behaviors such as endless price wars can frequently occur (Kephart et al., 1998). We show how the introduction of even the smallest amount of lookahead in the agents' pricing algorithms can significantly reduce or eliminate the occurrence of price wars. We also investigate two approaches to developing algorithms that are capable of deep lookahead, while avoiding the classic problem of infinite recursion of opponent models. The two approaches are based on adaptations of: (i) the classic minimax fixed-depth search algorithms used in two-player games such as chess; (ii) dynamic programming (DP)-style algorithms, that have recently been extended to the domain of two-player zero-sum Markov games (Littman, 1994).