BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Date iCal//NONSGML kigkonsult.se iCalcreator 2.20.2//
METHOD:PUBLISH
X-WR-CALNAME;VALUE=TEXT:Eventi DIAG
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:STANDARD
DTSTART:20231029T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20240331T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:calendar.27370.field_data.0@diag.uniroma1.it
DTSTAMP:20240527T184515Z
CREATED:20231106T131021Z
DESCRIPTION:When: 14 November 2023Where: Room B203\, DIAG\, Via Ariosto 25.
Program: 15:30 Online Combinatorial Auctions with Few SamplesSpeaker: Pau
l Duetting\, Google Research\, Zurich16:15 The Competition Complexity of P
rophet InequalitiesSpeaker: Johannes Bruestle\, London School of Economics
and Political Science\, London Link Zoom: https://uniroma1.zoom.us/j/8711
8576608pwd=NTR1VEZ2QUp3MGhsQk5uSFU2eVZFZz09(Meeting ID: 871 1857 6608 Pass
code: 107050) ------------- Abstracts: Online Combinatorial Auctions with
Few SamplesIn online combinatorial auctions\, n bidders sequentially arriv
e\, each with a combinatorial valuation (such as submodular/XOS) over m i
ndivisible items. The aim is to immediately allocate a subset of the remai
ning items to maximize the total welfare\, defined as the sum of bidder v
aluations. A long line of work has studied this problem when the bidder va
luations come from known distributions. In particular\, we know 2-compet
itive algorithms/mechanisms that set a fixed price for each item and the a
rriving bidders take their favorite subset of the remaining items at these
prices. However\, these studies assume that the distributions are given
to the algorithm as input. This paper explores the possibility of O(1)-c
ompetitive algorithms when only a handful of samples from the underlying d
istributions are provided.Our first main contribution shows that a mere si
ngle sample from each bidder distribution is sufficient to yield an O(1)-c
ompetitive algorithm for submodular/XOS valuations. This result leverages
a novel extension of the secretary-style analysis\, employing the sample
to have the algorithm compete against itself. Although online\, this fir
st approach does not provide an online truthful mechanism. Our second mai
n contribution shows that a polynomial number of samples suffices to yield
an O(1)-competitive online truthful mechanism for submodular/XOS valuati
ons. This result is based on a generalization of the median-based algori
thm for the single-item prophet inequality problem to combinatorial settin
gs with multiple items. (Joint work with Thomas Kesselheim\, Brendan Luci
er\, Rebecca Raiffenhauser\, and Sahil Singla.) The Competition Complexity
of Prophet InequalitiesOver the past decade\, the prophet inequality appr
oach has emerged as a new paradigm for the analysis of online algorithms\,
offering to strengthen the online algorithm by providing it with distribu
tional information about the input. An alternative\, well-established appr
oach to strengthening online algorithms is that of resource augmentation\,
where the online algorithm is compared to the best-possible offline solut
ion\, which is handicapped by fewer resources. In this work\, we combine t
he two directions by studying the classic (single-choice) prophet inequali
ty problem through a resource augmentation lens.In our model\, the online
algorithm sees $k$ copies of a prophet inequality instance\, where every i
nstance has $n$ values drawn independently from distributions $F_1\, \ldot
s\, F_n$. To evaluate the performance of an algorithm in this model\, we u
se the competition complexity metric introduced in the context of pricing
and auctions. We compare the expected value achieved by the online algorit
hm on $k$ copies to the expected maximum value on a single copy. Given $\v
arepsilon > 0$\, we ask how big $k$ has to be\, such that the online algor
ithm on $k$ copies is guaranteed to obtain a $(1-\varepsilon)$-approximati
on to the expected maximum on a single copy. (Joint work with Jose Correa\
, Paul Duetting\, Tomer Ezra\, Michal Feldman\, and Victor Verdugo.)
DTSTART;TZID=Europe/Paris:20231114T153000
DTEND;TZID=Europe/Paris:20231114T153000
LAST-MODIFIED:20231106T131454Z
LOCATION:Room B203\, DIAG\, Via Ariosto 25
SUMMARY:Seminar PhD Data Science - Paul Duetting\, Johannes Bruestle
URL;TYPE=URI:https://diag.uniroma1.it/node/27370
END:VEVENT
END:VCALENDAR