Online Prot-Maximizing Sampling Auctions For DigitalGoods

be sold in an auction. The online prot-maximizing sampling auctions for digital goods
are multiple-round auctions, where the items for selling are digital, identical and unlimited
goods and the objective is the maximization of the seller's revenue. In each round, only one
bidder arrives, bids once and for one item and gets at most one. In this setting, we further
assume uniformly random arrivals of the bidders and adversarial selection of bid values.
There are several mechanism designed for computing the prices, at which the items are
oered to the bidders in this kind of auctions. We studied two such mechanisms: the online
Sampling Cost Sharing (SCS) and the Best Price So Far (BPSF) auctions and we focused
on determining their competitive ratio with respect to the benchmark F(2), i.e. the optimal
single price sale prot with at least two bidders getting the item.
We proved that the competitive ratio of the online SCS auction is exactly 8. An upper
bound on the online SCS competitive ratio as a function of k was claimed in the literature,
with k dened as the number of items sold when all oered prices equal the optimal single
price with at least two bidders getting the item. We found a counterexample, for which this
upper bound was violated. Instead, we gave the tight online SCS competitive ratio as a
function of k.
Concerning the BPSF auction, we simulated it by generating the bid values using spe-
cic patterns. The ratio between the F(2) and the revenue of this auction was computed.
In support of the conjecture in the literature that the BPSF competitive ratio is 4, our
computed ratios didn't exceed 4. Moreover, our simulations indicate promising hypotheses
about BPSF properties. Further simulations and investigation are required for strengthening
these evidences.