Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Online Pro t-Maximizing Sampling Auctions For DigitalGoods
Speaker:Alkmini Sgouritsa
coming from:International Max Planck Research School for Computer Science - IMPRS
Speakers Bio:
Event Type:PhD Application Talk
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:Public Audience
Date, Time and Location
Date:Monday, 8 October 2012
Duration:60 Minutes
Building:E1 4
Auctions are publicly and privately seen in several contexts and almost anything can

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
o ered 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 o ered 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.

Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Created:Marc Schmitt/MPI-INF, 10/05/2012 04:12 PM Last modified:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Marc Schmitt, 10/05/2012 04:14 PM -- Created document.