next up previous
Next: Results Up: Adaptivity Previous: Allocation

Hotel Bidding

Perhaps most significantly, ATTac-2000 predicts the closing prices of hotel auctions based on their closing prices in previous games. Hotel bidding in TAC was particularly challenging due to the extreme volatility of prices near the end of the game. As stated in Section 3.1.2, at the end of the game ATTac-2000 bids the marginal utility for each desired hotel room, which was often in excess of $1000.

During the preliminary competition, few agents bid their marginal utilities on hotel rooms. Those that did, however, generally dominated their competitors; such agents were high-bidders, bidding $\sim \$1000$, always winning the hotels on which they bid, but paying far less than their bids. Having observed a dominant strategy during the preliminary rounds, most agents, including ATTac-2000, adopted this high-bidding strategy during the actual competition. The result was many negative scores, as prices skyrocketed in the last moments of the game once there were 16 high bids for a given room.

In Section 3.1, we stated that ATTac-2000 computes G* based on the current prices of the hotel rooms. Should the prices eventually become very high, ATTac-2000 would either end up paying too high a price for the hotel rooms or else fail to get travel packages for some of its clients. The only alternative was to avoid counting on obtaining contentious hotel rooms.

Since strategies were changing up to the last minute before the finals, there was no way to identify a priori which hotels would be most contentious or whether hotel prices would actually skyrocket in the tournament. Therefore, ATTac-2000 divided the 8 hotel rooms into 4 equivalence classes, exploiting symmetries in the game (hotel rooms on days 1 and 4 should be equally in demand as should rooms on days 2 and 3), assigned priors to the expected closing prices of these rooms, and then adjusted these priors based on the observed closing prices during the tournament.

As expected, the Grand Hotel on days 2 and 3 turned out to be most contentious during the finals. Le Fleabag Inn on the same days was also fairly contentious. Whenever the actual price for a hotel was less than the predicted closing price, ATTac-2000 used the predicted hotel closing price for computing all of its allocation values.

One additional method for predicting whether hotel prices would skyrocket in a given game is to notice who the participants are and whether or not they tended to be high-bidders in past games (see Figure 2). Although such information was not available via the server's API, a game's participants were always published beforehand on the TAC web page. By automatically downloading this information from the web (a practice whose ethicality was questioned at the competition), and matching against a precompiled database of which agents were high-bidders in the past, ATTac-2000 would only use the predicted hotel closing prices in games with 3 or more high-bidders involved: in games with fewer high-bidders, the prices of hotel rooms almost never skyrocketed4. As it turned out, all but one of ATTac-2000's games in the semi-finals, and all games in the finals, involved several high-bidders, thus triggering the use of predicted hotel closing prices.

Figure 2: Graphs of two different agents' bidding patterns over many games. Each line represents one game's worth of bidding in a single auction. Left: RiskPro never bids over $250 in the games plotted. Right: Aster consistently bids over $1000 for rooms.

Empirical testing (Section 4) indicates that this strategy is extremely beneficial in situations in which hotel prices do indeed escalate, while it does not lead to significantly degraded performance when they do not.

next up previous
Next: Results Up: Adaptivity Previous: Allocation
Peter Stone