The annual Trading
Agent Competition (TAC) challenges entrants to design autonomous
agents that trade online in simultaneous auctions. Since TAC's
inception in 2000, my group at Brown has entered successive
modifications of its autonomous trading agent, RoxyBot.
Our first entrant was
built around a deterministic optimization problem: how to bid given
point estimates of the auctions' clearing prices. This strategy
proved effective, as RoxyBot was one of the top-scoring agents in
TAC 2000. Nonetheless, RoxyBot-00 was limited by its inability to
explicitly reason about variance within prices.
In the years since
2000, we worked to recast the key challenges of TAC bidding as
stochastic optimization problems, whose solutions exploit
distributions over price predictions. However, RoxyBot fared
unimpressively in tournament conditions, year after year...until
2006.
Half a decade in the
laboratory spent searching for bidding heuristics that exploit
stochastic information at reasonable computational expense finally
bore fruit, as RoxyBot emerged victorious in TAC 2006. The "secret"
of RoxyBot-06's success, in brief: price prediction by simulating
simultaneous ascending auctions, and bidding based on the sample
average approximation method. Details of this approach, and the
trajectory leading up to it, are the subject of this talk.
Joint work with Victor
Naroditskiy and Seong Jae Lee