Correspondence: Georgia Perakis, Sloan School of Management and Operations Research Center, Massachusetts Institute of Technology, E53-359, Cambridge, MA 02139, USA. E-mail: georgiap@mit.edu

¹is currently the Boeing Professor of Operations Research and the co-director of the Operations Research Center at the Massachusetts Institute of Technology. He has received a BS in Electrical Engineering and Computer Science at the National Technical University of Athens, Greece in 1985, an MS in Operations Research at MIT in 1987 and a PhD in Applied Mathematics and Operations Research at MIT in 1988. Since 1988, he has been in the MIT faculty. His research interests include optimisation, stochastic systems, data mining and their application. He has published widely and he has co-authored three graduate-level textbooks. He is a member of the National Academy of Engineering, and he has received numerous research awards including the Erlang prize (1996), the Farkas prize (2008) and the SIAM prize in optimisation (1996).

²graduated with his bachelors degree from UBC in Canada. He subsequently joined the Operations Research Center at MIT where he finished his PhD entitled 'A Lagrangean decomposition method for dynamic optimization and its applications' in 2003. Upon graduation he joined 'Resource Planning Options Ltd' in Canada as a consultant. He is currently working in the US in the area of finance.

³is an associate professor at the Sloan School of Management at MIT since 1998. Her research interests include applications of optimisation and equilibrium in revenue management, pricing, competitive supply chain management and transportation. She has widely published in journals such as Operations Research, Management Science, Mathematics of Operations Research and Mathematical Programming among others. She has received the CAREER award from the National Science Foundation and subsequently the PECASE award from the office of the President on Science and Technology. She has also received an honourable mention in the TSL Best Paper Award, the Graduate Student Council Teaching Award for excellence in teaching, the Sloan Career Development Chair and subsequently the J. Spencer Standish Career Development Chair. Perakis currently serves in a variety of editorial boards such as for the journal of Operations Research and Naval Research Logistics.

Received 18 September 2008; Revised 18 September 2008.

Abstract

Online auctions are arguably one of the most important and distinctly new applications of the Internet. The predominant player in online auctions, eBay, has over 42 million users, and it was the host of over $9.3 billion worth of goods sold just in the year 2001. Using methods from approximate dynamic programming and integer programming, we design algorithms for optimally bidding for a single item in an online auction, and in simultaneous or overlapping multiple online auctions. We report computational evidence using data from eBay's website from 1772 completed auctions for personal digital assistants and from 4208 completed auctions for stamp collections that shows that (a) the optimal dynamic policy outperforms simple but widely used static heuristic rules for a single auction, and (b) a new approach for the multiple auctions problem that uses the value functions of single auctions found by dynamic programming in an integer programming framework produces high-quality solutions fast and reliably.