Bidding Algorithms for Simultaneous Auctions: A Case Study

摘要

This paper describes RoxyBot, one of the top-scoring agents in the First International Trading Agent Competition, TAC-2000. A TAC agent simulates one vision of future travel agents: it represents a set of clients in simultaneous auctions, trading complementary (e.g., airline tickets and hotel reservations) and substitutable (e.g., symphony and theater tickets) goods. RoxyBot faced two key technical challenges in TAC: (ⅰ) allocation — assigning purchased goods to clients at the end of a game instance so as to maximize total client utility, and (ⅱ) completion — determining the optimal quantity of each resource to buy and sell given client preferences, current holdings, and market prices. For the dimensions of TAC, an optimal solution to the allocation problem is tractable, and RoxyBot uses a search algorithm based on A~* to produce optimal allocations. An optimal solution to the completion problem is also tractable, but in the interest of minimizing bidding cycle time, RoxyBot solves the completion problem using beam search with a greedy heuristic, producing approximately optimal completions. RoxyBot's completer relies on an innovative data structure called a priceline.