An Optimal Strategy for Sellers
in an Online Auction
IBM T. J. Watson Research Center
We consider an online auction setting where the seller attempts to sell an item. Bids arrive over
time and the seller has to make an instant decision to either accept this bid and close the auction
or reject it and move on to the next bid, with the hope of higher gains. What should be the seller’s
strategy to maximize gains? Using techniques from convex analysis, we provide an explicit closed-
form optimal solution (and hence a simple optimum online algorithm) for the seller.
Our methodology is attractive to online auction systems that have to make an instant decision,
especially when it is not humanly possible to evaluate each bid individually, when the number of
bids is large or unknown ahead of time, and when the bidders are unwilling to wait.
Categories and Subject Descriptors: F.1.2 [Computation by Abstract Devices]: Modes of
Computation; G.1.6 [Numerical Analysis]: Optimization; G.1.7 [Numerical Analysis]: Ordinary
Differential Equations; K.4.4 [Computers and Society]: Electronic Commerce
General Terms: Algorithms, Theory
Additional Key Words and Phrases: Convex analysis, online auctions, random walks
An auction is a common market method to sell items. In a conventional market,
the buyer considers the price of an item as given; auctions come handy in cases
when the item has no predefined market value. There are many different forms
of auctions, and the most common takes place in an auction house where a seller
seeks the highest possible price for an item among several potential buyers.
Traditionally, the buyers in an auction are called bidders and the price they
seek for the item is called a bid. The birth of auctions can be dated back at
least as early as 193 AD, when the Roman empire was auctioned to the highest
bidder. A large volume of literature exists on auctions and auction analysis (see
[Mas-Collel et al. 1995; Osborne and Rubinstein 1994]).
Author’s address: IBM T. J. Watson Research Center