Open main menu

The odds-algorithm is a mathematical method for computing optimal strategies for a class of problems that belong to the domain of optimal stopping problems. Their solution follows from the odds-strategy, and the importance of the odds-strategy lies in its optimality, as explained below.

The odds-algorithm applies to a class of problems called last-success-problems. Formally, the objective in these problems is to maximize the probability of identifying in a sequence of sequentially observed independent events the last event satisfying a specific criterion (a "specific event"). This identification must be done at the time of observation. No revisiting of preceding observations is permitted. Usually, a specific event is defined by the decision maker as an event that is of true interest in the view of "stopping" to take a well-defined action. Such problems are encountered in several situations.

ExamplesEdit

Two different situations exemplify the interest in maximizing the probability to stop on a last specific event.

  1. Suppose a car is advertised for sale to the highest bidder (best "offer"). Let n potential buyers respond and ask to see the car. Each insists upon an immediate decision from the seller to accept the bid, or not. Define a bid as interesting, and coded 1 if it is better than all preceding bids, and coded 0 otherwise. The bids will form a random sequence of 0s and 1s. Only 1s interest the seller, who may fear that each successive 1 might be the last. It follows from the definition that the very last 1 is the highest bid. Maximizing the probability of selling on the last 1 therefore means maximizing the probability of selling best.
  2. A physician, using a special treatment, may use the code 1 for a successful treatment, 0 otherwise. The physician treats a sequence of n patients the same way, and wants to minimize any suffering, and to treat every responsive patient in the sequence. Stopping on the last 1 in such a random sequence of 0s and 1s would achieve this objective. Since the physician is no prophet, the objective is to maximize the probability of stopping on the last 1. (See Compassionate use.)

DefinitionsEdit

Consider a sequence of   independent events. Associate with this sequence another sequence   with values 1 or 0. Here  , called a success, stands for the event that the kth observation is interesting (as defined by the decision maker), and   for non-interesting. We observe independent random variables   sequentially and want to select the last success.

Let   be the probability that the kth event is interesting. Further let   and  .Note that   represents the odds of the kth event turning out to be interesting, explaining the name of the odds-algorithm.

Algorithmic procedureEdit

The odds-algorithm sums up the odds in reverse order

 

until this sum reaches or exceeds the value 1 for the first time. If this happens at index s, it saves s and the corresponding sum

 

If the sum of the odds does not reach 1, it sets s = 1. At the same time it computes

 

The output is

  1.  , the stopping threshold
  2.  , the win probability.

Odds-strategyEdit

The odds-strategy is the rule to observe the events one after the other and to stop on the first interesting event from index s onwards (if any), where s is the stopping threshold of output a.

The importance of the odds-strategy, and hence of the odds-algorithm, lies in the following odds-theorem.

Odds-theoremEdit

The odds-theorem states that

  1. The odds-strategy is optimal, that is, it maximizes the probability of stopping on the last 1.
  2. The win probability of the odds-strategy equals  
  3. If  , the win probability   is always at least  , and this lower bound is best possible.

FeaturesEdit

The odds-algorithm computes the optimal strategy and the optimal win probability at the same time. Also, the number of operations of the odds-algorithm is (sub)linear in n. Hence no quicker algorithm can possibly exist for all sequences, so that the odds-algorithm is, at the same time, optimal as an algorithm.

SourcesEdit

Bruss 2000 devised the odd-algorithm, and coined its name. It is also known as Bruss-algorithm (strategy). Free implementations can be found on the web.

ApplicationsEdit

Applications reach from medical questions in clinical trials over sales problems, secretary problems, portfolio selection, (one-way) search strategies, trajectory problems and the parking problem to problems in on-line maintenance and others.

There exists, in the same spirit, an Odds-Theorem for continuous-time arrival processes with independent increments such as the Poisson processBruss. In some cases, the odds are not necessarily known in advance (as in Example 2 above) so that the application of the odds-algorithm is not directly possible. In this case each step can use sequential estimates of the odds. This is meaningful, if the number of unknown parameters is not large compared with the number n of observations. The question of optimality is then more complicated, however, and requires additional studies. Generalizations of the odds-algorithm allow for different rewards for failing to stop and wrong stops as well as replacing independence assumptions by weaker ones (Ferguson (2008)).

VariationsEdit

Bruss & Paindaveine 2000 discussed a problem of selecting the last   successes.

Tamaki 2010 proved a multiplicative odds theorem which deals with a problem of stopping at any of the last   successes. A tight lower bound of win probability is obtained by Matsui & Ano 2014.

Matsui & Ano 2017 discussed a problem of selecting   out of the last   successes and obtained a tight lower bound of win probability. When   the problem is equivalent to Bruss' odds problem. If   the problem is equivalent to that in Bruss & Paindaveine 2000. A problem discussed by Tamaki 2010 is obtained by setting  


multiple choice problem: A player is allowed   choices, and he wins if any choice is the last success. For classical secretary problem, Gilbert & Mosteller 1966 discussed the cases  . The odds problem with   is discussed by Ano, Kakinuma & Miyoshi 2010. For further cases of odds problem, see Matsui & Ano 2016.

An optimal strategy belongs to the class of strategies defined by a set of threshold numbers  , where  . The first choice is to be used on the first candidates starting with  th applicant, and once the first choice is used, second choice is to be used on the first candidate starting with  th applicant, and so on.

When  , Ano, Kakinuma & Miyoshi 2010 showed that the tight lower bound of win probability is equal to   For general positive integer  , Matsui & Ano 2016 discussed the tight lower bound of win probability. When  , tight lower bounds of win probabilities are equal to  ,   and   respectively. For further cases that  , see Matsui & Ano 2016.

See alsoEdit

ReferencesEdit

External linksEdit