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:
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, Tb(Tb is the average time it takes to go through one iteration of the loop in step 1 of Table 3). We found that Tbranged from 10 seconds to well over a minute, and was primarily dependent upon the server's load. Call the time left in the game Tl. 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 Tl, ATTac-2000 bids for flights, hotel rooms, and entertainment tickets.