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.