Seminar PhD Data Science
Speaker:
Paul Duetting, Johannes Bruestle
Data dell'evento:
Martedì, 14 November, 2023 - 15:30
Luogo:
Room B203, DIAG, Via Ariosto 25
Contatto:
dottoratods@diag.uniroma1.it
When: 14 November 2023
Where: Room B203, DIAG, Via Ariosto 25.
Program:
15:30 Online Combinatorial Auctions with Few Samples
Speaker: Paul Duetting, Google Research, Zurich
16:15 The Competition Complexity of Prophet Inequalities
Speaker: Johannes Bruestle, London School of Economics and Political Science, London
Link Zoom:
(Meeting ID: 871 1857 6608 Passcode: 107050)
-------------
Abstracts:
Online Combinatorial Auctions with Few Samples
In online combinatorial auctions, n bidders sequentially arrive, each with a combinatorial valuation (such as submodular/XOS) over m indivisible items. The aim is to immediately allocate a subset of the remaining items to maximize the total welfare, defined as the sum of bidder valuations. A long line of work has studied this problem when the bidder valuations come from known distributions. In particular, we know 2-competitive algorithms/mechanisms that set a fixed price for each item and the arriving 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)-competitive algorithms when only a handful of samples from the underlying distributions are provided.
Our first main contribution shows that a mere single sample from each bidder distribution is sufficient to yield an O(1)-competitive 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 first approach does not provide an online truthful mechanism. Our second main contribution shows that a polynomial number of samples suffices to yield an O(1)-competitive online truthful mechanism for submodular/XOS valuations. This result is based on a generalization of the median-based algorithm for the single-item prophet inequality problem to combinatorial settings with multiple items.
(Joint work with Thomas Kesselheim, Brendan Lucier, Rebecca Raiffenhauser, and Sahil Singla.)
The Competition Complexity of Prophet Inequalities
Over the past decade, the prophet inequality approach has emerged as a new paradigm for the analysis of online algorithms, offering to strengthen the online algorithm by providing it with distributional information about the input. An alternative, well-established approach to strengthening online algorithms is that of resource augmentation, where the online algorithm is compared to the best-possible offline solution, which is handicapped by fewer resources. In this work, we combine the two directions by studying the classic (single-choice) prophet inequality problem through a resource augmentation lens.
In our model, the online algorithm sees $k$ copies of a prophet inequality instance, where every instance has $n$ values drawn independently from distributions $F_1, \ldots, F_n$. To evaluate the performance of an algorithm in this model, we use the competition complexity metric introduced in the context of pricing and auctions. We compare the expected value achieved by the online algorithm on $k$ copies to the expected maximum value on a single copy. Given $\varepsilon > 0$, we ask how big $k$ has to be, such that the online algorithm on $k$ copies is guaranteed to obtain a $(1-\varepsilon)$-approximation to the expected maximum on a single copy.
(Joint work with Jose Correa, Paul Duetting, Tomer Ezra, Michal Feldman, and Victor Verdugo.)
gruppo di ricerca: