Stochastic Probing with Increasing Precision

Hoefer, Martin; Schewior, Kevin; Schmand, Daniel

doi:10.24963/ijcai.2021/560

Stochastic Probing with Increasing Precision

Martin Hoefer, Kevin Schewior, Daniel Schmand

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 4069-4075.

https://doi.org/10.24963/ijcai.2021/560

Keywords

Agent-based and Multi-agent Systems: Algorithmic Game Theory
Planning and Scheduling: Planning under Uncertainty
Agent-based and Multi-agent Systems: Resource Allocation

Abstract

We consider a selection problem with stochastic probing. There is a set of items whose values are drawn from independent distributions. The distributions are known in advance. Each item can be \emph{tested} repeatedly. Each test reduces the uncertainty about the realization of its value. We study a testing model, where the first test reveals if the realized value is smaller or larger than the median of the underlying distribution. Subsequent tests allow to further narrow down the interval in which the realization is located. There is a limited number of possible tests, and our goal is to design near-optimal testing strategies that allow to maximize the expected value of the chosen item. We study both identical and non-identical distributions and develop polynomial-time algorithms with constant approximation factors in both scenarios.

Martin Hoefer, Kevin Schewior, and Daniel Schmand. 2021. Stochastic Probing with Increasing Precision. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 4069–4075. https://doi.org/10.24963/ijcai.2021/560

@inproceedings{ijcai2021p560,
  title     = {Stochastic Probing with Increasing Precision},
  author    = {Hoefer, Martin and Schewior, Kevin and Schmand, Daniel},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {4069--4075},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/560},
  url       = {https://doi.org/10.24963/ijcai.2021/560},
}

TY  - CPAPER
TI  - Stochastic Probing with Increasing Precision
AU  - Hoefer, Martin
AU  - Schewior, Kevin
AU  - Schmand, Daniel
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 4069
EP  - 4075
DO  - 10.24963/ijcai.2021/560
UR  - https://doi.org/10.24963/ijcai.2021/560
ER  -