Goran Zuzic on Byzantine Secretary Problem - YouTube CMU Theory

CMU Theory lunch talk from February 6, 2019 by Goran Zuzic on Byzantine Secretary Problem. In the classical secretary problem, a sequence of n elements arrive in a uniformly random order. The goal is to maximize the probability of selecting the largest element (or to maximize the expected value of the selected item). This model captures applications like online auctions, where we want to select the highest bidder. In many such applications, however, one may expect a few outlier arrivals that are adversarially placed in the arrival sequence. Can we still select a large element with good probability? Dynkin's popular 1/e -secretary algorithm is sensitive to even a single adversarial arrival: if the adversary gives one large bid at the beginning of the stream, the algorithm does not select any element at all. In this talk we introduce the Byzantine Secretary problem where we have two kinds of elements: green (good) and red (bad). The green elements arrive uniformly at random. The reds arrive adversarially. The goal is to find a large green element. It is easy to see that selecting the largest green element is not possible even when a small fraction of the arrival is red, i.e., we cannot do much better than random guessing. Hence we introduce the \emph{second-max} benchmark, where the goal is to select the second-largest green element or better. This dramatically improves our results. We give an explicit polylog∗n competitive algorithm, using a multi-layered bucketing scheme that adaptively refines our estimates of second-max as we see more elements. For the multiple secretary problem, where we can pick up to r secretaries, we show constant competitiveness as long as r is large enough. For this, we give an adaptive thresholding algorithm that raises and lowers thresholds depending on the quality and quantity of recently selected elements.

Goran Zuzic on Byzantine Secretary Problem - YouTube
2 Likes	2 Dislikes
128 views views	341 followers
People & Blogs	Upload TimePublished on 8 Feb 2019