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@www.u-gov-ricerca.uniroma1.it
DTSTAMP:20260405T115910Z
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:http://www.u-gov-ricerca.uniroma1.it/node/27370
END:VEVENT
END:VCALENDAR