Competitive Online Truthful Time-Sensitive-Valued Data Auction

In this work, we investigate online mechanisms for trading time-sensitive valued data. We adopt a continuous function d(t) to represent the data value fluctuation over time t. Our objective is to design an online mechanism achieving truthfulness and revenue-competitiveness. We first prove several lower bounds on the revenue competitive ratios under various assumptions. We then propose several online truthful auction mechanisms for various adversarial models, such as a randomized observe-then-select mechanism M1 and prove that it is textittruthful and Theta(log n)-competitive under some assumptions. Then we present an effective truthful weighted-selection mechanism M'W by relaxing the assumptions on the sizes of the discount-classes. We prove that it achieves a competitive ratio Theta(nlog n) for any known non-decreasing discount function d(t), and the number of buyers in each discount class nc ≥ 2. When the optimum expected revenue OPT1 can be estimated within a constant factor, i.e. c0 · OPT1 ≤ Z ≤ OPT1 for some constant c0 ∈(0,1), we propose a truthful online posted-price mechanism that achieves a constant competitive ratio frac4c0. Our extensive numerical evaluations demonstrate that our mechanisms perform very well in most cases.