Auctions are an increasingly popular method for transacting business, especially over the Internet. In an auction for a single good, it is straightforward to create automated bidding strategies--an agent could keep bidding until reaching a target reserve price, or it could monitor the auction and place a winning bid just before the closing time (known as sniping).
When bidding for multiple interacting goods in simultaneous auctions, on the other hand, agents must be able to reason about uncertainty and make complex value assessments. For example, an agent bidding on one's behalf in separate auctions for a camera and flash may end up buying the flash and then not being able to find an affordable camera. Alternatively, if bidding for the same good in several auctions, it may purchase two flashes when only one was needed.
This article makes three main contributions. The first contribution is a general approach to building autonomous bidding agents to bid in multiple simultaneous auctions for interacting goods. We start with the observation that the key challenge in auctions is the prediction of eventual prices of goods: with complete knowledge of eventual prices, there are direct methods for determining the optimal bids to place. Our guiding principle is to have the agent model its uncertainty in eventual prices and, to the greatest extent possible, analytically calculate optimal bids.
To attack the price prediction problem, we propose a machine-learning approach: gather examples of previous auctions and the prices paid in them, then use machine-learning methods to predict these prices based on available features in the auction. Moreover, for our strategy, we needed to be able to model the uncertainty associated with predicted prices; in other words, we needed to be able to sample from a predicted distribution of prices given the current state of the game. This can be viewed as a conditional density estimation problem, that is, a supervised learning problem in which the goal is to estimate the entire distribution of a real-valued label given a description of current conditions, typically in the form of a feature vector. The second main contribution of this article is a new algorithm for solving such general problems based on boosting [Freund SchapireFreund Schapire1997,Schapire SingerSchapire Singer1999].
The third contribution of this article is a complete description of a prototype implementation of our approach in the form of ATTac-2001, a top-scoring agent1 in the second Trading Agent Competition (TAC-01) that was held in Tampa Bay, FL on October 14, 2001 [Wellman, Greenwald, Stone, WurmanWellman et al.2003a]. The TAC domain was the main motivation for the innovations reported here. ATTac-2001 builds on top of ATTac-2000 [Stone, Littman, Singh, KearnsStone et al.2001], the top-scoring agent at TAC-00, but introduces a fundamentally new approach to creating autonomous bidding agents.
We present details of ATTac-2001 as an instantiation of its underlying principles that we believe have applications in a wide variety of bidding situations. ATTac-2001 uses a predictive, data-driven approach to bidding based on expected marginal values of all available goods. In this article, we present empirical results demonstrating the robustness and effectiveness of ATTac-2001's adaptive strategy. We also report on ATTac-2001's performance at TAC-01 and TAC-02 and reflect on some of the key issues raised during the competitions.
The remainder of the article is organized as follows. In Section 2, we present our general approach to bidding for multiple interacting goods in simultaneous auctions. In Section 3, we summarize TAC, the substrate domain for our work. Section 4 describes our boosting-based price predictor. In Section 5, we give the details of ATTac-2001. In Section 6, we present empirical results including a summary of ATTac-2001's performance in TAC-01, controlled experiments isolating the successful aspects of ATTac-2001, and controlled experiments illustrating some of the lessons learned during the competition. A discussion and summary of related work is provided in Sections 7 and 8.