Walverine 2004

The agent Walverine that participated in the 2004 TAC Classic tournament is an incremental revision of the agent by the same name that played in TAC-03, which in turn is an incremental version of the Walverine from TAC-02. Walverine 2002 is thoroughly described in an article appearing in Decision Support Systems. The incremental changes for 2003 are described elsewhere on this site. Here we describe the changes instituted for 2004.

Flight purchasing. The major change in 2004 was a modification of the flight pricing model, and a reduction in time to the initial hotel closing. Walverine 2004 instituted a more elaborate flight purchase decision module, based on continual estimation of the flight pricing model.
- Flight price estimation. For each flight, there is a hidden value x dictating the probability of price perturbations as a function of t. Walverine maintains a probability distribution over x, starting with a uniform prior, and performing a Bayesian update based on the observed price change every 10 seconds. Let E[D] denote the expected value of the next price perturbation for the flight in question.
- For each flight we are considering purchasing (i.e., it is part of our current optimal package), we compare E[D] to a lower threshold t1, and an upper threshold t2. If E[D] < t1 we DELAY the flight purchase, and if E[D] > t2 we BUY right away. Otherwise, for each trip with indeterminate flights, if the associated trip is shortenable (i.e., greater than one day), we proceed further. If the number of clients staying on the day of the inflight exceeds another threshold, t3, we mark the inflight as delayable. If not, but there are at least t3 clients staying the day before the outflight, we mark the outflight as delayable. Finally, among those marked as delayable, we unmark one of each flight (day/direction) if its assessed surplus is greater than yet another threshold, t4. We then go ahead and buy any of the candidate flights not marked as delayable.
- For Walverine-04, t1 = 0.25, t2 = 1.0, t3 = 3, and t4 = 200.
Hotel bid shading. Walverine determines an "optimal" bid shading based on a decision-theoretic calculation involving its own marginal values and a model of other agents' bids. In 2002, Walverine bid these shaded values in every game. In 2003, Walverine employed bid shading in a game with probability 0.11, and chose to bid unshaded marginal values with probability 0.89. In 2004, we reverted to the 2002 policy of shading every game.

Walverine Team, representing the University of Michigan AI Laboratory