Description
Online auctions are a viable alternative to conventional posted price mechanisms. Agrawal, Wang, and Ye [1] have proposed two primal-dual algorithms for revenue-maximizing multi-item allocation tasks. Although promising in terms of theoretical properties and competitive ratios, there is alack of evidence regarding the real-world practicability of these mechanisms, for instance referring to online auction-based tickets sales. In this paper, we conduct an experimental study on both the One-Time Learning Algorithm(OLA) and the Dynamic Learning Algorithm (DLA) based on synthetic data, revealing the remarkable aptitude of the latter for non-trivial online auctions. Being robust to most input variations, the inherent dynamic update of dual thresholds achieves a superior balance with respect to the trade-off between objective function values and runtimes. We address critical sensitivities quantitatively and draft several small extensions by incorporating input distribution knowledge.
Online Auctions with Dual-Threshold Algorithms: An Experimental Study and Practical Evaluation
Online auctions are a viable alternative to conventional posted price mechanisms. Agrawal, Wang, and Ye [1] have proposed two primal-dual algorithms for revenue-maximizing multi-item allocation tasks. Although promising in terms of theoretical properties and competitive ratios, there is alack of evidence regarding the real-world practicability of these mechanisms, for instance referring to online auction-based tickets sales. In this paper, we conduct an experimental study on both the One-Time Learning Algorithm(OLA) and the Dynamic Learning Algorithm (DLA) based on synthetic data, revealing the remarkable aptitude of the latter for non-trivial online auctions. Being robust to most input variations, the inherent dynamic update of dual thresholds achieves a superior balance with respect to the trade-off between objective function values and runtimes. We address critical sensitivities quantitatively and draft several small extensions by incorporating input distribution knowledge.