Information Technology Reference
In-Depth Information
Searching for Walverine 2005
Michael P. Wellman, Daniel M. Reeves, Kevin M. Lochner, and Rahul Suri
University of Michigan
Ann Arbor, MI 48109-2110 USA
{ wellman, dreeves, klochner, rsuri } @umich.edu
Abstract. We systematically explore a range of variations of our TAC travel-
shopping agent, Walverine . The space of strategies is defined by settings to be-
havioral parameter values. Our empirical game-theoretic analysis is facilitated
by approximating games through hierarchical reduction methods. This approach
generated a small set of candidates for the version to run in the TAC-05 tour-
nament. We selected among these based on performance in preliminary rounds,
ultimately identifying a successful strategy for Walverine 2005.
1
Introduction
There are many ways to play the TAC travel-shopping game. Our agent, Walverine [1],
employs competitive analysis to predict hotel prices and formulate an optimal bidding
problem. Other agents take different approaches to predicting hotel prices [2], bidding
under uncertainty [3], and many other facets of TAC. Even within a particular approach
to a particular subproblem, there is no end to possible variations one might consider,
ranging from fine-tuning of policy parameters to qualitatively different strategies.
Like most TAC participants, we apply a mix of modeling and experimentation in de-
veloping our agent. Since our models of the TAC environment necessarily simplify the
actual game, we rely on experimental offline trials to validate the ideas and set param-
eters. And since these offline experiments incorporate assumptions about other agents'
behavior, we also depend on online experiments (e.g., during preliminary tournament
rounds) to test our designs in the most realistic setting available. Also like most other
participants (with the notable exception of Whitebear [4], discussed below), our com-
bination of modeling and experimentation was essentially ad hoc , with only informal
procedures for fixing a particular agent behavior based on the results.
For 2005 (following a preliminary effort for 2004), we decided to adopt a more
systematic approach. The first element of our method is fairly standard: define a space of
strategies to consider by parametrizing the baseline agent Walverine . We then explore
the space through extensive simulation. A less conventional element of our method
is that we use the simulation results to estimate an empirical game , and apply standard
game-theoretic analysis to derive strategic equilibria. The particularly novel element we
introduce in the current work is hierarchical game reduction , a general technique for
approximating symmetric games by smaller games with fractional numbers of agents.
In this instance, we show that 4-player and 2-player reductions of the TAC game are far
more manageable than the full 8-player game, and argue that little fidelity is lost by the
reduction proposed here.
Search WWH ::




Custom Search