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.