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.

Share

COinS
 
Feb 28th, 8:00 AM

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.

 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.