Bidding Algorithms for Simultaneous Auctions: A Case Study
Amy Greenwald and Justin Boyan
Abstract
This paper introduces RoxyBot, one of the top-scoring agents in the
First International Trading Agent Competition. 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:
(i) allocation---assigning purchased goods to clients at the end of a
game instance so as to maximize total client utility, and (ii)
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.