Optimal Search (Secretary Problems)


When you're searching for someone to marry or for information online, when should you stop? One cannot answer those questions with anything besides nonsense, of course, unless the search problems are better specified. What is the objective of the searcher? While searching, what kind of information does one learn about the distribution of possible search outcomes? Once an alternative is rejected during search can it later be recalled? How costly is it to search? Etc. 

Interestingly, one can specify problems with sufficient mathematical precision to make them "solvable." The problems are often referred to as Optimal Stopping Problems or Secretary Problems. (Secretary Problems are actually a special class of Optimal Stopping Problems, but people often use the former to refer to the latter.)

Below are links to some of my own published papers on search in which I've examined both the nature of optimal search and also the behavior of actual people while searching. These papers deal with problems that are much simpler than many of the problems we face while googling, but they may give some hints to how we might do so better.  

Secretary Problem Papers


Bearden, J. N., & Rapoport, A. (2005). Operations research in experimental psychology. In J. C. Smith (Ed.), Tutorials in Operations Research: Emerging Theory, Methods, and Applications, 213-236. IN-FORMS: Hanover, MD.

Bearden, J. N., Murphy, R. O., & Rapoport, A. (2005). A multi-attribute extension of the secretary problem: Theory and experiments. Journal of Mathematical Psychology, 49, 410-425.

Bearden, J. N. (2006). A new secretary problem with rank-based selection and cardinal payoffs. Journal of Mathematical Psychology, 50, 58-59.

Bearden, J. N., Rapoport, A., & Murphy, R. O. (2006). Sequential observation and selection with rank-dependent payoffs: An experimental test. Management Science, 52, 1437-1449.

Bearden, J. N., Rapoport, A., & Murphy, R. O. (2006). Sequential selection and assignment: An experimental study. Journal of Behavioral Decision Making, 19, 229-250.

Bearden, J. N., & Murphy, R. O. (2007). On generalized secretary problems. In M. Abdellaoui, R.D. Luce, M. J. Machina and B. Munier (Eds.), Uncertainty and Risk – Mental, Formal and Experimental Representations. Springer: New York. (pre-published version)


Other Papers on Search and Optimal Stopping


Lim, C., Bearden, J. N., & Smith, C. (2006). Sequential search with multi-attribute options. Decision Analysis, 3, 3-15.

Smith, J. C., Lim, C., & Bearden, J. N. (2007). On the multi-attribute stopping problem with general value functions. Operations Research Letters, 35, 324-330.

Bearden, J. N. & Connolly, T. (2007). Multi-attribute sequential search. Organizational Behavior & Human Decision Processes, 103, 147-158.

Bearden, J. N. & Connolly, T. (2008). On optimal satisficing: How simple policies can achieve excellent results. In Kugler, T., Smith J. C., Connolly, T., and Son, Y. J. (Eds.). Decision Modeling in Uncertain and Complex Environments. Springer: New York. (pdf is of pre-published version)


Some Background


Optimal Stopping on Wikipedia

Secretary Problems on Wikipedia

Satisficing on Wikipedia

Ferguson, T.S. (1989). "Who solved the secretary problem?". Statistical science 4: 282–296.

Utility for Calculating Optimal Cutoff for Classical Secretary Problem (Much to my surprise, the utility also calculates the optimal policy for a problem I solved in this paper.)
Comments