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. 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 γ, and is clearly superior for large values of γ 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.