In decision theory, the odds algorithm (or Bruss algorithm) is a mathematical method for computing optimal strategies for a class of problems that belong to the domain of optimal stopping 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").
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.
Two different situations exemplify the interest in maximizing the probability to stop on a last specific event.
, called a success, stands for the event that the kth observation is interesting (as defined by the decision maker), and
The odds algorithm sums up the odds in reverse order until this sum reaches or exceeds the value 1 for the first time.
At the same time it computes The output is 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 odds theorem states that The odds algorithm computes the optimal strategy and the optimal win probability at the same time.
Bruss 2000 devised the odds algorithm, and coined its name.
Free implementations can be found on the web.
There exists, in the same spirit, an Odds Theorem for continuous-time arrival processes with independent increments such as the Poisson process (Bruss 2000).
In this case each step can use sequential estimates of the odds.
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).
Bruss & Paindaveine 2000 discussed a problem of selecting the last
Tamaki 2010 proved a multiplicative odds theorem which deals with a problem of stopping at any of the last
A tight lower bound of win probability is obtained by Matsui & Ano 2014.
Matsui & Ano 2017 discussed a problem of selecting
successes and obtained a tight lower bound of win probability.
A problem discussed by Tamaki 2010 is obtained by setting
For classical secretary problem, Gilbert & Mosteller 1966 discussed the cases
For further cases of odds problem, see Matsui & Ano 2016.
An optimal strategy for this problem belongs to the class of strategies defined by a set of threshold numbers
application officers, each holding one letter.
You keep interviewing the candidates and rank them on a chart that every application officer can see.
(Unsent letters of acceptance are by default given to the last applicants, the same as in the standard secretary problem.)
, Ano, Kakinuma & Miyoshi 2010 showed that the tight lower bound of win probability is equal to
, Matsui & Ano 2016 proved that the tight lower bound of win probability is the win probability of the secretary problem variant where one must pick the top-k candidates using just k attempts.
, tight lower bounds of win probabilities are equal to
, and an algorithm for general cases, see Matsui & Ano 2016.