research-article

Pandora's Box Problem with Order Constraints

Authors:

Shant Boodaghians,

Federico Fusco,

Stefano LeonardiAuthors Info & Claims

EC '20: Proceedings of the 21st ACM Conference on Economics and Computation

Pages 439 - 458

https://doi.org/10.1145/3391403.3399501

Published: 13 July 2020 Publication History

Abstract

The Pandora's Box Problem, originally formalized by Weitzman in 1979, models selection from a set of options each with stochastic parameters, when evaluation (i.e. sampling) is costly. This includes, for example, the problem of hiring a skilled worker, where only one hire can be made, but the evaluation of each candidate is an expensive procedure.

Weitzman showed that the Pandora's Box Problem admits a simple and elegant solution which considers the options in decreasing order of the value it which opening has exactly zero marginal revenue. We study for the first time this problem when the order in which the boxes are opened is constrained, which forces the threshold values to account for both the depth of search, as opening a box gives access to more boxes, and breadth, as there are many directions to explore in. Despite these difficulties, we show that greedy optimal strategies exist and can be efficiently computed for tree-like order constraints.

We also prove that finding approximately optimal adaptive search strategies is NP-hard when certain matroid constraints are used to further restrict the set of boxes which may be opened, or when the order constraints are given as reachability constraints on a DAG. We complement the above result by giving approximate adaptive search strategies based on a connection between optimal adaptive strategies and non-adaptive strategies with bounded adaptivity gap for a carefully relaxed version of the problem.

References

[1]

Aris Anagnostopoulos, Ilan Reuven Cohen, Stefano Leonardi, and Jakub Lacki. 2019. Stochastic Graph Exploration. In ICALP (LIPIcs), Vol. 132. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 136:1--136:14.

[2]

Hedyeh Beyhaghi and Robert Kleinberg. 2019. Pandora's Problem with Nonobligatory Inspection. In EC. ACM, 131--132.

[3]

Domagoj Bradac, Sahil Singla, and Goran Zuzic. 2019. (Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing. In APPROX-RANDOM (LIPIcs), Vol. 145. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 49:1--49:21.

[4]

Andrea E. F. Clementi and Luca Trevisan. 1999. Improved Non-Approximability Results for Minimum Vertex Cover with Density Constraints. Theor. Comput. Sci., Vol. 225, 1--2 (1999), 113--128.

Digital Library

[5]

Laura Doval. 2018. Whether or not to open Pandora's box. J. Econ. Theory, Vol. 175 (2018), 127--158.

[6]

Ioana Dumitriu, Prasad Tetali, and Peter Winkler. 2003. On Playing Golf with Two Balls. SIAM J. Discret. Math., Vol. 16, 4 (2003), 604--615.

Digital Library

[7]

Hossein Esfandiari, Mohammad Taghi Hajiaghayi, Brendan Lucier, and Michael Mitzenmacher. 2019. Online Pandora's Boxes and Bandits. In AAAI. AAAI Press, 1885--1892.

[8]

Moran Feldman. 2019. Guess Free Maximization of Submodular and Linear Sums. In WADS (Lecture Notes in Computer Science), Vol. 11646. Springer, 380--394.

[9]

Esther Frostig and Gideon Weiss. 2016. Four proofs of Gittins' multiarmed bandit theorem. Annals OR, Vol. 241, 1--2 (2016), 127--165.

[10]

Chenghao Guo, Zhiyi Huang, Zhihao Gavin Tang, and Xinzhi Zhang. 2019. Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problem. CoRR, Vol. abs/1911.11936 (2019).

[11]

Anupam Gupta, Viswanath Nagarajan, and Sahil Singla. 2017. Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions. In SODA. SIAM, 1688--1702.

[12]

Chris Harshaw, Moran Feldman, Justin Ward, and Amin Karbasi. 2019. Submodular Maximization beyond Non-negativity: Guarantees, Fast Algorithms, and Applications. In ICML (Proceedings of Machine Learning Research), Vol. 97. PMLR, 2634--2643.

[13]

Joseph B Kadane. 1969. Quiz show problems. J. Math. Anal. Appl., Vol. 27, 3 (1969), 609--623.

[14]

Joseph B Kadane, Herbert A Simon, et al. 1977. Optimal strategies for a class of constrained sequential problems. The Annals of Statistics, Vol. 5, 2 (1977), 237--255.

[15]

Godfrey Keller and Alison Oldale. 2003. Branching bandits: a sequential search process with correlated pay-offs. J. Econ. Theory, Vol. 113, 2 (2003), 302--315.

[16]

Jon M. Kleinberg and Robert Kleinberg. 2018. Delegated Search Approximates Efficient Search. In EC. ACM, 287--302.

[17]

Robert D. Kleinberg, Bo Waggoner, and E. Glen Weyl. 2016. Descending Price Optimally Coordinates Search. In EC. ACM, 23--24.

[18]

Wojciech Olszewski and Richard Weber. 2015. A more general Pandora rule? J. Econ. Theory, Vol. 160 (2015), 429--437.

[19]

Christos H. Papadimitriou and Mihalis Yannakakis. 1991. Optimization, Approximation, and Complexity Classes. J. Comput. Syst. Sci., Vol. 43, 3 (1991), 425--440.

[20]

Martin L. Puterman. 1994. Markov Decision Processes: Discrete Stochastic Dynamic Programming .Wiley.

[21]

Sahil Singla. 2018a. Combinatorial Optimization Under Uncertainty: Probing and Stopping-Time Algorithms. Ph.D. Dissertation. PhD thesis, Carnegie Mellon University.

[22]

Sahil Singla. 2018b. The Price of Information in Combinatorial Optimization. In SODA. SIAM, 2523--2532.

[23]

Maxim Sviridenko, Jan Vondrá k, and Justin Ward. 2017. Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature. Math. Oper. Res., Vol. 42, 4 (2017), 1197--1218.

Digital Library

[24]

Richard Weber et al. 1992. On the Gittins index for multiarmed bandits. The Ann. Appl. Probab., Vol. 2, 4 (1992), 1024--1033.

[25]

Gideon Weiss. 1988. Branching bandit processes. Probab. in the Eng. and Info. Sciences, Vol. 2, 3 (1988), 269--278.

[26]

Martin L Weitzman. 1979. Optimal search for the best alternative. Econometrica (1979), 641--654.

Cited By

Gergatsouli ETzamos COh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Weitzman's rule for pandora's box with correlationsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666677(12644-12664)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666677
Boodaghians SFusco FLazos PLeonardi S(2023)Pandora’s Box Problem with Order ConstraintsMathematics of Operations Research10.1287/moor.2022.127148:1(498-519)Online publication date: Feb-2023
https://doi.org/10.1287/moor.2022.1271
Dütting PGergatsouli ERezvan RTeng YTsigonias-Dimitriadis ALeyton-Brown KSamuelson LHartline J(2023)Prophet Secretary Against the Online OptimalProceedings of the 24th ACM Conference on Economics and Computation10.1145/3580507.3597736(561-581)Online publication date: 9-Jul-2023
https://dl.acm.org/doi/10.1145/3580507.3597736
Show More Cited By

Index Terms

Pandora's Box Problem with Order Constraints
1. Mathematics of computing
  1. Probability and statistics
    1. Stochastic processes
      1. Markov processes
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Stochastic approximation

Recommendations

Pandora’s Box Problem with Order Constraints
The Pandora’s Box problem, originally posed by Weitzman in 1979, models selection from a set of random-valued alternatives—the “boxes”—when evaluation is costly. Weitzman showed that the Pandora’s Box problem admits a simple threshold-based solution that ...
Pandora's Problem with Combinatorial Cost
EC '23: Proceedings of the 24th ACM Conference on Economics and Computation

Pandora's problem is a fundamental model in economics that studies optimal search strategies under costly inspection. In this paper we initiate the study of Pandora's problem with combinatorial costs, capturing many real-life scenarios where search ...
Pricing commodities

How should a seller price her goods in a market where each buyer prefers a single good among his desired goods, and will buy the cheapest such good, as long as it is within his budget? We provide efficient algorithms that compute near-optimal prices for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '20: Proceedings of the 21st ACM Conference on Economics and Computation

July 2020

937 pages

ISBN:9781450379755

DOI:10.1145/3391403

General Chairs:
Péter Biró
Hungarian Academy of Sciences
,
Jason Hartline
Northwestern University
,
Program Chairs:
Michael Ostrovsky
Stanford University
,
Ariel Procaccia
Harvard University

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGecom: Special Interest Group on Economics and Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 July 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

European Research Council
Ministero dellðIstruzione, dellðUniversità e della Ricerca

Conference

EC '20

Sponsor:

SIGecom

EC '20: The 21st ACM Conference on Economics and Computation

July 13 - 17, 2020

Virtual Event, Hungary

Acceptance Rates

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
229
Total Downloads

Downloads (Last 12 months)37
Downloads (Last 6 weeks)5

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gergatsouli ETzamos COh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Weitzman's rule for pandora's box with correlationsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666677(12644-12664)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666677
Boodaghians SFusco FLazos PLeonardi S(2023)Pandora’s Box Problem with Order ConstraintsMathematics of Operations Research10.1287/moor.2022.127148:1(498-519)Online publication date: Feb-2023
https://doi.org/10.1287/moor.2022.1271
Dütting PGergatsouli ERezvan RTeng YTsigonias-Dimitriadis ALeyton-Brown KSamuelson LHartline J(2023)Prophet Secretary Against the Online OptimalProceedings of the 24th ACM Conference on Economics and Computation10.1145/3580507.3597736(561-581)Online publication date: 9-Jul-2023
https://dl.acm.org/doi/10.1145/3580507.3597736
Fu HLi JLiu DSaha BServedio R(2023)Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation SchemeProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585229(789-802)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585229
Beyhaghi HCai LSaha BServedio R(2023)Pandora’s Problem with Nonobligatory Inspection: Optimal Structure and a PTASProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585217(803-816)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585217
Bechtel CDughmi SPatel NPennock DSegal ISeuken S(2022)Delegated Pandora's BoxProceedings of the 23rd ACM Conference on Economics and Computation10.1145/3490486.3538267(666-693)Online publication date: 12-Jul-2022
https://dl.acm.org/doi/10.1145/3490486.3538267
Cohen I(2022)Stochastic Graph Exploration with Limited ResourcesApproximation and Online Algorithms10.1007/978-3-031-18367-6_9(172-189)Online publication date: 21-Oct-2022
https://doi.org/10.1007/978-3-031-18367-6_9
Arsenis MDrosis OKleinberg RMarx D(2021)Constrained-order prophet inequalitiesProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458185(2034-2046)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458185
Aouad AJi JShaposhnik Y(undefined)Pandora's Box Problem with Sequential InspectionsSSRN Electronic Journal10.2139/ssrn.3726167
https://doi.org/10.2139/ssrn.3726167

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents