The Pandora’s Box Problem with Sequential Inspections

References

• Asadpour A, Nazerzadeh H (2015) Maximizing stochastic monotone submodular functions. Management Sci. 62(8):2374–2391.Link, Google Scholar
• Asawa M, Teneketzis D (1996) Multi-armed bandits with switching penalties. IEEE Trans. Automatic Control 41(3):328–348.Crossref, Google Scholar
• Attias C, Krauthgamer R, Levi R, Shaposhnik Y (2017) Stochastic selection problems with testing. Preprint, submitted December 11, https://doi.org/10.2139/ssrn.3076956.Google Scholar
• Balseiro SR, Brown DB (2019) Approximations to stochastic dynamic programs via information relaxation duality. Oper. Res. 67(2):577–597.Abstract, Google Scholar
• Baucells M, Zorc S (2024) Search in the dark: The case with recall and gaussian learning. Oper. Res. 73(5):2572–2590.Google Scholar
• Bertsekas D (2019) Reinforcement Learning and Optimal Control (Athena Scientific, Belmont, MA).Google Scholar
• Bertsimas D, Nino-Mora J (1996) Conservation laws, extended polymatroids and multiarmed bandit problems; a polyhedral approach to indexable systems. Math. Oper. Res. 21(2):257–306.Link, Google Scholar
• Beyhaghi H (2019) Approximately-optimal mechanisms in auction design, search theory, and matching markets. Unpublished PhD thesis, Cornell University, Ithaca, NY.Google Scholar
• Beyhaghi H, Kleinberg R (2019) Pandora’s problem with nonobligatory inspection. Proc. 2019 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 131–132.Google Scholar
• Boodaghians S, Fusco F, Lazos P, Leonardi S (2020) Pandora’s box problem with order constraints. ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 439–458.Google Scholar
• Brown DB, Smith JE (2013) Optimal sequential exploration: Bandits, clairvoyants, and wildcats. Oper. Res. 61(3):644–665.Link, Google Scholar
• Choi M, Dai AY, Kim K (2018) Consumer search and price competition. Econometrica 86(4):1257–1281.Crossref, Google Scholar
• Chu LY, Nazerzadeh H, Zhang H (2020) Position ranking and auctions for online marketplaces. Management Sci. 66(8):3617–3634.Link, Google Scholar
• Clarkson J, Glazebrook KD, Lin KY (2020) Fast or slow: Search in discrete locations with two search modes. Oper. Res. 68(2):552–571.Abstract, Google Scholar
• De los Santos B, Hortaçsu A, Wildenbeest MR (2012) Testing models of consumer search using data on web browsing and purchasing behavior. Amer. Econom. Rev. 102(6):2955–2980.Crossref, Google Scholar
• Derakhshan M, Golrezaei N, Manshadi V, Mirrokni V (2020) Product ranking on online platforms. Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 459.Google Scholar
• Doval L (2018) Whether or not to open Pandora’s box. J. Econom. Theory 175:127–158.Crossref, Google Scholar
• Eick SG (1988) Gittins procedures for bandits with delayed responses. J. Roy. Statist. Soc. Ser. B Methodological 50(1):125–132.Crossref, Google Scholar
• Fu H, Li J, Liu D (2023) Pandora box problem with nonobligatory inspection: Hardness and approximation scheme. Proc. 55th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 789–802.Google Scholar
• Gabaix X, Laibson D, Moloche G, Weinberg S (2006) Costly information acquisition: Experimental analysis of a boundedly rational model. Amer. Econom. Rev. 96(4):1043–1068.Crossref, Google Scholar
• Gibbard P (2022) A model of search with two stages of information acquisition and additive learning. Management Sci. 68(2):1212–1217.Link, Google Scholar
• Gittins J (1979) Bandit processes and dynamic allocation indices. J. Roy. Statist. Soc. Ser. B Methodological 41(2):148–164.Crossref, Google Scholar
• Gittins J, Glazebrook K, Weber R (2011) Multi-Armed Bandit Allocation Indices (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• Immorlica N, Leshno J, Lo I, Lucier B (2020) Information acquisition in matching markets: The role of price discovery. Preprint, submitted November 23, https://doi.org/10.2139/ssrn.3705049.Google Scholar
• Miller RA (1984) Job matching and occupational choice. J. Political Econom. 92(6):1086–1120.Crossref, Google Scholar
• Olszewski W, Weber R (2015) A more general pandora rule? J. Econom. Theory 160:429–437.Crossref, Google Scholar
• Pandey S, Chakrabarti D, Agarwal D (2007) Multi-armed bandit problems with dependent arms. Proc. 24th Internat. Conf. Machine Learn. (Association for Computing Machinery, New York), 721–728.Google Scholar
• Powell WB (2007) Approximate Dynamic Programming: Solving the Curses of Dimensionality, vol. 703 (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• Robert J, Stahl DO (1993) Informative price advertising in a sequential search model. Econometrica 61(3):657–686.Crossref, Google Scholar
• Singla S (2018) The price of information in combinatorial optimization. Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2523–2532.Google Scholar
• Ursu RM (2018) The power of rankings: Quantifying the effect of rankings on online consumer search and purchase decisions. Marketing Sci. 37(4):530–552.Link, Google Scholar
• Vishwanath T (1992) Parallel search for the best alternative. Econom. Theory 2:495–507.Crossref, Google Scholar
• Weitzman ML (1979) Optimal search for the best alternative. Econometrica 47(3):641–654.Crossref, Google Scholar
• Whittle P (1980) Multi-armed bandits and the Gittins index. J. Roy. Statist. Soc. Ser. B Methodological 42(2):143–149.Crossref, Google Scholar