over all clients ie the greatest possible value of given the client profiles owned for unallocated sell value" in Figure ATTac-2000 offers to sell for max where   increases linearly from   to Once again ATTac-2000 raises its price based on to meet an existing bid price that is greater than its target price This strategy reflects the increasing likelihood as the game progresses that * will be close to the final client allocation  and thus that any currently unused tickets will not be needed in the end  When in active mode ATTac-2000 assumes that * is final and offers to sell any unneeded tickets for $ in order to obtain at least some value for them represented by the discrete point at the bottom right in Figure      Below $    ATTac-2000 would rather waste the ticket than allow a competitor to make a large profit The Finally ATTac-2000 bids to buy each type of entertainment ticket including those that it is also offering to sell  based on the increased value that would be derived by owning
* be the optimal allocation that would result were - owned - buy value" in Let Note that * r could have different flight and hotel assignments than * so as to Figure make most effective use of     Then  ATTac-2000 offers to buy for where decreases linearly from based on to All of the parameters described in this section were chosen arbitrarily without detailed experimentation Again our intuition is that unless opponents know and explicitly exploit these values ATTac-200 s performance is not very sensitive to them

## 3.2 Allocation Strategy

ATTac-200 relies heavily on computing the current most As As is evident from Section profitable allocation of goods to clients * Since * changes as prices change ATTac-2000 nnow 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 entrants to do so 2 Most TAC participants used some form of greedy strategy for allocation  Greenwald It is computationally feasible to quickly determine the maximum utility Stone achievable by client given a set of purchased goods move on to client with the remaining goods etc However the greedy strategy can lead to suboptimal solutions  For example consider   clients   and   with identical travel days IAD and IDD as well as identical entertainment values e s e 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 t However if client s utility is optimized first it will be assigned the BGH leaving   to stay in LFI The agent s resulting score would be 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     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 ust before the tournament the greedy allocator was run approximately to times and produced allocations that averaged of the optimal value