Bid Determination in Simultaneous Auctions

Amy Greenwald and Justin Boyan

Abstract

This paper presents an architecture for trading agents in online simultaneous auctions. This architecture embodies various bid determination (BD) problems: allocation, acquisition, and completion. In the first part of the paper, it is argued that BD in double auctions (i.e., completion), where goods can be sold as well as bought, can be formally reduced to the problem of BD in single-sided auctions (i.e., acquisition). It is also noted that BD problems in simultaneous auctions are equivalent to common variants of the winner determination problem in combinatorial auctions.

In the second part of the paper, two algorithmic approaches to bid determination are proposed: heuristic search and integer linear programming. Using data from the First International Trading Agent Competition (TAC--2000), these alternative techniques are compared experimentally on the allocation problem. The key empirical findings reported herein are: (i) for the dimensions of TAC, optimal solutions are tractable; (ii) optimal solutions do not scale; and (iii) heuristic approximation methods scale well, achieving near optimal solutions with predictable time and space requirements.