zbMATH — the first resource for mathematics

Seller-focused algorithms for online auctioning. (English) Zbl 0997.68629
Dehne, Frank (ed.) et al., Algorithms and data structures. 7th international workshop, WADS 2001, Providence, RI, USA, August 8-10, 2001. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2125, 135-147 (2001).
Summary: 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(\log B)\)-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.
For the entire collection see [Zbl 0969.00079].

68U99 Computing methodologies and applications
68U35 Computing methodologies for information systems (hypertext navigation, interfaces, decision support, etc.)
Full Text: Link