Optimal Bidding in On-line Auctions
📜 Abstract
On-line auctions are arguably one of the most important and distinctly new applications of the Internet. The predominant player in on-line auctions, eBay, has over 42 million users, and it was the host of over $9.3 billion worth of goods sold 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 on-line auction, and in simultaneous or overlapping multiple on-line auctions. We report computational evidence using data from eBay’s web site 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.
✨ Summary
Summary
The paper formulates online bidding as a stochastic dynamic-programming problem rather than as a purely game-theoretic bidding problem. For a single auction, the state consists primarily of the current listed price and the bidder’s proxy-bid status. The model represents competing bids probabilistically as functions of the listed price and remaining auction time, and it explicitly models the possibility that bids submitted during the final seconds may fail to register. The bidder seeks to maximize expected surplus subject to a maximum willingness-to-pay.
The resulting Bellman-equation algorithm produces state-dependent bidding policies. In simulations calibrated with 1,772 Palm Pilot III auctions and 4,208 stamp-collection auctions, the dynamic policy outperformed fixed-time and fixed-budget heuristics in expected utility and generally reduced spending per win. For multiple simultaneous or overlapping auctions, the authors develop approximate dynamic-programming methods and integer-programming approximations. Their principal method, IPA, combines single-auction value functions within an integer program constrained by per-auction and aggregate budgets. Across the reported experiments, IPA achieved performance close to exact dynamic programming when the latter was computationally feasible, while remaining substantially more scalable. The paper also examines competition from additional strategic bidders and extends the framework to auctions ending at different times.
Subsequent research has explicitly used this work as a reference point for automated bidding agents and for optimization-based bidding under uncertainty. A later study on automated dynamic bidding agents describes the paper’s dynamic-programming and integer-programming approach as a basis for bidding in single, simultaneous, and overlapping online auctions. (opus.lib.uts.edu.au) A later robust-optimization study cites the paper as an example of strategic bidding based on approximate dynamic programming and integer programming, while adapting the problem to uncertainty sets and sealed-bid markets. (sciencedirect.com) The available evidence therefore indicates methodological influence on subsequent computational-auction research; the search did not identify independently documented large-scale commercial deployment of the specific algorithm beyond the authors’ own reported use in eBay auctions. The journal publication is bibliographically listed as a 2009 article in volume 8, issue 1, pages 21–41. (researchgate.net)