Often the most difficult obstacle to game-theoretic analysis of complex scenarios is developing a model of the game situation in the first place.  In the empirical game-theoretic analysis (EGTA) approach, expert modeling is augmented by empirical sources of knowledge: data obtained through real-world observations or (as emphasized here) outcomes of high-fidelity simulation. Simulation models employ procedural descriptions of strategic environments, which are often much easier to specify than declarative domain models. Our group has developed an extensive EGTA methodology, where techniques from simulation, search, and statistics combine with game-theoretic concepts to characterize strategic properties of a domain.

Empirical Game-Theoretic Analysis

Iterative EGTA process

An iterative view of the EGTA process, highlighting some key subproblems, is presented below.  The basic step is simulation of a strategy profile (vector of strategies, one for each player), determining a payoff observation (i.e., a sample drawn from the outcome distribution induced by stochastic elements of the simulation environment), which gets added to the database of payoffs. Based on the accumulated data, we induce an empirical game model. Analyzing this model may support strategic conclusions, or drive exploration of new strategies or further sampling of profile space.

Related Projects and Publications: