The Generalized Magician Problem under Unknown Distributions and Related Applications

Aravind Srinivasan, Pan Xu

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 (equation presented) BB of 1 - B!eB ≥ 1 - √21π 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.

Original languageEnglish (US)
Title of host publicationInternational Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Number of pages9
ISBN (Electronic)9781713854333
StatePublished - 2022
Event21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022 - Auckland, Virtual, New Zealand
Duration: May 9 2022May 13 2022

Publication series

NameProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
ISSN (Print)1548-8403
ISSN (Electronic)1558-2914


Conference21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022
Country/TerritoryNew Zealand
CityAuckland, Virtual

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering


  • magician problem
  • online algorithms
  • prophet inequality

Cite this