# Competitive Online Truthful Time-Sensitive-Valued Data Auction

arXiv: https://arxiv.org/abs/2210.10945 · HTML: https://mlsanity.com/paper/2210.10945/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Oct 2022.

## Built on by (most cited first, 1 of 1)

- [Fast-DataShapley: Neural Modeling for Training Data Valuation](https://mlsanity.com/paper/2506.05281/) (2025)

## Abstract (arXiv)

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.