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

Christopher Kiekintveld

The goal of my thesis work is to develop game analysis techniques capable of informing strategy design in large, complex games. Complex games often defy exact solution using the conventional tools of game theory because of their size and uncertainty about the possible outcomes. Empirical game theory offers a principled approach to analysis of such games, but there are many open questions about the best methods for exploring and analyzing empirical games. I contribute to the growing body of evidence that empirical game theory can offer useful strategic guidance in very complex multi-agent domains through empirical game-theoretic analyses of two specific games, TAC SCM and a four-player variant of chess. I propose an experimental framework for evaluating candidate methods for empirical game analysis, and apply this framework to conduct two experiments. In the first, I consider applying solution concepts to noisy estimates of games. I hypothesize that solution concepts that model noise and thus produce broader predictions of the outcome will yield relatively robust solutions, even if the exact structure of the underlying noise is unknown. In the second experiment I explore the ability of serveral candidate algorithms to exploit independence structure to direct exploration of a game to more relevant regions of the outcome space, enabling more data-efficient analysis.

Subjects: 7.1 Multi-Agent Systems; 1.8 Game Playing

Submitted: Apr 24, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.