Allocation Strategy

As is evident from Section 3.1, *ATTac-2000* relies
heavily on computing the current most profitable allocation of goods
to clients, *G*^{*}. Since *G*^{*} changes as prices
change, *ATTac-2000* needs to recompute it at every bidding opportunity.
By using an integer linear programming approach, *ATTac-2000* was able
to compute optimal final allocations in every game instance during the
tournament finals--one of only 2 entrants to do so.^{2}

Most TAC participants used some form of greedy strategy for
allocation [Greenwald StoneGreenwald Stone2001]. It is computationally feasible to quickly
determine the maximum utility achievable by client 1 given a set of
purchased goods, move on to client 2 with the remaining goods, etc.
However, the greedy strategy can lead to suboptimal solutions. For
example, consider 2 clients *A* and *B* with identical travel days
*IAD* and *IDD* as well as identical entertainment values *EV*, but
with *A*'s
and *B*'s
.
If the agent has
exactly one of each type of hotel room for each day, the optimal
assignment is clearly to assign the BGH to client *B*. However, if
client *A*'s utility is optimized first, it will be assigned the BGH,
leaving *B* to stay in LFI. The agent's resulting score would be
100 less than it could have been.

As an improvement over the basic greedy strategy, we implemented a heuristic approach that implements the greedy strategy over 100 random client orderings and chooses the most profitable resulting allocation. Empirically, the resulting allocation is often optimal, and never far from optimal. In addition, it is always very quick to compute. In a set of seven games from just before the tournament, the greedy allocator was run approximately 600 times and produced allocations that averaged 99.5% of the optimal value.

As the competition drew near, however, it became clear that every
point would count. We therefore implemented an allocation strategy
that is guaranteed to find the optimal allocation of
goods.^{3} The integer linear
programming approach
used by *ATTac-2000* works by defining a set of variables, constraints
on these variables, and an objective function. An assignment to the
variables represents an allocation to the clients and the
constraints ensure that the allocation is legal. The objective
function encodes the fact that we seek the allocation with maximum
value (utility minus cost).

The following notation is needed to describe the integer linear
program. The formal notation is included for completeness; an
equivalent English description follows each equation. The symbol *c*is a client (1 through 8). The symbol *f* is a feasible travel
package, which consists of: the arrival day *AD*(*f*) (1 through 4); the
departure day *DD*(*f*) (2 through 5), and the choice of hotel *H*(*f*)(BGH or LFI). There are 20 such travel packages. Symbol *e* is an
entertainment ticket, which consists of: the day of the event *D*(*e*)(1 through 4), and the type of the event *T*(*e*) (baseball *b*,
symphony *s*, or theater *t*). There are 12 different entertainment
tickets. Symbol *r* is a resource (*AD*, *DD*, BGH, or LFI).

Using this notation, the 272 variables are: *P*(*c*,*f*), which indicates
whether client *c* will be allocated feasible travel package *f* (160
variables); *E*(*c*,*e*), which indicates whether client *c* will be
allocated entertainment ticket *e* (96 variables); and, *B*_{r}(*d*) is
the number of copies of resource *r* we would like to buy for day *d*(16 variables).

There are also several constants that define the problem: *o*_{r}(*d*) is
the number of tickets of resource *r* currently owned for day *d*,
*p*_{r}(*d*) is the current price for resource *r* on day *d*, *u*_{P}(*c*,*f*)is utility to customer *c* for travel package *f*, and *u*_{E}(*c*,*e*) is
the utility to customer *c* for entertainment ticket *e*.

Given this notation, the objective is to maximize utility minus cost

subject to the following 188 constraints:

- For all
*c*, : No client gets more than one travel package (8 constraints). - For all
,

For all and ,

For all ,

The demand for resources from the selected travel packages must not exceed the sum of the owned and bought resources (16 constraints). - For all
*e*, : The total quantity of each entertainment ticket allocated does not exceed what is owned (12 constraints). - For all
*c*and*e*, : An entertainment ticket can only be used if its day is between the arrival and departure day of the selected travel package (96 constraints). - For all
*c*and , : Each client can only use one entertainment ticket per day (32 constraints). - For all
*c*and , : Each client can only use each type of entertainment ticket once (24 constraints). - All variables are integers.

The solution to the resulting integer linear program is a
value-maximizing allocation of owned resources to customers along with
a list of resources that need to be purchased. Using the linear
programming package ``LPsolve'', *ATTac-2000* is usually able to find the
globally optimal solution in under one second on a 650 MHz Pentium II.

Note that this is not by any means the only possible formulation of the allocation. boyan01 boyan01 studied a variant and found that it performed extremely well on a collection of large, random allocation problems.

The above approach is guaranteed to find the optimal allocation, and
usually does so quickly. However, since integer linear programming is
an NP-complete problem, some inputs can lead to significantly longer
solution times. In a sample of 32 games taken shortly before the
finals, the allocator was called 1866 times. In 93% of the cases,
the optimization took a second or less. Less than 1% took 6 or more
seconds. However, the 3 longest running times were all over a minute
and all came from the same game. *ATTac-2000* used the strategy that if an
integer linear program takes 6 or more seconds to solve, the
above-mentioned greedy strategy over random client orderings is used as
a fall-back strategy for the rest of the game. This fall-back
strategy was not needed during the tournament finals.