The Generalized Magician Problem under Unknown Distributions and Related Applications

The Generalized Magician Problem under Unknown Distributions and Related Applications
复制标题

DOI：
10.5555/3535850.3535986
复制
发表时间：
2022
期刊：
--
影响因子：
--
通讯作者：
A. Srinivasan;Pan Xu
A. Srinivasan;Pan Xu
中科院分区：
其他
文献类型：
--
作者：
A. Srinivasan;Pan Xu

文献摘要

相似文献

魔术师问题（MP）及其推广，广义魔术师问题（GMP），由Alaei等人（APPROX-RANDOM 2013）和Alaei（SICOMP 2014）引入，并已被用作许多困难问题的在线算法设计中的强大成分，如k -选择先知不等式，贝叶斯组合拍卖中的机制设计和广义分配问题。这里的对抗模型本质上是一个遗忘的对手。在本文中，我们介绍了GMP（MP）在两种不同的到达设置下的推广（通过使对手更强）：未知独立相同分布（UIID）和未知对抗分布（UAD）。不同的对手模型捕获一系列的到达模式。对于GMP下的UIID，我们证明了一个自然的贪婪算法贪婪是最优的。对于MP在UIID下的情况，我们证明了Greedy的最优性能为1 − B B B！e B ≥ 1 − 1 2 πB，其中B是预算，并给出了随机报酬在线B -匹配的应用.对于UAD下的GMP，我们提出了一个简单的算法，这是近最佳的所有非自适应算法。我们考虑MP下UAD B = 1的简单情况下，并给出了一个精确的表征各自的最佳自适应和最佳非自适应算法的任何有限的时间范围。我们提供了一个在UAD下的MP的例子，在这个例子上，即使时间范围T = 4，在对抗秩序下的经典MP和UAD下的MP之间也存在可证明的差距。
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 de-sign 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.