Stronger bidding strategies through empirical game-theoretic analysis and reinforcement learning.

Abstract

Empirical game-theoretic analysis (EGTA) combines tools from simulation, search, statistics, and game-theoretic concepts to study strategic properties of large multiagent scenarios. One direct application of EGTA techniques is the study of complex market problems which, due to dynamic behavior by many agents, large strategy spaces, incomplete and incrementally revealed information, have generally resisted direct solution. I report applications of EGTA techniques to study the specific problem posed by bidding in continuous double auctions (CDAs). I develop a simulator emulating a generic CDA game commonly found in the literature, and conduct the most comprehensive CDA strategic study yet, covering versions of all major CDA strategies published to date. This EGTA study confirms prior findings about the relative performance of the different strategies. In order to improve upon existing proposals and automate the search for equilibrium strategies, I develop a general methodology to derive new strategy candidates that interleaves EGTA with reinforcement learning (RL). I apply this methodology to the CDA game, and obtain new strategies that are stronger than any other published CDA policy, culminating in a new Nash equilibrium supported by learned strategies only. I evaluate this methodology on a second scenario, the Trading Agent Competition (TAC) Travel game. Building upon an existing simulator and a dataset comprising five years of observations, I apply a similar approach to derive new CDA bidding strategies in the TAC Travel domain by interleaving EGTA and RL. New experiments confirm the superiority of the learned strategies, and find a new approximate Nash equilibrium that consists of learned strategies only. These results are evidence that the combined EGTA/RL methodology is an effective method for generating stronger strategies for CDAs, and a promising approach for other domains with similar characteristics. I formulate an iterative framework to evaluate alternative strategy exploration policies, and experimentally evaluate a set of generic policies on three market problems. I find that policies seeking beneficial deviations or best responses perform generally well, and that stochastic introduction of suboptimal deviations can often lead to more effective exploration of the strategy space in the early stages of the process.