Empirical Game-Theoretic Methods for Strategy Design and Analysis in Complex Games.

Abstract

Complex multi-agent systems often are not amenable to standard game-theoretic analysis. I study methods for strategic reasoning that scale to more complex interactions, drawing on computational and empirical techniques. Several recent studies have applied simulation to estimate game models, using a methodology known as empirical game-theoretic analysis. I report a successful application of this methodology to the Trading Agent Competition Supply Chain Management game. Game theory has previously played little—if any—role in analyzing this scenario, or others like it. In the rest of the thesis, I perform broader evaluations of empirical game analysis methods using a novel experimental framework.

I introduce meta-games to model situations where players make strategy choices based on estimated game models. Each player chooses a meta-strategy, which is a general method for strategy selection that can be applied to a class of games. These meta-strategies can be used to select strategies based on empirical models, such as an estimated payoff matrix. I investigate candidate meta-strategies experimentally, testing them across different classes of games and observation models to identify general performance patterns. For example, I show that the strategy choices made using a naive equilibrium model quickly degrade in quality as observation noise is introduced.

I analyze three families of meta-strategies that predict distributions of play, each interpolating between uninformed and naive equilibrium predictions using a single parameter. These strategy spaces improve on the naive method, capturing (to some degree) the effects of observation uncertainty. Of these candidates, I identify logit equilibrium as the champion, supported by considerable evidence that its predictions generalize across many contexts.

I also evaluate exploration policies for directing game simulations on two tasks: equilibrium confirmation and strategy selection. Policies based on computing best responses are able to exploit a variety of structural properties to confirm equilibria with limited payoff evidence. A novel policy I propose—subgame best-response dynamics—improves previous methods for this task by confirming mixed equilibria in addition to pure equilibria. I apply meta-strategy analysis to show that these exploration policies can improve the strategy selections of logit equilibrium.