Tech Report CS-06-15

Heuristics for the Deterministic Bidding Problem: Lessons from TAC Travel

Amy Greenwald, Victor Naroditskiy and Seong Jae Lee

June 2006

Abstract:

We study heuristics that were designed for bidding in the simultaneous auctions that characterize the Trading Agent Competition (TAC) Travel Game. At a high-level, the design of many successful TAC agents can be summarized as: (i) predict: build a model of the auctions' clearing prices; (ii) optimize: solve for an (approximately) optimal set of bids, given this model.

Analytically, we address the (decision-theoretic) deterministic bidding problem. We derive the class of bidding heuristics that solves this problem optimally. In particular, we prove that the marginal-value-based bidding heuristic implemented in RoxyBot-2000 -- one of the top-scoring agents in TAC 2000 -- is an instance of this class. Moreover, we identify the special set of circumstances in which bidding marginal values themselves is also optimal.

Experimentally, we embed these heuristics in TAC Travel agents and evaluate their success in the game-theoretic bidding problem that characterizes TAC Travel auctions. We find that RoxyBot-2000's bidding heuristic dominates the others in our test set. We conclude that RoxyBot-2000's bidding heuristic is effective in that it performs well in a decision-theoretic setting assuming perfect price prediction and a game-theoretic setting where price predictions are imperfect.

(complete text in pdf)