AdONE Seminar: Alexandros Tsigonias-Dimitriadis (TUM)

Events

Alexandros Tsigonias-Dimitriadis (TUM, AdONE): "On Prophets and Secretaries with Binomial Sampling" – Suppose that we want to pick the maximum value of a sequence of n elements and the only information that we have is the cardinality n. The elements, after an adversary assigns (non-negative) values to them, start arriving one by one in a uniformly random order. Upon each arrival, we need to make an immediate and irrevocable decision of whether to accept an element or continue to the next. Our goal is to design an algorithm which maximizes the probability of picking the maximum element. This is the so-called secretary problem, a fundamental result in online decision-making. It is well known that there exists an elegant algorithm which picks the maximum with probability 1/e, and this is the best possible.

In this paper we study a data-driven variant of the classical problem: The cardinality of the sequence is unknown and both the values and the order are adversarial, but we are given a set of samples in advance. These samples are drawn from the adversarial input and they represent historical data available to us. The remaining part of the input arrives online, and we want to pick the maximum element. We present a single-threshold algorithm which accepts the first value that is above the k’th largest sample, for a suitable chosen k. Although very simple, we show that this algorithm is optimal. To do so, we introduce a new technique, which is based on interpreting the model as a game on a graph. This approach might be of independent interest.

Next, we explore the “prophet variant” for this model. The performance measure now is the worst-case ratio between the expected value that the algorithm gets and the expected optimal value of the online set. Again, we examine the performance that simple, deterministic algorithms achieve.

This is ongoing work with José Correa, Laurent Feuilloley and Tim Oosterwijk.

Date: Monday 11^th of May 2020, starting at 2 p.m.

The seminar will take place online. If you are a TUM-member and want to join, though you have not received the link via e-mail, please contact adone@tum.de

◄ Back to: Events