Thursday, February 8, 2007
4:15 pm
B17 Upson Hall

Computer Science
Spring 2007

Amy Greenwald
Brown University

Autonomous Bidding Agents:
Strategies and Lessons from TAC Travel

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