Bidding Algorithms for Simultaneous Auctions:A Case StudyAmy GreenwaldDepartment of Computer ScienceBrown University, Box 1910Providence, RI [email protected] BoyanITA SoftwareCambridge, MA [email protected] 10, 2002AbstractThis paper describes RoxyBot, one of the top-scoring agents in the First International TradingAgent Competition, TAC-2000. A TAC agent simulates one vision of future travel agents: itrepresents a set of clients in simultaneous auctions, trading complementary (e.g., airline ticketsand hotel reservations) and substitutable (e.g., symphony and theater tickets) goods. RoxyBotfaced two key technical challenges in TAC: (i) allocation—assigning purchased goods to clientsat 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 theallocation problem is tractable, and RoxyBot uses a search algorithm based on A∗to produceoptimal allocations. An optimal solution to the completion problem is also tractable, but inthe interest of minimizing bidding cycle time, RoxyBot solves the completion problem usingbeam search with a greedy heuristic, producing approximately optimal completions. RoxyBot’scompleter relies on an innovative data structure called a priceline.11 IntroductionThe first international Trading Agent Competition (TAC-2000) challenged its entrants to design anautomated trading agent capable of bidding in simultaneous on-line auctions for complementary andsubstitutable goods [15]. A TAC-2000 agent is a simulated travel agent whose task is to organizeitineraries for a group of clients who wish to travel from TACTown to Boston and back againduring a five-day period in July.1Travel goods, such as airline tickets and hotel reservations, arecomplementary, and tickets to entertainment events, such as the Boston Red Sox and the BostonSymphony Orchestra, are substitutable. The trading agent’s objective is to win items that bestsatisfy its clients’ preferences as inexpensively as possible.In this paper, we introduce RoxyBot, one of the top-scoring TAC-2000 agents. The name RoxyBotis short for “ApproximateBot,” which suggests our goal of constructing a trading agent whose biddingdecisions approximate optimal behavior. RoxyBot faced two key technical challenges in TAC-2000:(i) allocation—assigning purchased goods to clients at the end of a game instance so as to maximizetotal client utility, and (ii) completion—determining the optimal quantity of each resource to buyand sell given client preferences, current holdings, and market prices. The allocation problem is aform of the winner determination problem, in which an auctioneer seeks to allocate goods to bidderswith combinatorial valuations so as to maximize his revenue, and completion can be reduced towinner determination with reserve prices.For the dimensions of TAC-2000, an optimal solution to the allocation problem is tractable,and RoxyBot uses a search algorithm based on A∗to produce optimal allocations. One of theprimary foci of this paper is the design RoxyBot’s admissible heuristics. An optimal solution to thecompletion problem is also tractable, but was observed to run for as long as 10 seconds on difficultproblem instances. In the interest of minimizing bidding cycle time, RoxyBot solves the completionproblem using beam search with a greedy heuristic, producing approximately optimal completions.The completion algorithm relies on an innovative data structure called a priceline, that reducescompletion to acquisition—the problem of determining the optimal quantity of each resource to buy,not sell, given client preferences, current holdings, and market prices.This paper is organized as follows. In the following section, we motivate our approach to thedesign of bidding agent algorithms, and describe RoxyBot’s high-level architecture. In Section 3, wedescribe the TAC-2000 market game, and present examples of allocation and completion. Section 4presents our allocation algorithm. This algorithm is based on A∗search, and this discussion is there-fore dedicated to the description of our admissible heuristics. Section 5 describes our approach tocompletion. Special emphasis is placed on the priceline, a novel data structure which transparentlyhandles either one-sided or double-sided auctions, short-selling of resources, hedging, and both lim-ited and unlimited supply and demand. In Section 6, we describe estimation techniques for building1The TAC-2000 workshop was held at ICMAS ’00 in Boston in July, 2000.2pricelines. In Section 7, we present the results of the competition. Lastly, in Section 8, we discussthe general applicability of this work.2 RoxyBot’s ArchitectureThe primary challenge in TAC-2000 is to bidding agents is to determine how to bid on complementaryand substitutable goods that are sold in simultaneous, not combinatorial, auctions. Complementarygoods are goods with superadditive utilities: i.e., u(AB)+u(AB) ≤ u(AB). In TAC-2000, the utilityof airline tickets without hotel reservations (or of hotel reservations without airline tickets) is zero,whereas the utility of complete travel packages is strictly positive. Substitutable goods are goodswith subadditive utilities: u(AB) + u(AB) ≥ u(AB). In TAC-2000, the utility of both a theaterticket and a symphony ticket for the same night is bounded above by the higher of the individualutilities attributed to the two separate events. It does not make sense to assign individual utilitiesto complementary goods (which can be worthless in isolation) or substitutable goods (which can beworthwhile only in isolation). Thus, simple bidding strategies such as “for each good x, bid up toits utility” are not applicable in the TAC-2000 setup.Instead, RoxyBot was built to reason directly about sets of goods—the utilities of which arewell-defined. RoxyBot poses and solves questions such as:2• “Given only the set of goods I already hold, what is the maximum utility I can attain?”Inspired by TAC-2000, we call this problem allocation, since in the case of an agent biddingon behalf of multiple clients, the solution is an optimal allocation of goods to clients.• “Given the set of goods I already hold, and given market prices, supply, and demand, on whatset of additional goods should I place bids or asks so as to