Competitive Online Truthful Time-Sensitive-Valued Data Auction
share
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 ℳ_1 and prove that it is truthful and Θ(log n)-competitive under some assumptions. Then we present an effective truthful weighted-selection mechanism ℳ'_W by relaxing the assumptions on the sizes of the discount-classes. We prove that it achieves a competitive ratio Θ(nlog n) for any known non-decreasing discount function d(t), and the number of buyers in each discount class n_c ≥ 2. When the optimum expected revenue OPT_1 can be estimated within a constant factor, i.e. c_0 · OPT_1 ≤ Z ≤ OPT_1 for some constant c_0 ∈(0,1), we propose a truthful online posted-price mechanism that achieves a constant competitive ratio 4/c_0. Our extensive numerical evaluations demonstrate that our mechanisms perform very well in most cases.
READ FULL TEXT