Back to November 2002 CRN Table of Contents

[Published originally in the November 2002 edition of Computing Research News, Vol. 14/No. 5, pp. 3, 10.]

By Amy Greenwald

Amy Greenwald, Brown University, is the fifth CRA Digital Government Fellow. The following article is a synopsis of her presentation to the Auctions Division at the Federal Communications Commission on May 7, 2002.

Suppose you want to buy a used Canon AE-1 SLR camera at an online auction. It would be quite a daunting task to manually monitor prices and make bidding decisions at all web sites currently offering the camera--especially if accessories like a flash and tripod are sometimes bundled with the camera, and sometimes auctioned separately. But for the next generation of automated trading agents this will be a routine task.

Simultaneous auctions, which arise naturally on Internet sites such as eBay.com and amazon.com, are a challenge to bidders, particularly when complementary and substitutable goods are on offer. Complementary goods are items such as a flash, a tripod, and a case that would complement a camera--but a bidder desires any of the former only if s/he is certain to acquire the latter. Substitutable goods are goods such as the Canon AE-1 and the Canon A-1--a bidder desires one or the other, but not both. In combinatorial auctions, bidders bid on combinations of items, such as "camera and flash for $295''; in these auctions, the (NP-complete) problem of determining how to allocate goods so as to maximize revenue falls in the hands of the auctioneer. In simultaneous auctions, however, the complexity burden lies with the bidders.

The international trading agent competition (TAC) challenges its entrants to design online agents capable of bidding in simultaneous auctions for substitutable and complementary goods. TAC was conceived of by Mike Wellman and the AI laboratory at the University of Michigan. This year, for the third rendition of the competition, the TAC software platform was redesigned by the Intelligent Systems Laboratory at the Swedish Institute of Computer Science, led by Erik Aurell.

Rules

The TAC competition (http://www.sics.se/tac and http://tac.eecs.umich.edu) consists of a series of game instances, each of which pits eight autonomous bidding agents against one another. Each TAC agent simulates a travel agent with eight clients who were interested in traveling from TACtown to Boston and home again during a five-day period. Each client is characterized by a random set of preferences for the possible arrival and departure dates, hotel rooms (The Grand Hotel and Le Fleabag Inn), and entertainment tickets (symphony, theater, and baseball). A TAC agent's score in a game instance is the difference between the total utility it obtains for its clients, based on its clients' preferences, and the agent's expenditures. To minimize the effects of randomization, agents' scores are averaged across several game instances during TAC competitions.

In order to obtain utility for a client, an agent constructs a complete travel package for that client by purchasing airline tickets to and from TACtown and securing hotel reservations. It is also possible to obtain additional utility by supplementing a travel package with tickets to entertainment events. Each item is sold separately at auction: in total there are 28 goods and 28 simultaneous auctions. Airline ticket prices follow a biased random-walk--prices are more likely to increase than decrease. Hotel room reservations are sold in ascending 'English' auctions (auctions like those for antiques and art). These auctions clear one per minute, in an unspecified random order. Entertainment tickets are traded in continuous 'double' auctions (auctions like those on the New York Stock Exchange).

Decision-Making

During a TAC game, agents are continuously faced with three basic decisions: what goods to bid on, how many to bid for, and what price to bid at. These bidding decisions are complicated by the tradeoffs that result from complementary and substitutable goods. For example, a flight to Boston complements a flight back to TACtown, but a one-way ticket is of no utility. Similarly, an entertainment ticket for a given night would complement a travel package that included that night, such as a flight arriving that day, a hotel room for that night, and a flight departing the next day--but the entertainment ticket is of value only if the complete travel package is obtained. Moreover, multiple entertainment tickets on a given night are substitutable (a single client can go to at most one of symphony, theater, and baseball); thus, an agent has to trade off among its clients' preferences for the various types of entertainment tickets and the price differentials of the tickets. Similarly, the good and bad hotel rooms are substitutable: an agent has to trade off between its clients' preferences for the good hotel and the price differentials between the two hotels.

In competing TAC-agent designs, one strategic dichotomy is seen in the use of greedy vs. optimal decision-making algorithms. Greedy solutions are fast and easy to implement, but are suboptimal in general. Optimal solutions, on the other hand, repeatedly solve NP-complete problems in real-time. For example, while some agents focus on obtaining complete packages, others make bidding decisions on travel packages alone (i.e., flights and hotel rooms) without regard for entertainment tickets, essentially breaking the TAC problem down into two sub-problems. But it is preferable to extend a client's stay whenever the utility obtained by assigning that client an additional entertainment ticket exceeds the cost of the ticket and an additional hotel room (plus any travel penalties incurred). Similarly, it is sometimes preferable to sell entertainment tickets and shorten a client's stay accordingly. A second example of this strategic dichotomy is seen in the fact that some agents aim to satisfy each of their clients in turn (greedy), whereas others make global decisions regarding all their clients' interests simultaneously (optimal).

RoxyBot

"Roxybot" is short for "ApproximateBot," a name that represents the goal of constructing a trading agent whose strategic behavior approximates optimal behavior. Using AI heuristic search techniques, Roxybot incorporates an optimal solver for the problem of completion--determining the optimal quantity of each item to buy and sell given current holdings and estimates of auction clearing prices.

At the heart of Roxybot is an algorithm that generates TAC bidding policies consisting of: 1) a set of goods A on which to bid, or ask; and 2) a set of prices, one price corresponding to each good in the set A. During each bidding cycle, Roxybot-00 (see Table 1) pings the server for updated information; estimates auction clearing prices; solves the completion problem (to generate part 1 of a TAC bidding policy), and computes marginal utilities (to generate part 2 of a TAC bidding policy). (The marginal utility of good x is defined as the utility of all goods, including good x, less the utility of all goods, excluding good x.)

Roxybot-01 (see Table 2) generalizes Roxybot-00 by computing policies not simply from price point estimates, but rather from estimated price distributions. Roxybot-01 determines a set of goods that is likely to be of value under many samples of its estimated price distributions. (This algorithm proceeds by determining an initial set of goods that is desired under many samples, adding that set to the set of current goods, and repeating. A larger and larger set of goods is built up by conditioning on those goods that were desired in earlier iterations.) Bid and ask prices are computed by averaging marginal utilities across many samples of the estimated price distributions.

Roxybot-02 (see Table 3), an agent based on Monte Carlo simulations, generalizes both earlier versions of Roxybot. Specifically, this agent: 1) generates candidate bidding policies a la Roxybot-01, using estimated price distributions, or Roxybot-00, obtaining a set of price point estimates by sampling from estimated price distributions; and 2) evaluates each candidate by averaging its score across many samples of estimated price distributions. This search through the space of bidding policies continues until time expires, at which point Roxybot-02 bids according to the best bidding policy. Roxybot-02 generalizes and outperforms both Roxybot-01 and Roxybot-00.

The trading agent competition is an exciting domain in which to study artificial intelligence (AI) techniques. Some TAC agent designs are based on straightforward applications of AI: for example, at the heart of \roxybot-00 is a beam search optimization routine. Other TAC agent
designs extend state-of-the art techniques in AI: \roxybot-01 and \roxybot-02 both offer solutions to a generalized search problem that is relevant to decision making under uncertainty.

The Future of TAC

The travel domain has been the focus of the trading agent competition for three years running. At TAC-2003, this game will take a back seat, and a new game based on supply chain management will be introduced. In next year's competition, each TAC agent will act as a PC assembler, buying computer parts piecemeal from suppliers, and compiling its inventory into custom-specific products for its clients. This game is being designed by Norman Sadeh and Raghu Arunachalam at Carnegie Mellon's eCommerce Institute, in conjunction with the SICS development team. Game details will be announced in mid-October.

Amy Greenwald is an Assistant Professor in the Department of Computer Science at Brown University. Email: amygreen@cs.brown.edu; URL: http://www.cs.brown.edu/~amygreen/

The CRA Digital Government Fellowship is supported by the National Science Foundation's Digital Government Program, and is intended to build ties between academic and industrial computing research communities, as well as among information technology workers in federal, state, and local governments.