Cover ERCIM News 51

This issue in pdf
(64 pages; 13,7 Mb)

Archive:
cover ERCIM News No. 50
previous issue
(Number 50
July 2002):
Special theme:
ERCIM Mathematics

all previous issues

Next issue:
January 2003

Next Special theme:
Embedded Systems

About ERCIM News

Valid HTML 4.01!

spacer
 
EVENTS
< Contents ERCIM News No. 51, October 2002
 

The Trading Agent Competition - TAC 2002

by Joakim Eriksson and Sverker Janson

The finals of the third annual Trading Agent Competition were held on 28 July 2002, co-located with AAAI-02 in Edmonton, Canada. The actual games took place on the Internet, with the game and auction servers running at SICS in Kista, Sweden. The agents resided at the home locations of the participating research groups.

Trading Agents
A trading agent is a computer program that acts on online markets on behalf of one or more clients, trying to satisfy their preferences. In the trading agent competition (TAC), agents are travel agents with the goal of assembling travel packages in a five-day period, from flight tickets, to hotel rooms, and event tickets. In a game (Figure 1), eight agents, each representing eight clients, compete for a limited amount of goods on a total of 28 different auctions, for 12 minutes. The agents receive a score based on how well client preferences are satisfied (sum of client utilities) and the average score over a number of games determines the winner.

Figure 1: A TAC game has 8 agents, each with 8 clients, and 28 simultaneous auctions.
Figure 1: A TAC game has 8 agents, each with 8 clients, and 28 simultaneous auctions.
Figure 2: SICS TAC server and clients.
Figure 2: SICS TAC server and clients.

TAC combines a fairly realistic model of the Internet commerce of the future with challenging problems in automated reasoning and decision making:

  • Relative to their clients, TAC agents have to solve a combinatorial assignment problem, where goods available to an agent are packaged into bundles, and delivered as such to the clients. This problem is related to that of an auctioneer determining winning bids in a combinatorial auction. Successful trading agents must therefore make use of similar integer programming or constraint programming techniques.
  • Relative to other agents, TAC agents instead have a strategy problem. To determine which strategy to use in a competitive situation is not easy. Essentially, there is no known way to compute the best course of action. One important strategic component in TAC is estimating auction closing prices.

Good software trading agents can potentially handle more complex combinations of goods, larger numbers of goods and markets, a wider range of market types, and faster markets with more fine-grained goods than their human counterparts.

TAC Software
For TAC-02, SICS developed open-source TAC server software, freely available to all TAC competitors as well as to other researchers, students, and educators in the field. The previous two competitions, TAC-00 and TAC-01, were played on the Michigan Internet AuctionBot platform, a configurable auction server available as an Internet service but not available as downloadable software.

The SICS TAC server (Figure 2) is written using a combination of SICStus Prolog and Java and consists of two main subsystems, the Game Server, running the actual games and communicating with trading agents, and the Information Server, for managing participants, games scheduling, and collecting and distributing game information and statistics via the Web and game monitoring applets.

SICS also developed new TAC agentware, a Java software toolkit for developing TAC agents, making it easy to get started. Most of the new TAC entrants based their agents on the SICS TAC agentware.

Figure 3: Locations of the TAC-2002 participants.
Figure 3: Locations of the TAC-2002 participants.

TAC-02 Games and Agents
The winner in this year's tight field of competitors was 'whitebear', developed by Ioannis A. Vetsikas at Cornell University with the the University of Southampton as a close runner-up.

The TAC-02 finals were the conclusions of several weeks of qualification and seeding rounds involving thousands of games, with different combinations of agents and different random client preferences:

  • Qualification: select top 16 out of 26 agents for the semi-finals (120 games/agent)
  • Seeding: seed agents into two semi-final groups (440 games/agent)
  • Semi-finals: select top 4 agents of each group for the finals (14 games/agent)
  • Finals: determine winner (32 games/agent).

The number of games in the finals is quite small, due to the desire to run them in a single day. This increases the element of chance in the game and is likely to be changed in future competitions.
Each year most teams build their agents on the ideas and solutions of the previous year's top-performing agents. Methods, models, and technologies used in TAC-02 agents include:

  • Linear Programming - for finding optimal set of travel packages, many inspired by the optimiser used by TAC-00 winner, ATTac
  • Machine Learning - automatic learning of closing prices on hotels, trading policies for entertainment, etc
  • POMDP, Partially Observable Markov Decision Processes
  • Genetic Algorithms - for finding an optimal set of travel packages
  • Price Prediction - various ways of predicting price including 'Walrasian competitive equilibrium'.

Many of the agent teams did not have time to fully implement their ideas and approaches to the TAC problem. There are still many untested ideas, which will guarantee interesting results for coming TAC events.

The future of TAC
Following the 2002 finals, discussions about the future of TAC have been intense. The competition has increased in popularity, and is widely recognised as a both fruitful and entertaining means of addressing important issues in the field of agents. While participant performance has increased considerably in the first three competitions, the TAC game is by no means a fully solved problem and will remain as the 'TAC classic' in future competitions.

There is consensus that the TAC community is ready for the introduction of an additional trading game, introducing new aspects and corresponding research issues. But there are several different candidate proposals, ranging from minor modifications of 'TAC classic' to quite different games involving spectrum auctions, stock markets, and supply chain management. There is also consensus that TAC will be proposed as an official workshop in a major AI or agents conference such as IJCAI or AAMAS, potentially attracting more interest and participants.

We look forward to seeing even more European participants in future competitions. You can get a head start in 'TAC classic' by downloading and trying out the SICS TAC server and agentware.

Link:
http://www.sics.se/tac/

Please contact:
Joakim Eriksson, SICS
Tel: +46 8 633 1541
E-mail: joakime@sics.se
http://www.sics.se/~joakime/
 
spacer