The competition, held in conjunction with the International Conference on Multi-agent Systems, was sponsored by e-commerce heavyweights Andersen Consulting, Ariba and IBM. Professor Michael Wellman of the University of Michigan organized the competition to learn about how agents behave in competitive markets. Wellman's group designs market mechanisms; i.e., auction rules. To design better mechanisms they need to know how agents will use them. "We wanted to put a steak in the ground to define a benchmark problem," he said. And a challenging benchmark he picked.

Software agents (a.k.a. bots, short for ‘robots’) were tasked with purchasing airline tickets, hotel rooms and entertainment tickets for eight customers. Each customer has different preferences, so bots couldn't simply put together a single package and sell it to all eight customers. Each "game" in the competition was 15 minutes long and included eight bots competing head-to-head. To make things really difficult, different market mechanisms were used for each category of product. Airline tickets were sold at a fixed price, but the price fluctuated slightly every 30 seconds. At the beginning of each game, entertainment tickets were evenly distributed among the bots. During the game the bots could buy and sell the tickets in a continuous double auction (a.k.a. exchange), much the way stocks are traded on Wall Street. Lastly, hotel rooms were sold in blocks of 16 in an ascending price auction. That's the kind of auction used at estate sales and on eBay. The bots bid on blocks of one or more rooms, and the final price for all 16 rooms is the 16th highest bid. For example, if you bid $100 each for eight rooms and I bid $110 each for eight rooms, then we each get our eight rooms at $100 each. If somebody had bid $90 each for two rooms, then they wouldn't get any.

The bots had to put together itineraries for each customer, based on their preferences, and purchase products for that itinerary. The interdependencies between the products added to the challenge. For example, hotel reservations must correspond to the arrival and departure dates of the airline tickets. The bots were graded on how closely the itineraries purchased matched customers' preferences, and on the total cost of trips.

Twenty teams from six countries entered the competition. Universities, industrial research labs, government research labs, consulting firms and commercial companies were all represented. Preliminary rounds were held and the top eight teams were invited to Boston for the finals. After about ten games, the competition became a head-to-head battle between RoxyBot and ATTac.

RoxyBot was developed by Professor Amy Greenwald of Brown University and Dr. Justin Boyan of NASA Ames Research Center. During a game, RoxyBot continuously estimated the final prices of the products it wanted, estimated the value of the products for completing its itineraries, compared these to the current market prices, and bid accordingly. An interesting effect was that near the end of a game, when time was running out to get hotel rooms, RoxyBot would sometimes bid $1000 for a hotel room. This was because RoxyBot had already purchased airline tickets, and if it didn't get a hotel room then the trip would be canceled and it would lose the cost of the tickets. Thus it valued the hotel room at the cost of the airline tickets.

Developed 50 years ago to study nuclear war strategies, the Prisoner's Dilemma examines the tradeoffs between personal utility and group utility. The dilemma goes as follows. You and Albert are arrested for a crime and taken to separate rooms for interrogation. If you both confess then you'll both get 4-year sentences. If neither confesses then you'll both get 2-year sentences due to a lack of evidence. But if only one confesses then the confessor will go free and the other will get 5 years. Your best strategy is to confess, regardless of what Albert does. If he confesses then you're better off confessing and taking the 2 years. If he doesn't confess then you're better off confessing because you'll go free. The problem is that Albert also understands this, so you both confess and get 4 years each. If you both remained silent then you would have only received 2 years each. In this dilemma, pursuing personal good leads to a worse situation for the group as a whole.

A similar dilemma arose in the trading competition while bidding for hotel rooms. If all bots bid their actual utility for a hotel room—say $1000—then the final price would be very high. But if only a few bots bid their actual utility, then the final price would be the 16th highest price, which would be much lower. ATTac avoided expensive hotel rooms by calculating the average price a room sold for in previous games, and then not bidding on high-priced rooms regardless of their current price in the current game.

At the end of the day, ATTac edged out RoxyBot 3398 points to 3283. The RoxyBot team was quick to point out that that point spread was not statistically significant, while the ATTac team was quick to point out that they won. Both teams learned a lot. Professor Greenwald called it, "some of the most fun I've ever had," and is looking forward to a rematch next year.

The competition will likely be even more complex next year. To stay ahead of rapid e-commerce uptake, researchers must continuously raise the bar. In fact, by next year RoxyBot and ATTac might be buying tickets for real. "I wouldn't be surprised if we see something like this within a year," concluded Dr. Stone.

--- the end ---

Contact info: