In this paper we provide an algorithmic approach to the study of online auctioning. From the perspective of the seller we
formalize the auctioning problem as that of designing an algorithmic strategy that fairly maximizes the revenue earned by
selling n identical items to bidders who submit bids online. We give a randomized online algorithm that is O(logB)-competitive against an oblivious adversary, where the bid values vary between 1 and B per item. We show that this algorithm is optimal in the worst-case and that it performs significantly better than any worst-case
bounds achievable via deterministic strategies. Additionally we present experimental evidence to show that our algorithm outperforms
conventional heuristic methods in practice. And finally we explore ways of modifying the conventional model of online algorithms
to improve competitiveness of other types of auctioning scenarios while still maintaining fairness.
A significant portion of this work was done while this author was at IBM’s India Research Lab.