论文标题
竞争性在线真实的时间敏感的数据拍卖
Competitive Online Truthful Time-Sensitive-Valued Data Auction
论文作者
论文摘要
在这项工作中，我们研究了用于交易时间敏感的有价值数据的在线机制。我们采用连续函数$ d（t）$来表示随时间$ t $的数据值波动。我们的目标是设计\ emph {在线}实现\ emph {真实性}和\ emph {Revenue-Competitions}的机制。我们首先在各种假设下证明了收入竞争比率的几个下限。然后，我们为各种对抗模型提出了几种在线真实的拍卖机制，例如随机观察到 - 然后选择机制$ \ MATHCAL {M} _1 $ $，并证明它是\ textit {真实{真实}和$θ（\ log n）$ - 在某些假设下有竞争力。然后，我们通过放松折扣级尺寸的假设来放松一个有效的真实加权选择机制$ \ MATHCAL {M'} _ W $。我们证明，对于任何已知的非淘汰折扣功能$ d（t）$，以及每个折扣类$ n_c \ ge 2 $中的购买者数量$ d（t）$。如果可以在不变的因素内估算最佳预期收入$ opt_1 $，即$ C_0 \ CDOT opt_1 \ le z \ le z \ le opt_1 $对于某些常数$ c_0 \ in（0,1）$，我们提出了一种真实的在线发布的优点机制，可以达到恒定竞争力的比例$ \ freac $ \ freac $ \ freac $ \ freac $ \ freac $ \ freac {4} co_0} $} co_0}。我们广泛的数值评估表明，在大多数情况下，我们的机制表现良好。
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 \emph{online} mechanism achieving \emph{truthfulness} and \emph{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 $\mathcal{M}_1$ and prove that it is \textit{truthful} and $Θ(\log n)$-competitive under some assumptions. Then we present an effective truthful weighted-selection mechanism $\mathcal{M'}_W$ by relaxing the assumptions on the sizes of the discount-classes. We prove that it achieves a competitive ratio $Θ(n\log n)$ for any known non-decreasing discount function $d(t)$, and the number of buyers in each discount class $n_c \ge 2$. When the optimum expected revenue $OPT_1$ can be estimated within a constant factor, i.e. $c_0 \cdot OPT_1 \le Z \le OPT_1 $ for some constant $c_0 \in(0,1)$, we propose a truthful online posted-price mechanism that achieves a constant competitive ratio $\frac{4}{c_0}$. Our extensive numerical evaluations demonstrate that our mechanisms perform very well in most cases.
