Information Technology Reference
In-Depth Information
near neighbors in the reduced game that are close to equilibrium there. Elsewhere we
provide evidence that the hierarchical reduction provides an effective approximation in
several natural game classes [5]. Intuition suggests that it should apply for TAC, and the
basic agreement between TAC
↓
2
and TAC
↓
4
seen in our results tends to support that
assessment.
5
TAC Experiments
To apply reduced-game analysis to the TAC domain, we identified a restricted set of
strategies, defined by setting parameters for
Walverine
. We considered a total of 40
distinct strategies, covering variant policies for bidding on flights, hotels, and entertain-
ment. We collected data for a large number of games: over 47,000 as of the start of
the TAC-05 finals, representing over one year of (almost continuous) simulation.
4
Each
game instance provides a sample payoff vector for a profile over our restricted strategy
set.
Table 1 shows how our dataset is apportioned among the 1-, 2-, and 4-player reduced
games. We are able to exhaustively cover the 1-player game, of course. We could also
have exhausted the 2-player profiles, but chose to skip some of the less promising ones
(around one-quarter) in favor of devoting more samples elsewhere. The available num-
ber of samples could not cover the 4-player games, but as we see below, even 1.7% is
sufficient to draw conclusions about the possible equilibria of the game. Spread over
the 8-player game, however, 47,000 instances would be insufficient to explore much,
and so we refrain from any sampling of the unreduced game.
Ta b l e 1 .
Profiles evaluated, reduced TAC games (TAC
↓
p
)
p
Profiles
Samples/Profile
total evaluated
% min
mean
4 123,410
2114
1.7 12
22.3
2
840
586
71.5 15
31.7
1
40
40 100.0
25
86.5
In the spirit of hierarchical exploration, we sample more instances per profile as the
game is further reduced, obtaining more reliable statistical estimates of the coarse back-
bone relative to its refinement. On introducing a new profile we generate a minimum
required number of samples, and subsequently devote further samples to particular pro-
files based on their potential for influencing our game-theoretic analysis. The sampling
policy employed was semi-manual and somewhat
ad hoc
, driven in an informal way by
4
Our simulation testbed comprises two dedicated workstations to run the agents, another RAM-
laden four-CPU machine to run the agents' optimization processes, a share of a fourth machine
to run the TAC game server, and background processes on other machines to control the ex-
periment generation and data gathering. We have continued to run the testbed since the tourna-
ment, accumulating over 56,000 games as of this writing. Results presented here correspond
to a snapshot at the end of July 2005, right before the final tournament.
