1 Competitive Online Truthful Time-Sensitive-Valued Data Auction

2025-04-30 0 0 1.61MB 33 页 10玖币

Competitive Online Truthful

Time-Sensitive-Valued Data Auction

Shuangshuang Xue, Student Member, IEEE, Xiang-Yang Li, Fellow, IEEE,

Abstract—Digital product, such as original data and data-copyright, as an irreplaceable form of data products, can be transferred by

the owner to potential users to maximize its potential usage while protecting the traded data from being resold. Moreover, the value of

the digital product and data typically changes over time in real data application scenarios such as monitoring and recommendation

systems, i.e., its value is time-sensitive. In this work, we investigate online mechanisms for trading time-sensitive valued digital product

and data-copyright. We adopt a continuous function d(t)to represent the data value ﬂuctuation over time t. Our objective is to design

an online trading mechanism achieving truthfulness and revenue-competitiveness with respect to the ofﬂine widely-celebrated Vickrey

auction. However, designing such single-round online mechanisms (i.e., the copyright can only be sold to one unique buyer) is much

more challenging than that in a multi-round scenario due to the short of opportunities to learn the trading information, or than that in a

non-time-sensitive scenario as each user’s valuation changes over time. We ﬁrst prove several lower bounds on the revenue

competitive ratios of individual-rational mechanisms under various assumptions, such as a lower bound of Ω(n)when there is an

arbitrarily unknown function d(t), and a lower bound of Ω( log n

log log n)when the known function d(t)is non-increasing. We then propose

several online truthful auction mechanisms for various adversarial models, such as a randomized observe-then-select mechanism MR

and prove that it is truthful and Θ(log2n)-competitive when d(t)is known and non-increasing and the number of users ncin each

discount-class is of same order. With same assumption, we show that a simpler mechanism M1is truthful and Θ(log n)-competitive.

Furthermore, without any restrictions on the sizes of the discount-classes, we prove that the mechanism M1could have a competitive

ratio as ad as Ω(n2). Then we present an effective truthful weighted-selection mechanism M0Wby 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 nc≥2. When the optimum expected revenue can be estimated within a constant factor, we propose a truthful online

posted-price mechanism that achieves a constant competitive ratio. We conduct extensive numerical evaluations to evaluate the

practical performances of proposed mechanisms and our results demonstrate that our mechanisms perform very well in most cases.

Index Terms—Data trading, truthful mechanisms, digital product, auction.

1 INTRODUCTION

Big data and AI techniques have demonstrated remarkable

capabilities in many areas [1], such as noise monitoring [2],

trafﬁc analysis [3], visual object recognition [4], recommen-

dations on e-commerce websites [5]. Big data, as a key

ingredient to unlock the power of artiﬁcial intelligence, has

become a strategic resource for economic and social devel-

opment similar to the land, oil and capital [6]. Powerful

deep learning models, such as speech recognition [7], deep

face recognition [8], and deepfake forensics [9], heavily rely

on large amounts of speciﬁc training data, e.g., sensor data,

picture, video, and so on. Thus, for data consumers, effective

approaches for data acquisition are urgently in need. For

example, one can adopt some crowdsourcing techniques to

collect the needed data, or buy the required data from data

owners who are willing to share their data for proﬁts, or

buy the machine learning services without actually buying

the data directly.

To facilitate the data exchange between data owners and

data-based service providers, emerging works are exploring

various approaches to build data trading markets [10], [11].

Designing effective data trading markets has attracted a

great amount of attentions recently [10], [11], [11], [12], [13],

and a number of data trading platforms have emerged, such

as DataExchange, Datacoup, DATATANG, GBDEx, Data-

coup, Qlik, CitizenMe Factual, XOR Data Exchange. In a

typical trading scenario, data providers sell their data to the

platform from where consumers can discover and purchase

the data. There are two main procedures for users of the

data platform: data purchasing and data selling.

Data trading is signiﬁcantly different from trading of

traditional commodities [11]. There are many technical chal-

lenges and concerns in designing effective data trading

platforms, such as trustable data rights determination and

management [14], [15], [16], effective data quality evalua-

tion [17], [18], [19], [20], data privacy [21], [22], [23], [24]

especially unstructured data privacy, privacy-preserving

computing and learning [25], [26], [27], [28], strategy-proof

trading mechanism design [29], [30], data tracing [31], [32],

law and rule enforcement [33], [34], accountability [35], [36],

and intelligent data applications. Data pricing, a critical

fundamental mechanism for data markets, has become a hot

topic both in industry and academia [13]. Designing data

pricing mechanisms for revenue (approximately) maximiza-

tion, or social welfare maximization has attracted a great

amount of attentions [12], [13], [37], [38], [39], [40], [41], [42].

In general, revenue maximization considers the aspects

of cost minimization in data collection and proﬁt maximiza-

tion in data selling. Some existing works try to minimize

the cost in the process of data purchasing via crowdsourc-

ing [17], [43], [44], [45], [46]. In this work, we focus on

designing revenue-competitive truthful online mechanisms

for trading data related digital products. In other words,

arXiv:2210.10945v1 [cs.GT] 20 Oct 2022

the seller of the data (which could be the data owner

or the data trading platform) selects some buyers from a

group of potential buyers to maximize the total payment

paid by these selected buyers. Previous works (e.g., [12],

[38], [46], [47]) proposed various data pricing models based

on privacy, quality and query-version. As a supplement

of existing work, we here investigate online mechanisms

for trading raw data (or dataset1) or some form of digital

products such as software or machine-learning models by

jointly considering the data copy-sensitiveness and time-

sensitiveness:

•Copy-sensitiveness: The more scarce resource the more

valuable it is. Speciﬁcally, being the only owner of some

critical data (or some AI models, or some Apps) might

beneﬁt the owner to dominate a speciﬁc market. In

this work, we study the scenario that all buyers are

competitive to obtain the data-copyright or exclusive

usage of some data which is universally unique. In

other words, the speciﬁc data or the data product will

be sold to only one carefully selected user to maximize

the expected revenue of the seller.

•Time-sensitiveness: In real data application scenarios,

typically the perceived data value will change over

time. In some cases such as monitoring [48] and rec-

ommendation systems [49], the consumers prefer near-

term data to improve the prediction or classiﬁcation

accuracy. Thus, the data value may decrease over time.

In other cases such as the time-series data [47], [50],

the value may increase over time since the data grad-

ually becomes more accurate and complete. Besides,

the variation of data value may be more complicated

due to some speciﬁc considerations, e.g., increasing for

some time and then decreasing. In general, we use a

continuous ”discount” function d(t)2to denote the

data value ﬂuctuation over time t. When a buyer ihas

an initial valuation vifor the data at time 0, then the

valuation becomes vi·d(t)at time t≥0. In this work,

we assume that such a value discount function d(t)is

known to the buyers and also the seller.

In this work, our objective is to design strategy-proof

mechanisms that can incentivize buyers to truthfully arrive

in time and report his true valuation vior discounted val-

uation vid(t), while approximately maximize the revenue

and/or social efﬁciency. The combined feature of copy-

sensitiveness and time-sensitiveness increases the difﬁculty

of mechanism design for revenue maximization in online

data pricing. Unfortunately, existing online mechanisms can-

not be applied directly here. In this work, we focus on

trading time-sensitive valued digital product (such as data

or data-copyright, etc.) and our objective is to design an

online mechanism with the following desirable properties:

Individual Rationality, Incentive Compatibility (both time-

IC and value-IC), Consumer Sovereignty, Competitiveness,

and Computational Efﬁciency. A mechanism is called truth-

ful (or strategy-proof) if it satisﬁes both Individual Rational-

ity (IR, non-negative utility), Incentive Compatible(value-

1. We use the “data” or “dataset” interchangeably to denote one unit

of the trading data or the data product such as an AI model.

2. In this paper, we use the term “discount” though the function d(t)

is not necessarily monotone decreasing as a function of t.

bidding and time-arrival) and Consumer Sovereignty(CS,

a chance to win). We focus on designing truthful auction

mechanisms with approximately optimum revenue.

When selling the data to potential buyers for revenue

maximization, typically there are two different approaches.

One is the posted price mechanism, where the seller posts a

public price for a single data and the buyers take-it-or-leave-

it. i.e., the buyer decides to buy if its discounted valuation

vid(t)is at least this posted price. Previous works [38],

[51], [52] usually model it as a multi-armed bandit (MAB)

optimization. However, the MAB-based approaches are all

multi-round-play games, while the problem studied here is

to consider the single-round trading for a speciﬁc digital

good or data copyright. The other is auction mechanism

where each buyer reports a possible bid when arrives, and

the seller determines whether to sell the product to this

buyer and at what price. One typical auction mechanism

is online auction mechanism when users arrive online. Then

when a user iarrives, the user needs report a value repre-

senting his reserving price ri(called bid) for his target data;

and then the seller will immediately decide whether to sell

the data or not and the decision is irrevocable. Typically,

the seller also needs to immediately determine the price the

buyer needs to pay online when the user arrives. In certain

situations, the seller is allowed to postpone his decision on

the amount of payment that the buyer needs to pay.

The problem studied here is similar to the online sec-

retary problem, and its variations such as discounted sec-

retary problem. Without considering the time-sensitiveness,

Hajiaghayi et al. [53] have presented a constant-competitive

truthful online auction of single item. However, when con-

sidering the discount function d(t), each bidder’s true val-

uation ﬂuctuates overtime and thus the existing mechanism

may result in an arbitrarily large competitive ratio with

respect to ofﬂine Vickrey for revenue. When considering

discounting valuations, by using a two-stage sampling-

accepting process, Wu et al. [54] presented a strategy-proof

online auction in the multi-round-play setting, i.e., each

data can be sold up to g≥1copies in each time slot t.

Unfortunately, such mechanisms cannot be directly applied

to our setting where only one buyer will get the data. The

single-round online trading task studied in this work is

much more challenging due to the short of opportunities

to learn the trading information.

To the best of our knowledge, this work is the ﬁrst

to study the single-round online mechanism in the time-

sensitive setting. Observe that even when all buyers are

truthful in advance, all online algorithms have competitive

ratio at least Ω( log n

log log n)[55]. Generally, for all truthful

online mechanisms, we will ﬁrst show a lower bound of

Ω(n)on the revenue competitive ratio when we have an

arbitrary unknown discount function d(t)(§4), and a lower

bound Ω( log n

log log n)for non-increasing discount functions. We

design a sequence of online truthful auction mechanisms by

the following approaches: 1) partition the discount function

into different classes such that the discount values in each

discount-class is within a constant B > 1of each other, i.e.,

the discount value in class cis in the range [B−c, B−c+1]

(assuming that the maximum discount value is 1); 2) then

run some mechanism on users from one carefully selected

discount-class (in this sub-procedure, we will ignore the

discount values of users as they are within a constant

factor of each other). Then we design an online truthful

and O(log2n)-competitive mechanism (called MR) when

there is an arbitrary known non-increasing discount function

d(t)(§5.1 and §5.2) and the number of users per discount-

class is within a constant factor of each other. We also

present a simpler truthful mechanism M1with O(log n)-

competitive ratio. Furthermore, without any restrictions on

the sizes of the discount-classes, we prove that the mecha-

nism M1could have a competitive ratio as bad as Ω(n2).

The design of online approximate algorithm, due to its

worst-case nature, can be quite pessimistic when the input

instance at hand is far from worst-case. Then we propose an

heuristic weighted selection mechanisms MW(see §5.4) and

a modiﬁed weighted selection mechanism M0

W(see §5.5).

We show that the modiﬁed weighted selection mechanism

Wachieves a competitive ratio O(nlog n)for any known

non-decreasing function d(t), and by only assuming that

each discount class has at least 2 users, i.e.,nc≥2. When

the optimum revenue can be estimated within a constant

factor, we then design a mechanism MZwith a constant-

competitive ratio. We also present several reserved-price

mechanisms when the valuations of users are drawn from

some given known distribution. All mechanisms has linear

time computation complexity. We conduct extensive simu-

lations to study the performance of proposed mechanisms,

especially the competitive ratios and the impact of different

parameters. Our numerical results show that all mecha-

nisms MR,MW, and M0

Wdo achieve better performance

than its theoretical worst-case results in terms of revenue,

and the performance of MWis about ten times better than

MRin our evaluation (§7.2).

The rest of the paper is organized as follows. In Section 2,

we brieﬂy review related work in the literature. In Sec-

tion 3, we introduce the model of online auction with time

discounting values, and recall important solution concepts

used in this paper. We ﬁrst analyze some lower bound of

the competitive ratios of truthful mechanisms in several ad-

versary models in Section 4 for a various adversary models.

In Section 5, we ﬁrst assume that the adversary is arrival-

sequence adaptive online, i.e., the valuations are not selected

by the adversary and the adversary can only determine the

arrival sequence of users. We present a sequence of strategy-

proof online auction mechanisms and analyze the compu-

tational and economic properties of these mechanisms. In

Section 7, we report the extensive numerical evaluations of

performances of our proposed mechanisms compared with

some related mechanisms proposed in the literature. We

conclude the paper in Section 8 with the discussion of some

future research questions.

2 RELATED WORK

In the era of big data, data pricing has attracted consider-

able attentions and a series of data pricing strategies from

different perspectives have been proposed. Niu et al. [47]

studied trading time-series data by compensating the data

owners for their privacy losses, Yu et al. [12] proposed data

pricing strategies based on data quality. Zheng et al. [38]

investigated online pricing mechanisms for version-based

data trading. In this work, we focus on designing the

online mechanism for trading time-sensitive valued data-

A closely related problem is to choose the maximum

from a sequence. This well known problem is also called

the secretary problem or optimal stopping problem. Pre-

vious works [55], [56] have studied how to select an ele-

ment with a discount function. However, these approaches

are not designed in the scenario where the participating

agents could be selﬁsh, thus, these methods cannot guar-

antee truthfulness when the valuations of bidders are pri-

vate information. The design of proﬁt-maximizing truthful

online auctions for digital goods, or information, goods

such as electronic books, software, and digital copies of

music have been extensively explored in academic area.

Goldberg [57] is the ﬁrst to introduce the notion of com-

petitive auctions. They studied a class of ofﬂine single-

round, sealed-bid auctions for items in unlimited supply,

and proposed truthful, constant-competitive auctions via

random sampling. Bar-Yossef et al. [58] studied the com-

petitive incentive-compatible online auctions for unlimited

digital goods. When considering limited supply, Hajiaghayi

et al. [53] presented constant-competitive truthful online

mechanisms with respect to the ofﬂine Vickrey for revenue,

using a two-stage sampling-accepting process. In addition,

a number of previous works [38], [59], [60], [61] explored

online pricing mechanisms based on the multi-armed bandit

problem. However, these mechanisms did not take time-

sensitive valuations into consideration.

Since data has some new peculiar properties, i.e., time-

sensitive valuations, previous works can not be applied

any more. When we take the time-sensitive valuations into

consideration, the problem become more challenging. Some

recent pricing models started to focus on goods whose

valuations are time sensitive. Lavi et al. [62] studied the

allocation of multiple identical items that they “expire” at

different times and proposed online auction mechanisms to

approximately maximize the social welfare. Wu et al. [54]

presented a strategy-proof online auction with discounting

valuations, but they assume the discounting functions are

known to the seller, and their objective is to maximize social

welfare instead of revenue. They assume that the items can

be sold up to ghighest bidding agents in each time slot t. Xu

et al. [51] focused on pricing private personal data via multi-

armed bandit approach with time-variant rewards. Mao et

al. [52] designed an online pricing mechanism based on the

feature of discounting valuations with unlimited number

of copies. Romano [63] proposed posted-pricing mecha-

nisms with unknown time-discounted valuations drawn

from some distributions. However, when we consider sell-

ing only one copy to some carefully selected buyers, the

problem model is totally different and it becomes more

challenging due to the short of opportunities of learning

future information.

3 TRADING MODEL AND PROBLEM DEFINITION

In this section, we present the system models of trading data

related product such as data or data-copyright with time

discounting valuations, and introduce some related deﬁ-

nitions and concepts from algorithmic mechanism design.

There are three parties in our model: data owner, data seller

and data consumer (i.e., buyer), see Figure 1 for illustration.

The seller collects data from the owners and consumers

buy some data from the seller to facilitate their data-driven

services. Potentially all these transactions are conducted on

a data sharing/trading platform.

Seller 1

Data broker

Buyer 1

bid 2

Buyer N

Buyer 2

Seller 2

Seller M

Data value

decrease

Data collection Winner selection

Dataset

Management

Different buyers have

different valuations

Upload

dataset 1

Upload

dataset 2

Time t

discount value d(t)







Dataset

to be sold

Fig. 1. System model for data trading.

Data broker: Suppose the data broker has a set of

datasets Dand each dataset contains a set of organized data

items after some process. e.g., data cleaning and labeling.

Each dataset is associated with a description3for exhibition,

and the data buyers decide which data set to buy according

to the description. For each dataset D∈ D, the broker needs

to take into account of three kinds of cost: initial cost in data

collection and cleaning; maintaining cost in the procedures

of data storage, organization, management, etc.;trading cost

including the cost for copy and others. We use Cs

i, Cs

m, Cs

to denote dataset Ds’s initial, maintaining and trading cost

respectively. For the sake of simplicity, we assume the total

cost is a ﬁxed and known constant in our system. The

objective of the data broker is to sell the data to potential

buyers to gain maximum proﬁt, or to maximize the social

welfare.

Data value: It is very complicated to estimate the data

value in practice. For example, different data consumers of-

ten have different evaluations on the same dataset and thus

report different prices. Data broker can estimate dataset’s

value by data quality, data function, market survey or other

types of data value. Each potential data buyer ihas his own

data evaluation viaccording to data application scenario.

A data buyer may estimate data value by current market

situation and future forecast. For instance, the data value

may change following a non-increasing function of time d(t)

in reality. Consequently, it is reasonable to assume that the

broker will stop providing the dataset Dat some time te,

when the dataset’s market value is lower than the cost for

holding it. In our model, we assume that d(t)is known

in advance to data seller and data buyers. Actually, this is

a reasonable assumption in practice; for example, we can

learn d(t)by sufﬁcient survey in the market.

Data buyers: In some trading scenarios, a buyer may

cooperate with others to get lower purchasing cost, for

example, share digital data (e.g. movie, music) with other

potential buyers. Here we assume there are no collusions be-

tween buyers/bidders; actually we assume that the buyers

compete with each other and do not want to share their

3. The description may include the data content, time of generation,

quality, volume, etc.. Methods of data exhibition is another challenging

but important issue in data trading market.

target datasets with others. For a speciﬁc dataset D, the j-

th arrived buyer i, arriving at time tj, has a private initial

valuation vi, representing the maximum price he is willing

to pay; he has the utility vi·d(tj)−p(tj), if picked by the

mechanism, where p(tj)is the payment by buyer iat the

time tj. All buyers are assumed to be selﬁsh, that is, to max-

imize the utility, each buyer will manipulate his reported

price rjstrategically. We also assume that the buyers have

the full knowledge of the auctioneer’s mechanism when

they bid.

3.1 Trading Model

For simplicity, we focus on the selling of one speciﬁc dataset,

or one speciﬁc data product. Assume that there are nbuyers

U={1,2,· · · , i, i+1,· · · , n}for this data who arrive online

in a random order and follow some random process, such

as a Poisson process with the arrival rate λ. To focus on

the design of truthful mechanisms, without worrying about

the subtle differences caused by the different arrival times

from a random arrival process, in this work we assume

that users’s arrival follows a ﬁxed sequence of time instances.

This sequence of time instances are assumed to be pre-

determined, which could be generated by some random

process in advance. For the sake of simple analysis, let

T={t1, t2,· · · , ti, ti+1,· · · ,}be the time sequence when

the i-th arrived user will arrive at time ti. In this work,

we use a set v={v1, v2, v3,· · · , vn−1, vn}to denote the

set of arbitrary given initial valuations of users, i.e., the

user ihas an initial valuation vi. An arrival sequence

is a mapping πfrom Tto U,i.e., the j-th arrived user

is π(j). Given an arrival sequence πwe use a vector

π(v) = ~

v= [vπ(1), vπ(2), vπ(3),· · · , vπ(n−1), vπ(n)]to denote

a given sequence of initial valuations of users arrived in

order π. Let T= [0, te]denote the time horizon of the

auction, here time 0is the starting time of the auction, and te

is the time when the seller stops selling the data. Each buyer

ihas a private initial valuation vifor the data at the time of

data production. The buyers’ initial valuations are arbitrary

unknown without any prior knowledge, and the buyers have

the full knowledge of the auctioneer’s mechanism when

they bid. We model the interactive process between the

seller and the buyers as an online auction.

Auction Mechanism Setting: In the auction mechanism

setting, we assume the following. We assume that the jth-

arrived buyer has a user ID π(j). Here πis a mapping from

time tjto a user with ID π(j). For simplicity of notations,

sometimes we assume that π(j) = jif no confusion is

caused. When the j-th buyer arrives, he submits a price

(i.e., bid) rjrepresenting the maximum reported price he is

willing to pay. For each j-th arrived buyer, let tjdenote his

arrival time instance and vjbe his private initial valuation.

We say hj=vj·d(tj)is the true maximum value of the

j-th buyer (actually with an ID π(j)) arrived at time tj

for the data product. If rj=hj, we say that the user jis

truthful. In this work, we assume that the discount function

d(t)satisﬁes that 0< d(t)≤1for any value t≥0. In

other words, for any user i, the valuation of the product

cannot exceed its initial valuation vi. After receiving the

bid, the seller must decide whether to sell the data or not

immediately and the decision is irrevocable. Here, we study

a real trading scenario that the buyers are competitive and

there are no collusions among them. In addition, we assume

that all buyers are rational: each buyer jarrived at time tj

reports his price rjstrategically to maximize the utility. Then

buyer jarrived at time tjhas the utility:

uj=vj·d(tj)−pj,if picked as winner and pay pj;

0,otherwise. (1)

where pjis the payment by j-th arrived buyer if he is picked

by the mechanism at his arrival time tj. Let E[uj]denote the

expected utility of user j, where E[·]is the expectation over

the mechanism’s randomizations if it has any.

Posted-Price Mechanism Setting: In this case, the mech-

anism decides a posted price ptfor all users arrived starting

from tand hereafter. The seller may dynamically set mul-

tiple posted-prices pt1,pt2,pt3,· · · ,ptm. When a buyer j

arrives at a time t∈[ti, ti+1), this buyer jis accepted as the

winner iff his reported price rj≥pti. The winner will be

charged a price pti. The mechanism stops if one winner has

been determined. If g≥1copies of the data will be sold,

the mechanism stops if gcopies have been sold or all users

have been processed.

Revenue-Maximizing Objectives: We focus on studying

the seller’s revenue R, i.e., the sum of the winning buyers’

payments minus the seller’s total cost. For simplicity, we

assume the data cost is constant and ﬁxed, and we also

assume that no two buyers arrive at the same time. If

multiple buyers satisfy our decision rule at the same time,

our mechanism can be modiﬁed by selecting the one who

reports the highest price. Formally, we aim to maximize the

revenue Rof the mechanism

(R=Pn

j=1 yj∗pj

s.t. Pn

j=1 yj≤1, yj∈ {0,1}(2)

Here the reported price vector r, allocation vector y, and

the payment vector pare initialized with the zero vector

(0,0,...,0) and updated online with each arrived buyer.

The mechanism Mcomputes (y,p)online based on the

received report price information r,i.e.,M(r, d(t)) = (y,p),

Notice that mechanism, composed of the payment rule p

and the allocation rule y, must be strategy-proof.

1) y= (y1, y2, . . . , yn)is the allocation rule, where yj= 1

indicates that the seller accepts the j-th arrived buyer

as the winner; yj= 0 rejects. In this setting, we only

choose one winner, i.e.,Pn

j=1 yj≤1.

2) p= (p1, p2, . . . , pn)is the payment rule, where pjis the

value paid by the j-th arrived buyer.

For the convenience of our understanding, we summa-

rize some important notations in Table 1.

3.2 Adversary Models and Competitive Ratio

For online mechanism design, there are some common

models about the adversary (the power of the adversary

from weakest to weak, to medium, to strong) that could

affect the performance of the mechanism:

1) Oblivious adversary (also called weakest adversary): The

oblivious adversary knows the online mechanism, but

not the coin toss of the mechanism if there is any. The

adversary has to generate the entire request sequence

in advance before any requests are processed by the

TABLE 1

Notations and abbreviations used in this work.

Notation Description

v,orπ(v)A vector of the valuations, i.e., a permutation

πof the initial valuation set v.

tjThe arrival time of j-th arrived user in a

given arrival time-sequence.

rjThe reported price of j-th arrived user in a

given arrival sequence.

djThe discount value of j-th arrived user for

a given discount function and arrival time-

sequence.

r(j)(π)The j-th largest report price in sequence π,

sometimes abbreviated as r(j).

r(j)(Π) The expected value of j-th largest report

price given the set of arrival sequence Π.

vπ(k)The valuation of the k-th arrived user in an

arrival sequence π.

vkThe k-th largest initial valuation in the valu-

ation set V.

(k)(π)The k-th largest initial valuation of users in

the class cin the arrival sequence π.

max The maximum discount value in class c.

min The minimum discount value in class c.

ˆcThe number of reserved discount classes.

ncThe number of users in a discount class c.

TcThe time-interval of the discount class c.

IcThe discount values interval of the class c.

c(k)(π)The class id where the k-th largest report

price r(k)is from in arrival sequence π.

%(M)The competitive ratio of a mechanism M

against a fully adaptive-online adversary.

%d(M)The competitive ratio of a mechanism M

against a valuation adaptive-online adversary.

v(M)The (worst case) competitive ratio of a mech-

anism Magainst a discount-function adaptive-

online adversary.

ρv,d(M)The expected competitive ratio of a mecha-

nism Magainst an arrival-sequence adaptive-

ofﬂine adversary.

online mechanism. The adversary is charged the cost

of the optimum ofﬂine algorithm for that sequence.

Notice that the adversary could be valuation oblivious

or discount-function oblivious, or both.

2) Adaptive-online adversary (also called medium adver-

sary): This adversary may observe the online mech-

anism and generate the next request based on the

algorithm’s (randomized) answers to all previous re-

quests. The adversary must serve each request online,

i.e., without knowing the random choices made by the

online algorithm on the present or any future request.

This adversary must make its own decision before it is

allowed to know the decision of the online mechanism.

3) Adaptive-ofﬂine adversary (also called strong adversary):

This adversary knows everything of the mechanism

design, even the random number generator used by

the randomized mechanism. This adversary is so strong

that randomization does not help against it. This adver-

sary is allowed to make its own decision after it knows

the decision of the mechanism. The adversary then

generates a request’s values and its arrival sequence

adaptively. However, it may serve the sequence to the

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

1CompetitiveOnlineTruthfulTime-Sensitive-ValuedDataAuctionShuangshuangXue,StudentMember,IEEE,Xiang-YangLi,Fellow,IEEE,AbstractDigitalproduct,suchasoriginaldataanddata-copyright,asanirreplaceableformofdataproducts,canbetransferredbytheownertopotentialuserstomaximizeitspotentialusagewhileprotectingth...

展开>> 收起<<

1 Competitive Online Truthful Time-Sensitive-Valued Data Auction.pdf

共33页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

1 Competitive Online Truthful Time-Sensitive-Valued Data Auction

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: