Scaling Empirical Game-Theoretic Analysis.

Abstract

To analyze the incentive structure of strategic multi-agent interactions, such scenarios are often cast as games, where players optimize their payoffs by selecting a strategy in anticipation of the strategic decisions of other players. When our modeling needs are too complex to address analytically, empirical game models, game models in which observations of simulated play are used to estimate payoffs of agents, can be employed to facilitate game-theoretic analysis. This dissertation focuses on extending the capability of the empirical game-theoretic analysis (EGTA) framework for modeling and analyzing large games.

My contributions are in three distinct areas: increasing the scale of game simulation through software infrastructure, improving performance of common analytic tasks by bringing them closer to the data, and reducing sampling requirements for statistically confident analysis through sequential sampling algorithms. With the advent of EGTAOnline, an experiment management system for distributed game simulation that I developed, EGTA practitioners no longer limit their studies to what can be conducted on a single computer. Over one billion payoff observations have been added to EGTAOnline's database to date, corresponding to hundreds of distinct experiments. To reduce the cost of analyzing this data, I explored conducting analysis in the database. I found that translating data to an in-memory object representation was a dominant cost for game-theoretic analysis software. By avoiding that cost, conducting analysis in the database improves performance. A further way to improve scalability is to ensure we only gather as much data as is necessary to support analysis. I developed algorithms that interweave sampling and evaluations of statistical confidence, improving on existing ad hoc sampling methods by providing a measure of statistical confidence for analysis and reducing the number of observations taken. In addition to these software and methodological contributions, I present two applications: a strategic analysis of selecting a wireless access point for your traffic, and an investigation of mapping an analytical pricing model to a large simulated stock market.