Open AccessRobust sequential search
Author(s) -
Schlag Karl H.,
Zapechelnyuk Andriy
Publication year - 2021
Publication title -
theoretical economics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 4.404
H-Index - 32
eISSN - 1555-7561
pISSN - 1933-6837
DOI - 10.3982/te3994
Subject(s) - prior probability , computer science , linear search , independent and identically distributed random variables , mathematical optimization , cutoff , robustness (evolution) , value (mathematics) , binary number , mathematics , algorithm , bayesian probability , random variable , artificial intelligence , statistics , machine learning , biochemistry , physics , chemistry , arithmetic , quantum mechanics , gene
We study sequential search without priors. Our interest lies in decision rules that are close to being optimal under each prior and after each history. We call these rules robust. The search literature employs optimal rules based on cutoff strategies, and these rules are not robust. We derive robust rules and show that their performance exceeds 1/2 of the optimum against binary independent and identically distributed (i.i.d.) environments and 1/4 of the optimum against all i.i.d. environments. This performance improves substantially with the outside option value; for instance, it exceeds 2/3 of the optimum if the outside option exceeds 1/6 of the highest possible alternative.