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.

Therefore, ATTac-2000 aims to delay most of its purchases, and particularly its airline purchases, until late in the game. ATTac-2000's high-level bidding strategy is based on the premise that it is best to delay ``committing'' to the current G^* for as long as possible. Although it continually reevaluates G^*, and is therefore never technically committed to anything, the markets are such that it is rarely advantageous to change a client's travel package if it would mean wasting an airline ticket or an expensive hotel room (thus requiring additional ones to be purchased).

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_branged 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 $T_l \leq 2 \times T_b$, 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.