Information Technology Reference
In-Depth Information
comprehensive and structured experimentation process. Its successor placed third again
in 2003, and regained its first-place standing in 2004. Since the rules were adjusted for
TAC-04, this most recent outcome required a new regimen of experiments.
4
Hierarchical Game Reduction
4.1
Motivation
Suppose that we manage to narrow down the candidate
Walverine
variants to a reason-
able number of strategies (say 40). Because the performance of a strategy for one agent
depends on the strategies of the other seven, we wish to undertake a game-theoretic
analysis of the situation. Determining the payoff for a particular strategy profile is ex-
pensive, however, as each game instance takes nine minutes to run, plus another minute
or two to calculate scores, compile results, and set up the next simulation. Moreover,
since the environment is stochastic, numerous samples (say 12) are required to produce
a reliable estimate for even one profile. At roughly two hours per profile, exhaustively
exploring profile space will require 2
40
8
or 13 trillion hours simply to estimate the
payoff function representing the game under analysis. If the game is symmetric, we can
·
exploit that fact to reduce the number of distinct profiles to
4
8
, which will require 628
million hours. That is quite a bit less, but still much more time than we have.
The idea of hierarchical game reduction is that although a strategy's payoff does
depend on the play of other agents (otherwise we are not in a game situation at all),
it may be relatively insensitive to the exact numbers of other agents playing particular
strategies. For example, let (
s, k
;
s
) denote a profile where
k
other agents play strategy
s
, and the rest play
s
. In many natural games, the payoff for the respective strategies
in this profile will vary smoothly with
k
, differing only incrementally for contexts with
k
1. If such is the case, we sacrifice relatively little fidelity by restricting attention to
subsets of profiles, for instance those with only even numbers of any particular strategy.
To do so essentially transforms the
N
-player game to an
N/
2-player game over the
same strategy set, where the payoffs to a profile in the reduced game are simply those
from the original game where each strategy in the reduced profile is played twice.
The potential savings from reduced games are considerable, as they contain combi-
natorially fewer profiles. The 4-player approximation to the TAC game (with 40 strate-
gies) comprises 123,410 distinct profiles, compared with 314 million for the original
8-player game. In case exhaustive consideration of the 4-player game is still infeasi-
ble, we can approximate further by a corresponding 2-player game, which has only 840
profiles. Approximating by a 1-player game is tantamount to ignoring strategic effects,
considering only the 40 profiles where the strategies are played against themselves.
±
In general, an
N
-player symmetric game with
S
strategies includes
N
+
S−
1
N
distinct
profiles. Figure 2 shows the exponential growth in both
N
and
S
.
4.2
Hierarchy of Reduced Games
We develop our hierarchical reduction concepts in the framework of
symmetric normal-
form games
.
