Information Technology Reference
In-Depth Information
3
Strategic Interactions in TAC Travel
TAC agents interact in the markets for each kind of good, as competing buyers or po-
tential trading partners. Based on published accounts, TAC participants design agents
given specified game rules, and then test these designs in the actual tournaments as well
as offline experiments. The testing process is crucial, given the lack of any compact an-
alytical model of the domain. During testing, agent designers explore variations on their
agent program, for example by tuning parameters or toggling specific agent features.
That strategic choices interact has been frequently noted in the TAC literature. A re-
port on the first TAC tournament [9] observes that the strategy of bidding high prices
for hotels performed reasonably in preliminary rounds, but poorly in the finals when
more agents were high bidders (thus raising final prices to unprofitable levels). Stone
et al. [10] evaluate their agent
ATTac-2000
in controlled post-tournament experiments,
measuring relative scores in a range of contexts, varying the number of other agents
playing high- and low-bidding strategies. A report on the 2001 competition [11] con-
cludes that the top scorer,
livingagents
, would perform quite poorly against copies of
itself. The designers of
SouthamptonTAC
[12] observed the sensitivity of their agent's
TAC-01 performance to the tendency of other agents to buy flights in advance, and
redesigned their agent for TAC-02 to attempt to classify the competitive environment
faced and adapt accordingly [13].
ATTac-2001
explicitly took into account the iden-
tity of other agents in training its price-prediction module [7]. To evaluate alternative
learning mechanisms through post-competition analysis, Stone et al. recognized the ef-
fect of the policies on the outcomes being learned, and thus adopted a carefully phased
experimental design in order to account for such effects.
One issue considered by several TAC teams is how to bid for hotels based on pre-
dicted prices and marginal utility. Greenwald and Boyan [3] have studied this in depth,
performing pairwise comparisons of four strategies, in profiles with four copies of each
agent.
3
Their results indicate that absolute performance of a strategy indeed depends
on what the other agent plays. We examined the efficacy of bid shading in
Walverine
,
varying the number of agents employing shading or not, and presented an equilibrium
shading probability based on these results [14].
By far the most extensive experimental TAC analysis reported to date is that per-
formed by Vetsikas and Selman [4]. In the process of designing
Whitebear
for TAC-
02, they first identified candidate policies for separate elements of the agent's overall
strategy. They then defined extreme (boundary) and intermediate values for these partial
strategies, and performed systematic experiments according to a deliberately considered
methodology. Specifically, for each run, they fix a particular number of agents playing
intermediate strategies, varying the mixture of boundary cases across the possible range.
In all, the
Whitebear
experiments comprised 4500 game instances, with varying
even
numbers of candidate strategies (i.e., profiles of the 4-player game). Their design was
further informed by 2000 games in the preliminary tournament rounds. This system-
atic exploration was apparently helpful, as
Whitebear
was the top scorer in the 2002
tournament. This agent's predecessor version placed third in TAC-01, following a less
3
In our terminology introduced below, their trials focused on the 2-player reduced version of
the game.
