Empirical Game-Theoretic Methods for Strategy Design and Analysis in Complex Games
Christopher D. Kiekintveld
Doctoral Thesis, University of Michigan, December 2008.
Download
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.
