Bidding Strategy

TAC was defined so as to be simple enough to have a low barrier to
entry, yet complex enough to prevent tractable solution via direct
game-theoretic analysis. Given that an optimal solution is not
attainable, we use a principled approach that takes advantage of
details of the TAC scenario. In general, *ATTac-2000* aims to be robust to
the parameter space defined by TAC as well as to conceivable opponent
strategies.

At every bidding opportunity, *ATTac-2000* begins by computing the most
profitable allocation of goods to clients (which we shall denote
*G*^{*}), given the goods that are currently owned and the current
prices of hotels and flights. (See
Section 3.3 for a caveat.) For the purposes
of this computation, *ATTac-2000* allocates, but does not consider buying
or selling, entertainment tickets. In most cases, *G*^{*} is
computed using integer linear programming, as described in
Section 3.2.

*ATTac-2000*'s high-level bidding strategy is based on the following two
observations:

- 1.
- Since airline prices periodically increase or decrease with
equal probability, the
*expected*change in price for each airline auction is $0. Indeed, it can be shown that if the airline auction is considered in isolation, waiting until the very end of the game to purchase tickets is an optimal strategy (except in the rare case that the price reaches the lowest allowed value). - 2.
- Since hotel prices are monotonically increasing, as the game proceeds, the hotel prices approach the eventual closing prices.

*ATTac-2000* accomplishes this delay of commitment by bidding in two
different modes: *passive* and *active*. The *passive*
mode, which lasts most of the game, is designed to keep as many
options open as possible. During the passive mode, *ATTac-2000* computes
the average time it takes for it to compute and place its bids, *T*_{b}(*T*_{b} is the average time it takes to go through one iteration of the
loop in step 1 of Table 3). We found that *T*_{b}ranged from 10 seconds to well over a minute, and was primarily
dependent upon the server's load. Call the time left in the game
*T*_{l}. When
,
*ATTac-2000* switches to its
*active* mode, during which it buys the airline tickets required
by the current *G*^{*} and places high bids for the required hotel
rooms. Note that *ATTac-2000* expects to run at most 2 bidding iterations
in active mode. In fact, only 1 such iteration is necessary, but
there is a huge cost to failing to complete the iteration before the
end of the game. Planning for 2 active iterations leaves room for
some error.

Based on the current *G*^{*}, its current mode, and *T*_{l}, *ATTac-2000* bids for flights, hotel rooms, and entertainment tickets.