Sample-driven online selection

Abstract

In this thesis, we study from a sample-based perspective four online selection problems that generalize two classic models: the secretary problem and the prophet inequality. In the first chapter, we propose a model we call p-DOS, that generalizes both the secretary problem and the i.i.d. prophet inequality. In this problem, an adversary chooses a set of numbers, and each of them is sampled independently with probability p and revealed to us beforehand. The remaining numbers are revealed sequentially and we make irrevocable stop/continue decisions, with the objective of maximizing the expectation of the selected number. We characterize the optimal algorithm for all values of p, and show that its performance guarantee continuously interpolates between 1/e and 0.745, the optimal performances in the secretary problem and the i.i.d. prophet inequality. In the second chapter, we propose a similar model called ROSp, where the objective is to maximize the probability of selecting the best number of the non-sampled numbers. Again, we find the optimal performance and show it gracefully interpolates between 1/e and 0.5801, the optimal guarantees in the secretary problem and the i.i.d. secretary problem. The third chapter studies fairness and bias in the context of the secretary problem. We introduce a new variant where each candidate belongs to a certain group. We assume comparisons between candidates of different groups are arbitrarily biased, so we analyze the optimal algorithm that only compares candidates of the same group. We show that this optimal policy is fair in a fundamental sense, achieving a balance between different groups. We also propose a sample-based variant of this problem, inspired in the ROSp model. In the fourth chapter we study Online Combinatorial Auctions, an important generalization of the prophet inequality to multiple selection. We are given m items and we set a price for each of them. Then, a sequence of agents that arrive one by one buy their preferred set from the remaining items at the given prices. We assume we know the distributions from which the valuations of the buyers are drawn. We show via a novel fixed-point argument that the optimal prices achieve a (d+1)-approximation to the optimal social welfare in hindsight, where d is the size of the largest set any buyer would like to buy. We show that if we have only samples of the values instead of the distributions, we still can compute prices that achieve a (d + 1 + ε)-approximation, and moreover, we can do this in polynomial time.