Decision-Making on the Full Information Secretary Problem
Decision-Making on the Full Information Secretary Problem Michael D. Lee, Tess A. O’Connor and Matthew B. Welsh {michael.lee,tess.oconnor,matthew.welsh}@psychology.adelaide.edu.au Department of Psychology, University of Adelaide South Australia, 5005, AUSTRALIA Abstract The secretary problem is a recreational mathematics problem, suited to laboratory experimentation, that nevertheless is representative of a class of real world sequential decision-making tasks. In the ‘full infor- mation’ version, an observer is presented with a se- quence of values from a known distribution, and is required to choose the maximum value. The difficul- ties are that a value can only be chosen at the time it is presented, that the last value in the sequence is a forced choice if none is chosen earlier, and that any value that is not the maximum is scored as completely wrong. We report a study of human performance on full information secretary problems with 10, 20 and 50 values in the sequence, and considers three differ- ent heuristics as models of human decision-making. It is found that some people achieve near-optimal lev- els of accuracy, but that there are individual differ- ences in human performance. A quantitative evalua- tion of the three heuristics, using the Minimum De- scription Length criterion, shows inter-individual dif- ferences, but intra-individual consistency, in the use of the heuristics. In particular, people seem to use the heuristics that involve choosing a value when it exceeds an internal threshold, but differ in how they set thresholds. On the basis of these findings, a more general threshold-based family of heuristic models is developed. Introduction Many real world decision-making problems are sequen- tial in nature. A series of choices is made available over time, and it is often efficient (and sometimes even necessary) to make a selection without waiting to be presented with all of the alternatives. On long cross- country drives, for example, people refill their cars at one of a sequence of towns on the route, without know- ing the price of fuel at subsequent towns. This type of sequential decision has a continuous utility function. People aim to choose the cheapest price, and measure their success by how much their purchase exceeded this minimum. Other sequential decision-making tasks have bi- nary utility functions, where any incorrect decision is equally (and completely) incorrect. For example, con- sider being a witness for a police line-up, where, be- cause of the circumstances of the case, the offender is known to be in the line-up. Police line-up policy demands that suspects are presented one at a time, may only be viewed once, and that a suspect must be identified at the time they are presented (e.g., Ste- blay, Deisert, Fulero, & Lindsay 2001). Suppose also (unrealistically, we hope) that the police insist that a suspect be identified, and indicate that they will force the identification of the last person in the line-up if none of the previous people are chosen. The aim is to choose the offender, and any misidentification has the equally bad outcome of selecting an innocent suspect. This decision-making scenario has the same essential features as a recreational mathematics problem known as the ‘secretary problem’ (see Ferguson 1989 for a his- torical overview). In secretary problems, an observer is presented with a sequence of possible choices, and must decide whether to accept or reject each possi- bility in turn. The number of choices in the complete sequence is fixed and known, and only the rank of each possibility, relative to those already seen, is presented to the observer. If the observer chooses the best pos- sibility in the sequence, their decision is correct, and any other choice is regarded as incorrect. Variants of the secretary problem have been consid- ered that change or relax different parts of the problem. In particular, the full information version of the secre- tary problem, sometimes known as the ‘Cayley’ prob- lem, presents observers with a score from a known dis- tribution for each possibility, and the goal is to choose the maximum score in the sequence. Rank information corresponds to the assumption that witnesses keep a relative ordering of people in line-ups, whereas value information corresponds to the assumption that wit- nesses evaluate some continuous measure of the prob- ability that a person is the offender. In either case, the secretary problem has the important feature of using the same binary utility function as the line-up deci- sion. The goal is to choose the actual offender, and any incorrect decision is equally wrong. Problem Solving and Secretary Problems Human performance on secretary problems is an in- teresting topic for cognitive science, for a number of reasons. It offers a well defined task, suited to labora-