Selecting Strategies Using Empirical Game Models: An Experimental Analysis of Meta-Strategies
C Kiekintveld and MP Wellman
In Seventh International Joint Conference on Autonomous Agents and Multiagent Systems, pages 1095-1102, May 2008.
Copyright (c) 2008, IFAAMAS. This is the author's version of the work.
It is posted here by permission of IFAAMAS for personal use, not for redistribution.
Download
Abstract
In many complex multi-agent domains it is impractical to compute
exact analytic solutions. An alternate means of analysis applies
computational tools to derive and analyze empirical game models.
These models are noisy approximations, which raises questions
about how to account for uncertainty when analyzing the model.
We develop a novel experimental framework and apply it to benchmark
meta-strategies - general algorithms for selecting strategies
based on empirical game models.
We demonstrate that modeling noise is important; a naive approach
that disregards noise and plays according to Nash equilibrium
yields poor choices. We introduce three parameterized algorithms
that factor noise into the analysis by predicting distributions
of opponent play. As observation noise increases, rational players
generally make less specific outcome predictions. Our comparison
of the algorithms identifies logit equilibrium as the best method for
making these predictions. Logit equilibrium incorporates a form
of noisy decision-making by players. Our evidence shows that this
is a robust method for approximating the effects of uncertainty in
many contexts. This result has practical relevance for guiding analysis
of empirical game models. It also offers an intriguing rationale
for behavioral findings that logit equilibrium is a better predictor of
human behavior than Nash equilibrium.
