Tech Report CS-05-16

Bid Determination in Simultaneous Auctions

Amy Greenwald

November 2005

Abstract:

In this paper, bid determination problems, which are faced by autonomous agents trading in simultaneous auctions, are studied. In particular, the central problems of allocation, acquisition, completion, and arbitrage are defined. The main theorem states that bid determination in double-sided auctions---i.e., completion---where goods can be sold as well as bought, is polynomial-time reducible to bid determination in single-sided auctions---i.e., acquisition.

The problems analyzed are generalizations of those which were faced by agents that participated in the First International Trading Agent Competition (TAC-2000), and the (two) proofs of the main theorem are inspired by the implementations of the two top-scoring agents. The first, which is based on ATTac-2000, is straightforward, while the second, which is based on RoxyBot-2000, handles arbitrage in a preprocessing step, thereby simplifying the optimization problem.

Regarding complexity, it is noted that allocation in simultaneous auctions is equivalent to the winner determination problem in combinatorial auctions. Similarly, acquisition in simultaneous auctions is equivalent to the winner determination problem with reserve prices in combinatorial auctions. Finally, completion in simultaneous auctions is a special case of winner determination in combinatorial exchanges. Hence, these three bid determination problems are NP-hard.

Two algorithmic approaches to bid determination problems are applied: heuristic search and integer linear programming. These alternatives are compared experimentally using data from TAC--2000. Three empirical findings are reported: (i) for the dimensions of TAC--2000, 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.

(complete text in pdf)