Generating trading agent strategies: Analytic and empirical methods for infinite and large games.

Abstract

A <italic>Strategy Generation Engine</italic> is a system that reads a description of a game or market mechanism and outputs strategies for participants. Ideally, this means a game solver---an algorithm to compute Nash equilibria. This is a well-studied problem and very general solutions exist, but they can only be applied to small, finite games. This thesis presents methods for finding or approximating Nash equilibria for infinite games, and for intractably large finite games. First, I define a broad class of one-shot, two-player infinite games of incomplete information. I present an algorithm for computing best-response strategies in this class and show that for many particular games the algorithm can be iterated to compute Nash equilibria. Many results from the game theory literature are reproduced---automatically---using this method, as well as novel results for new games. Next, I address the problem of finding strategies in games that, even if finite, are larger than what any exact solution method can address. Our solution involves (1) generating a small set of candidate strategies, (2) constructing via simulation an approximate payoff matrix for the simplification of the game restricted to the candidate strategies, (3) analyzing the empirical game, and (4) assessing the quality of solutions with respect to the underlying full game. I leave methods for generating candidate strategies domain-specific and focus on methods for taming the computational cost of empirical game generation. I do this by employing Monte Carlo variance reduction techniques and introducing a technique for approximating many-player games by reducing the number of players. We are additionally able to solve much larger payoff matrices than the current state-of-the-art solver by exploiting symmetry in games. I test these methods in small games with known solutions and then apply them to two realistic market scenarios: Simultaneous Ascending Auctions (SAA) and the Trading Agent Competition (TAC) travel-shopping game. For these domains I focus on two key price prediction approaches for generating candidate strategies for empirical analysis: self-confirming price predictions and Walrasian equilibrium prices. We find that these are highly effective strategies in SAA and TAC, respectively.