Odds algorithm: Difference between revisions

Revision as of 15:57, 30 May 2011

Revision as of 16:01, 30 May 2011

Line 1:

The '''odds-algorithm''' is a mathematical method to computefor computing optimal

strategies for a class of problems that belong to the ___domain of [[optimal stopping]] problems. Its Their solution determinesfollows 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 lastspecific criterion (a "specific event"). This identification must be done at the time of observation. No recallrevisiting onof preceding observations is permitted. Usually, a specific

event is defined by the decision maker as an event whichthat is of true interest in the view of "stopping" in order to take a well-defined action. Such problems are encountered in several situations.

==Examples==

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

# Suppose a car is advertised for sale to the highest bidder (best "offer"). 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''.