Dr. Dobb's Journal May 2001
Online trading, specifically in support of online auctions, is an important topic in the artificial intelligence (AI) and e-commerce research communities, as well as for the general public. Public auction sites such as eBay and Yahoo! list millions of items for sale, and attract a multitude of users. Currently, these auction sites require human interaction for participation in auctions, almost always through web interfaces. Users manually select items (goods) they wish to purchase, submit bids, and monitor the status of the auctions. Some sites support more advanced automation and monitoring tools, but these provide limited functionality and still require human interaction to make strategic decisions and communicate these to the auction site.
In the near future, however, this landscape will change dramatically. The next generation trading market infrastructures will add automated negotiation facilities, allowing humans to be represented by software agents. To illustrate, a simplified version of this scenario is as follows: Say a person has decided to purchase a new DVD player. He communicates his preferences (model, price, features, location of purchase, and the like) to a software agent that negotiates for the item on behalf of the person. As you can imagine, the interaction of these preferences can be complex, requiring advanced knowledge to be designed into the agent. The agent combs online auction sites looking for a DVD player that meets the person's preferences and bids on the available players, making all strategic judgments until a deal is reached. Once the agent has negotiated the deal, it informs the person what it bought, or possibly presents him with a list of DVD players and lets him choose between any of several models. In some cases, it can even arrange for payment and delivery of the purchase. For our purposes, the main shift taking place is that the entire negotiation process occurs without human interaction.
Our group at the University of Michigan Artificial Intelligence Laboratory organized a Trading Agent Competition (TAC) market game as part of last year's Fourth International Conference on Multiagent Systems (ICMAS-00). The competition was held at the conference in conjunction with a workshop devoted to that purpose. TAC pitted software agents from six countries and 18 affiliations against each other in a market game embodying the agent negotiation elements of the example just described. Throughout TAC, participants, as well as our group, learned a great deal about developing agents for agent negotiation, and also uncovered some interesting software engineering issues.
In this article, I'll present an overview of the TAC market game, software infrastructure, and system performance. Special emphasis is placed on the design and implementation of two software components, featuring design choices that were made to produce a stable and high-performing system. I'll also present some follow-up work that addresses some system performance problems that were discovered during TAC.
The Michigan Internet AuctionBot API supports a number of languages and platforms. C++ implementations are freely available for both UNIX (Solaris, SunOS, SGI IRIX, and Redhat Linux) and Windows 98 using the g++ and Metrowerks CodeWarrior compilers, respectively. Java source code is available for Solaris and SunOS using Sun's Java compiler, and Mathematica code is available for Solaris and SunOS. Likewise, C++ source code for the Bidding Agent is available for UNIX (Solaris, SunOS, and RedHat Linux) and Windows 98. Again, compiler support is for g++ and CodeWarrior, respectively.
An "entrant" to TAC is a group (or person) who implements a strategy in a software agent. Agents run on any machine connected to the Internet, communicating with the TAC game server over TCP sockets. For example, during TAC, participants ran their agents on a machine in their home country and communicated with the TAC game server located at Michigan's AI lab. In spite of the distances and random Internet traffic, this design performed well.
Each TAC game lasts 15 minutes with a 10 minute break between games. Each game involves eight buyer agents and one seller agent. During the practice round (from mid February to mid June) players used the web interface to the TAC game system to schedule and join games. This phase let players develop, test, and refine their agents. During the practice round thousands of games were played. For the qualifying round (from mid June to early July) we scheduled all games for the 18 entrants, randomly adding them to each game (games were scheduled 24 hours a day, seven days a week). The result of this round was 12 semifinalists who competed against one another in Boston in the semi and final rounds. The semi-final round reduced the pool to the top eight agents, who then played in the final round.
In the TAC market game, each player takes the part of a travel agent, with the goal of assembling travel packages for its customers. Each player acts on behalf of its customers, who express their preferences for various travel packages. Travel packages consist of the following:
Customers have individual preferences such as what days they will be in Boston, the hotel to stay at, and which entertainment events to attend. The objective of the game is for travel agents to provide their customers with travel packages that best match their travel preferences. (That is, maximize the total satisfaction of the customers by achieving the highest sum of customer utility.)
A travel agent accomplishes this by receiving the customer's preferences at the beginning of the game, buying and selling items (flight tickets, hotel room reservations, and entertainment tickets) throughout the game, and allocating the held items to customers at the end of the game. Each item is represented by an auction. There are 28 auctions per game: 12 entertainment auctions, eight flight auctions, and eight hotel auctions. Players make purchases by placing bids in an auction for the desired number of items. The auction immediately updates the price quote for the auction, indicating the current price for the item. Each category of auctions has a different set of rules governing its behavior. (See http://tac.eecs.umich.edu/game.html for a complete discussion of the market game, items, and auction rules.)
The TAC software infrastructure is built on the Michigan Internet AuctionBot. The AuctionBot is a highly configurable auction server built to support research on electronic commerce and multiagent negotiation. The server has been operational since 1996 and has matured into a stable auction platform. Over the past few years, the system was redesigned to address the performance needs imposed by the addition of an automated trading facility supporting agent interaction (see "A Control Architecture for Flexible Internet Auction Servers," P.R. Wurman, M.P. Wellman, W.E. Walsh, and K.A. O'Malley, First IAC Workshop on Internet Based Negotiation Technologies, March 1999). In this article, I'll discuss the TAC software system and the AuctionBot system as one system.
As Figure 1 illustrates, the TAC game system is composed of:
To start the game system, the TACShell program is run. This program runs the API, scheduler, scorer, and game manager as child processes. The purpose of the TACShell is to ensure that its child processes stay running. If it detects that a child process has crashed, it logs the event and restarts the process. The TACShell proved to be invaluable because games were running 24 hours a day, seven days a week, and the system could not always be manually monitored.
To run a TAC game, the game manager selects the most recent game from its pending game queue. At the appropriate time, the system runs the game. First, all auctions for the previous game are checked to make sure they closed properly. Next, the auctions for the new game are created and run. For each auction, the scheduler is sent the auction's final clear time. If an error occurs, the game's status is set to "not run," and the game scheduler returns to its main loop.
Next, the game manager launches the TAC seller and any dummy agents participating in the instance. It also enables the distribution of game parameter information so that participating agents can begin playing. At this point, the game manager sleeps until the end of the game.
As the game is running, players can view the progress of the game through the TAC visualization tools. These tools are accessed through a web browser and are implemented as Java applets. They show the bid and ask prices for all auctions and the items held by all agents.
Once the game ends, the scheduler queue contains final clear events for all auctions that should be closed. Each event is popped from the scheduler queue and sent to the corresponding auction. When the auction receives the final clear event, it sends the scheduler a deactivated event informing it that the auction is exiting, and the auction exits. When the scheduler processes the deactivated event for an auction, it checks whether the auction has exited, and then clears it from its process table.
The game data extractor is called to extract all game data from the database into game text files. These files serve as input files for the summary plot generator. The summary plot generator uses these files to construct plots of bidding activity for each auction in the game. Once the plots are generated, the files are then archived for later retrieval through the web interface.
Once a game is complete, players may view the game results through the summary page. The summary page shows the final utility scores of all players in the game. Each player's score is linked to the allocation page, which provides detailed information about the player's allocation, customer preference profile, cost of each item, and unused tickets.
The summary page also shows plots of bidding activity in each auction, all transactions for the game, and an applet showing the final flight, hotel, and entertainment items that all agents hold at the end of the game.
The TAC game system supports participation by software agents through a TCP-based agent API (see "An API for Internet Auctions" by Kevin O'Malley and Terence Kelly, DDJ, September 1998). The API's communication protocol precisely defines message formats for API operations. Messages are encoded as strings that are sent to the server and invoke API functions that run on the server. The server functions return string-based messages to the API client, which inform the client of the result of the request. By implementing the protocol, developers have an API that they can use to interact with the game system.
All agents interact with the TAC game system through the API, therefore, a great deal of time was spent making sure that the API was as efficient and stable as possible. The high-level protocol for agent interaction is as follows:
1. The agent authenticates with the API, supplying a username and password.
2. Once authenticated, it sends API messages to the system and receives results.
3. Once complete, it sends a quit message and disconnects from the API.
Most API operations involve selecting and/or inserting data into a database. The original API implementation forked a process to handle each client connection, opened a database connection when the forked process starts, and closed it when the agent disconnected. Through an examination of the run-time system, we found that a great deal of memory was being consumed by each database connection, too much time was consumed opening a database connection for every client connection, and a slight performance hit was being incurred because of the inefficiency of process invocation. Consequently, we found that the API did not scale well when the number of simultaneous agent connections increased, largely because of the high-memory requirement for a database connection.
To address these issues, the API was redesigned to make better use of memory, eliminate the inefficiency of opening and closing numerous database connections per client connection, and remove the overhead of process invocation. The new design involved moving the API from a forked server to a threaded server that pools client connection threads and database connections. When the API starts up, it creates a pool of database connections and a pool of connection threads. When a client connects, the API selects the next available connection thread from the thread pool. This thread handles all messages for that client connection. When the connection thread receives a client message, it gets the next available database connection object from the database pool, uses it to communicate with the database when servicing the client request, and when complete, returns it to the database connection pool. This process is repeated for each message that the client sends. Once the client disconnects from the API (issues a quit message and terminates), the connection thread is returned to the connection thread pool.
This architecture scales well by making the memory required for database connections constant (rather than dynamic) throughout the life of the API. Database connection memory is now constant and does not grow linearly as new clients connect to the system. Next, we eliminated the overhead of opening/closing database connections as clients connect/disconnect by fixing the number of connections, allocating them at API startup, and maintaining a pool of database connections. Lastly, we removed inefficiency of process invocation by changing the design from a forked server to a threaded server.
To implement these pools, we use STL containers, specifically the list container. The containers are protected by semaphores and synchronized by condition variables. Throughout the projects we use the list, vector, map, and priority queue containers, and have been pleased with their ease of use, performance, and stability.
The scheduler provides three services: It sequences events from the API and auction processes, manages the set of active auctioneers through its process table, and serves as the official time stamper of all generated events.
The scheduler is a multithreaded application with a shared-event queue, which is protected by semaphores and is synchronized by condition variables. The scheduler's main thread is the event loop, which continually checks the event queue and removes the top item at the appropriate time, passing the event to a connection thread to handle the event. The listener thread accepts connections from the API and auctioneers, and places the event on the event queue. The scheduler is based on the producer/consumer model.
The scheduler maintains a table of currently active auctions called the "process table." An entry in the table contains information that the scheduler uses to identify a running auction process. For TAC, all auctions were loaded at game startup to ensure that no auctions needed to be loaded during a game.
When the API or an auction process sends the scheduler an event, it is placed on the scheduler's event queue. At the appropriate time, the event loop pops the event from the queue, looks up the target auction from the process table, and sends the event to the auction process.
System performance was a concern going into TAC. We wanted to present users with a stable and responsive system that could keep up with agents interacting with the game server at a reasonable rate. Initially, it was difficult to identify a precise level of performance that would enable simultaneous agents to implement and carry out meaningful bidding strategies. This was primarily due to our lack of experience in understanding how real agents would behave in the context of a TAC game. For example, our test-bidding agent would submit bids, update its state, and sleep for a few seconds before repeating the process. Real agents are free to do anything — and usually did. Typically, they would hit the server consistently with no sleep time, sometimes connecting/disconnecting several times throughout a game. When entrants were developing their agents during the practice round, clients would often crash during a game, disconnecting without sending the quit message. Though we did attempt to gather an understanding of the required system performance through simulation, it was the interaction of real agents with real bidding strategies, playing in thousands of TAC games, that gave us a better awareness of what constituted permissible system performance.
To demonstrate system performance, I present results here from real TAC semi- and final-round data. I highlight and discuss aspects of the system that required optimizations, and show results of some post-TAC game simulations that show the performance optimizations. The points we used to judge system performance are:
1. The average number of bids per game/minute/second.
2. The bid transition times throughout the game (the time from when the scheduler receives an event until it is processed by the auctioneer program).
3. The number of events received by the API per game.
4. The time required for the API calls throughout the game.
The TAC game system uses a database to store all bids, quotes, and transactions that occurred in a TAC game. For each bid submitted to the system, we write the time that the API received the bid, the time that the scheduler sent the bid to the auction, and the time that the auction processed the bid. This measure tells us how long an agent can expect to wait until their bid is processed by the system. To measure points 1 and 2, I wrote a tool that extracted all bid records from the database for each final-round game. A Perl script is used to process the files and collect results; see Tables 1 and 2.
As Table 2 shows, the bid transitions times are higher than we would have liked. In examining the systems' log files, we found that events were getting from the scheduler to the auctioneers in a few seconds, but the auctioneers made a SQL call that was taking up to 25-35 seconds to complete. This call was performing a SQL select on a database table with a large number of records (around 60,000), which did not have a primary key (because of value duplication). In addition, this table would grow in size as more games were run. Since this information is transitory, it was not necessary to save this data after the game was complete. Removing all the data from the table at game startup significantly reduced the bid transition time; see Table 3.
System performance was also affected by the time spent loading auctions. Originally, the game scheduler would load all auctions at game startup. Once the last auction was loaded, the game started. Since it takes 4-5 seconds to load an auction, the scheduler was still processing several auction load events as the game was beginning and bidding had started. This caused initial bids to have longer transition times at the beginning of a game. By waiting for all auctions to load before the game began, we decreased the initial bid times and made all bid transition times consistent throughout the game.
Gathering data for the final two points required running post-TAC games because we did not get data for these during the semi- and final rounds. To gather performance data on the final two points, I conducted a series of simulations using the TAC game system and eight test agents. These tests were conducted after TAC was completed and include some additional performance enhancements that were not implemented in the original TAC software. The test agent is based on the dummy agent we used during the practice phase of the competition, but interacts with the TAC game server at a much higher rate. This elevated rate of interaction more closely simulates the agent interaction patterns we observed during TAC. The agent's bidding strategy is quite simplistic, but sufficient for the purpose of performance measurements.
A series of 15 games were run on the TAC game system with the eight test agents participating in each game. The test agents were executed on a machine other than the game server to reflect typical game activity. The API, scheduler, and auctioneer programs were instrumented with code that logged event information and wrote it to a file for each game. This code is very minimal and does not negatively impact system performance. Once the 15 games were run, we used the performance log files as well as information in the database for these games to analyze system performance. Perl code collected information from the files and generated summary performance statistics. C++ code selected information from the database. Table 4 displays the number of events received by the API per game.
To get data on the final point (time required for the API calls throughout the game), we ran a test agent during the games that called the most common API functions used by most agents throughout a game, and logged the time each call took to complete. The agent ran on a machine within our domain. During the final round, the API call times averaged 0-10 seconds but could reach 20-30 seconds a call. Some of this time was caused by random Internet traffic, but most was due to system inefficiencies that the post-TAC performance optimization addressed. The times reported by the post-TAC agent were between 0-5 seconds per call.
Overall, TAC was a success with most entrants expressing an interest in making this a yearly event. This year's TAC (TAC-01) will take place in October 2001 in Tampa, Florida, as part of the 3rd ACM Conference on Electronic Commerce. For more information on TAC-01, see http://tac.eecs.umich.edu/. Over the course of the event, we learned a great deal about designing and implementing an agent negotiation system and developing agents for agent negotiation.
DDJ