Journal of Artificial Intelligence Research, 19 (2003) 209-242.
Submitted 12/02; published 9/03
© 2003 AI Access Foundation and Morgan Kaufmann Publishers.
All rights reserved.
Decision-Theoretic Bidding Based on Learned Density Models in
Simultaneous, Interacting Auctions
Department of Computer Sciences, The University of Texas at Austin
1 University Station C0500, Austin, TX 78712 USA
pstone @ cs.utexas.edu
Robert E. Schapire
Department of Computer Science, Princeton University
35 Olden Street, Princeton, NJ 08544 USA
schapire @ cs.princeton.edu
Michael L. Littman
Department of Computer Science, Rutgers University
Piscataway, NJ 08854-8019 USA
mlittman @ cs.rutgers.edu
János A. Csirik
D. E. Shaw & Co.
120 W 45th St, New York, NY 10036 USA
janos @ pobox.com
Toyota Technological Institute at Chicago
1427 East 60th Street, Chicago IL, 60637 USA
mcallester @ tti-chicago.edu
Auctions are becoming an increasingly popular method for transacting
business, especially over the Internet. This article presents a general
approach to building autonomous bidding agents to bid in multiple
simultaneous auctions for interacting goods. A core component of our approach
learns a model of the empirical price dynamics based on past data
and uses the model to analytically calculate, to the greatest extent
possible, optimal bids. We introduce a new and general boosting-based
algorithm for conditional density estimation problems of this kind,
i.e., supervised learning problems in which the goal is to estimate
the entire conditional distribution of the real-valued label. This
approach is fully implemented as ATTac-2001, a top-scoring agent in the
second Trading Agent Competition (TAC-01).
We present experiments demonstrating the
effectiveness of our boosting-based price predictor relative to
several reasonable alternatives.