The Generalized Magician Problem under Unknown Distributions and Related Applications

The Magician Problem (MP) and its generalization, the Generalized Magician Problem (GMP), were introduced by Alaei et al. (APPROX-RANDOM 2013) and Alaei (SICOMP 2014) and have been used as powerful ingredients in online-algorithm design for many hard problems such as the k-choice prophet inequality, mechanism design in Bayesian combinatorial auctions, and the generalized assignment problem. The adversarial model here is essentially that of an oblivious adversary. In this paper, we introduce generalizations of GMP (MP) under two different arrival settings (by making the adversary stronger): unknown independent identical distributions (UIID) and unknown adversarial distributions (UAD). Different adversary models capture a range of arrival patterns. For GMP under UIID, we show that a natural greedy algorithm Greedy is optimal. For the case of MP under UIID, we show that Greedy has an optimal performance of 1-B B B!e B ≥ 1-1 √ 2π B , where B is the budget, and show an application to online B-matching with stochastic rewards. For GMP under UAD, we present a simple algorithm, which is near-optimal among all non-adaptive algorithms. We consider the simple case of MP under UAD with B = 1, and give an exact characterization of the respective optimal adaptive and optimal non-adaptive algorithms for any finite time horizon. We offer an example of MP under UAD on which there is a provable gap between the classical MP under adversarial order and MP under UAD even with a time horizon T = 4.