Strategic sequential bidding in auctions using dynamic programming

ABSTRACT

We develop a general framework in which real-time Dynamic Programming (DP) can be used to formulate agent bidding strategies in a broad class of auctions characterized by sequential bidding and continuous clearing. In this framework, states are represented primarily by an agent's holdings, and transition probabilities are estimated from the market event history, along the lines of the "belief function" approach of Gjerstad and Dickhaut [7]. We use the belief function, combined with a forecast of how it changes over time, as an approximate state-transition model in the DP formulation. The DP is then solved from scratch each time the agent has an opportunity to bid. The resulting algorithm optimizes cumulative long-term discounted profitability, whereas most previous strategies such as Gjerstad-Dickhaut (GD) merely optimize immediate profits.We test our algorithm in a simplified model of a Continuous Double Auction (CDA). Our results show that the DP-based approach reproduces the behavior of GD for small discount parameter &ggr;, and is clearly superior for large values of &ggr; close to 1. We suggest that this algorithm may offer the best performance of any published CDA bidding strategy. The framework our algorithm provides is extensible and can accommodate many market and research aspects.

REFERENCES

• 1: T. A. Bass. The Predictors. Henry Holt & Co.,1999
• 2: Dimitri P. Bertsekas, Dynamic Programming and Optimal Control, Athena Scientific, 1995
• 3: Craig Boutilier , Moisés Goldszmidt , Bikash Sabata, Sequential Auctions for the Allocation of Resources with Complementarities, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.527-523, July 31-August 06, 1999
• 4: Murray Campbell , A. Joseph Hoane, Jr. , Feng-hsiung Hsu, Deep Blue, Artificial Intelligence, v.134 n.1-2, p.57-83, January 2002 [doi>10.1016/S0004-3702(01)00129-1]
• 5: D. Cliff. Minimal-intelligence agents for bargaining behaviors in market-based environments, technical report HPL-97-91. Technical report, Hewlett Packard Labs, 1997
• 6: R. Das, J. E. Hanson, J. O. Kephart,and G. Tesauro. Agent-human interactions in the continuous double auction. In Proceedings of the 17th International Joint Conference on Artificial Intelligence , Seattle, WA, Aug. 2001. Morgan Kaufmann
• 7: S. Gjerstad and J. Dickhaut. Price formation in double auctions. Games and Economic Behavior, 22(1):1--29,Jan.1998
• 8: D. K. Gode and S. Sunder. Allocative effciency of markets with zero intelligence traders:Market as a partial substitute for individual rationality. Journal of Political Economy , 101(1):119--137, Feb.1993
• 9: J. D. Hamilton. Time Series Analysis. Princeton University Press, Princeton, NJ, 1994
• 10: Hiromitsu Hattori , Makoto Yokoo , Yuko Sakurai , Toramatsu Shintani, Determining bidding strategies in sequential auctions: quasi-linear utility and budget constraints, Proceedings of the fifth international conference on Autonomous agents, p.83-84, May 2001, Montreal, Quebec, Canada [doi>10.1145/375735.376005]
• 11: Junling Hu , Michael P. Wellman, Online learning about other agents in a dynamic multiagent system, Proceedings of the second international conference on Autonomous agents, p.239-246, May 10-13, 1998, Minneapolis, Minnesota, United States [doi>10.1145/280765.280839]
• 12: J. Rust, J. H. Miller, and R. Palmer. Behavior of trading automata in a computerized double auction market. In D.Fried and J.Rust, editors, The Double Auction Market: Institutions, Theories, and Evidence, pages 155--198. Addison-Wesley, Redwood City, CA, 1992
• 13: Jonathan Schaeffer, One jump ahead: challenging human supremacy in checkers, Springer-Verlag New York, Inc., New York, NY, 1997
• 14: V. L. Smith. An experimental study of competitive market behavior. Journal of Political Economy, 70(3):111--137, Apr.1962.
• 15: V. L. Smith. Microeconomic systems as an experimental science. American Economic Review, 72(5):923--955, Dec.1982
• 16: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 17: Gerald Tesauro, Programming backammon using self-teaching neural nets, Artificial Intelligence, v.134 n.1-2, p.181-199, January 2002 [doi>10.1016/S0004-3702(01)00110-2]
• 18: Gerald Tesauro , Rajarshi Das, High-performance bidding agents for the continuous double auction, Proceedings of the 3rd ACM conference on Electronic Commerce, p.206-209, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501183]
• 19: W. E. Walsh, R. Das, G. Tesauro, and J. O. Kephart. Analyzing complex strategic interactions in multi-agent games. In Proceedings of AAAI-02 Workshop on Game-Theoretic and Decision-Theoretic Agents (GTDT-02), Edmonton, Canada, July 2002

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Algorithms, Economics, Experimentation

Keywords:
auctions, bidding and bargaining agents, dynamic programming, electronic commerce, multi-agent based simulation