ABSTRACT

This talk is concerned with computational problems that arise in the design of bidding agents for simultaneous auctions.  Three natural bid determination (BD) problems are identified---allocation, acquisition, and completion.  The first part of the paper contains theoretical results.  It is argued (i) BD in double auctions, where goods can be sold as well as bought, can be formally reduced to the problem of BD in single-sided auctions; and (ii) BD problems in simultaneous auctions are isomorphic to common variants of the winner determination problem. In the second part of the talk, two algorithmic approaches to bid determination are proposed: heuristic search and integer linear programming.  Using data from the First International Trading Agent Competition (TAC), these alternative techniques are compared empirically.  The key findings reported herein are (i) for the dimensions of TAC, optimal solutions to BD problems 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.
 
 

Dr. Amy Greenwald is an Assitant Professor of Computer Science at Brown University.  She has degrees from NYU, Cornell, Pennsylvania and Oxford. Her current research concerns the  study of multi-agent learning on the Internet via game-theoretic models of computational interactions.