Abstract: The 2002 Trading Agent Competition (TAC) presented a challenging market game in the domain of travel shopping. One of the pivotal issues in this domain is uncertainty about hotel prices, which have a significant influence on the relative cost of alternative trip schedules. Thus, virtually all participants employ some method for predicting hotel prices. We survey approaches employed in the tournament, finding that agents apply an interesting diversity of techniques, taking into account differing sources of evidence bearing on prices. Based on data provided by entrants on their agents' actual predictions in the TAC-02 finals and semifinals, we analyze the relative efficacy of these approaches. The results show that taking into account game-specific information about flight prices is a major distinguishing factor. Machine learning methods effectively induce the relationship between flight and hotel prices from game data, and a purely analytical approach based on competitive equilibrium analysis achieves equal accuracy with no historical data. Employing a new measure of prediction quality, we relate absolute accuracy to bottom-line performance in the game.
Introduction
In the high-stakes environment of the 2002 Trading Agent Competition (TAC), predicting hotel prices was the "make or break" factor for success. Agents acted as travel agents booking complete trips for eight clients with unique preferences. This required navigating simultaneous, overlapping auctions where flight prices changed stochastically and hotel prices remained unknown until the auctions closed—often minutes after flight commitments were made.
This creates a massive coordination problem. Underestimating hotel prices leads to buying flights for prohibitively expensive trips, while overestimating leads to missed profitable itineraries. This paper addresses the challenge of initial price prediction: forecasting market clearing prices at the start of a game before any bidding data is available.
Methods
A survey of 19 teams from the TAC-02 tournament revealed three primary categories of prediction methods:
- Historical Averaging: Agents like harami and UMBCTAC utilized the closing prices of over 100 previous games, using the mean or median as their forecast.
- Machine Learning (ML): Agents like ATTac used boosting-based algorithms for conditional density estimations, while kavayaH employed neural networks. These models incorporated "game-specific" features, such as initial flight prices.
- Competitive Analysis: Utilized by the agent Walverine, this approach treated the TAC game as a micro-economy. It calculated a Walrasian competitive equilibrium—the prices where total demand from all agents would exactly meet the supply of 16 rooms per hotel.
To evaluate these methods, the authors introduced the Expected Value of Perfect Prediction (EVPP). Unlike standard Euclidean distance, EVPP measures the instrumental value of a prediction by calculating the utility gain an agent would achieve with perfect foresight versus its actual prediction.
Datasets and Tournament Performance
The study utilized data from the TAC-02 tournament, focusing on the finals and semifinals (60 games) and agent prediction logs from 13 different participants. Additionally, historical data from 440 seeding rounds provided a training baseline for ML models.
Key Insights
- Flight Prices as the "Hidden Variable": The most successful predictors (ATTac, Walverine, kavayaH) incorporated initial flight prices. Low flight prices on a specific day drive up hotel demand and prices; agents ignoring this "cross-good" influence performed significantly worse.
- Theory vs. Data: The analytical "Walverine" approach performed as well as top ML models. Despite the assumption of "price-taking" behavior in a small 8-agent game, the Walrasian equilibrium abstraction proved surprisingly effective.
- Accuracy vs. Performance: Low Euclidean distance does not always correlate with success. The EVPP metric proved to be a superior proxy for game scores because it weights errors based on their impact on decision-making.
Key Results
- Top Performers: Walverine and ATTac01 (the 2001 version) were the most accurate predictors. ATTac02 performed worse than its predecessor, likely due to software bugs or environmental changes.
- ML Regression: Controlled trials indicated that reducing an agent's EVPP by 1 point per client translated to an increase of approximately 8 to 11 points in the final game score.
Limitations and Future Work
The paper focuses on initial predictions; however, agents update beliefs as auctions close during the "interim" phase. Furthermore, the simplification of probability distributions to mean values may undervalue agents designed for risk management. Finally, the regression analysis was limited to variants of a single agent (Walverine), meaning other factors like bidding strategy might play a larger role in a more diverse field.
Summary updated