Odds strategy

The odds strategy (derived from odds ) or the Bruss algorithm or the Bruss strategy (after the developer of the method F. Thomas Bruss ) is a mathematical method from decision theory , with which one is very likely to find an optimal " opportunity " can choose from a sequence of events . The algorithm for calculating the strategy is also optimal itself.

The strategy can be used when there is a chronological sequence of unrelated events, some of which are considered “opportunities”, and when an opportunity arises it is not known whether another or better opportunity will follow. An example is the situation of a used car dealer or real estate agent who, when there is a purchase offer, does not know whether another prospective buyer will later make a better offer. Every better offer is then an interesting event (opportunity), and the last interesting event that is not known in advance is the best offer. A special case for the application of the odds strategy is the secretary's problem , in which the the best candidate should be selected.

The odds strategy can be used in several areas, as it allows any definition for "opportunity" or "interesting events" and thus enables the optimization of quite general target functions. For ethical reasons, for example, it is optimal to "stop" in clinical trials if, in a series of experiments, a fixed number of patients to be treated sequentially was recorded with maximum probability that the last treatment was successful. Every successful treatment is an opportunity here. Opportunities are not compared qualitatively, but all successes are achieved with the last opportunity, so that all further patients can be spared the treatment (see e.g. "Compassionate use" and (B. 2005).)

Definitions

In order to be able to apply the odds strategy, reality must be modeled mathematically . To this end, a sequence of events is accepted, for example each event could be an offer to buy. The events are the index of up numbered: . Every event is an "opportunity" with a certain probability . ${\ displaystyle n}$ ${\ displaystyle k}$ ${\ displaystyle 1}$ ${\ displaystyle n}$ ${\ displaystyle E_ {1}, E_ {2}, \ dots, E_ {k}, \ dots, E_ {n}}$ ${\ displaystyle E_ {k}}$ ${\ displaystyle p_ {k}}$

If the likelihood is that the opportunity is being sought, then is ${\ displaystyle p_ {k}}$ ${\ displaystyle E_ {k}}$

{\ displaystyle q_ {k} = 1-p_ {k}}

the likelihood that it isn't. The strategy takes its name from the quotient

{\ displaystyle r_ {k} = {\ frac {p_ {k}} {q_ {k}}},}

which is called English odds .

algorithm

The strategy is to take the first opportunity at a certain index , the so-called “stop index”, which is better than any previous opportunity. ${\ displaystyle s}$

The stop index is determined by the odds backwards written: , , etc. In this case, they are added up, and until such time as the sum is 1 reached or exceeded. The sum is defined for this ${\ displaystyle s}$ ${\ displaystyle r_ {n}}$ ${\ displaystyle r_ {n-1}}$ ${\ displaystyle r_ {n-2}}$

{\ displaystyle R_ {k} = \ sum _ {i = k} ^ {n} r_ {i}}

and the one at which the value of this sum reaches or exceeds the value 1 for the first time forms the stop index . ${\ displaystyle k}$ ${\ displaystyle s}$

Probability of success

The odds strategy is optimal with the stipulation of choosing the last opportunity of all opportunities with the highest probability. In the application, an opportunity is often understood to mean an event that is better than all previous events according to one criterion, for example a better offer than all previous offers. In this context, the odds strategy chooses the best offer with the highest probability compared to other strategies.

The probability of success for the odds algorithm, so the probability that the last or best opportunity is used is: . Here is ${\ displaystyle W = R_ {s} \ cdot Q_ {s}}$

{\ displaystyle R_ {s} = \ sum _ {i = s} ^ {n} r_ {i}}

the sum of the odds and

{\ displaystyle Q_ {s} = \ prod _ {i = s} ^ {n} q_ {i}}

the probability that there is no opportunity among the events in question.

Examples

Secretary problem

${\ displaystyle k}$	${\ displaystyle p_ {k}}$	${\ displaystyle q_ {k}}$	${\ displaystyle r_ {k}}$	${\ displaystyle R_ {k}}$
16	0.0625	0.9375	0.0667	0.0667
15th	0.0667	0.9333	0.0714	0.1381
14th	0.0714	0.9286	0.0769	0.2150
13	0.0769	0.9231	0.0833	0.2984
12	0.0833	0.9167	0.0909	0.3893
11	0.0909	0.9091	0.1000	0.4893
10	0.1000	0.9000	0.1111	0.6004
9	0.1111	0.8889	0.1250	0.7254
8th	0.1250	0.8750	0.1429	0.8682
7th	0.1429	0.8571	0.1667	1.0349

For example, suppose the used car salesman knows that an average of 16 customers are interested in a car in a month, and of course they want to sell to the customer who offers the highest price. An event is an “opportunity” for the used car dealer if it is better than any previous one.

This certainly applies to the first offer , so is . For the second offer , if every order of arrival is assumed to be equally likely, then generally applies . It follows and . ${\ displaystyle p_ {1} = 1}$ ${\ displaystyle p_ {2} = {\ tfrac {1} {2}}}$ ${\ displaystyle p_ {k} = {\ tfrac {1} {k}}}$ ${\ displaystyle q_ {k} = {\ tfrac {k-1} {k}}}$ ${\ displaystyle r_ {k} = {\ tfrac {p_ {k}} {q_ {k}}} = {\ tfrac {1} {k-1}}}$

Since the used car dealer has an average of 16 customers per month . The adjacent table shows that the stop index is because the sum of the backwards added up odds reaches or exceeds 1 for the first time. So the used car dealer has to wait until the seventh offer and then accept the first, which is better than any previous one. ${\ displaystyle n = 16}$ ${\ displaystyle s = 7}$ ${\ displaystyle k = 7}$ ${\ displaystyle \ textstyle R_ {k} = \ sum _ {i = k} ^ {n} r_ {i}}$

The probability of success is around 39%. In other words, the used car dealer sells the car at the best price 39% of the time. ${\ displaystyle W = R_ {s} \ cdot Q_ {s} = 1 {,} 0349 \ cdot 0 {,} 3750 = 0 {,} 3881}$

Generalizations

The previous example is the "secretary problem". The solution is less interesting as soon as the used car dealer has additional information. This shows the advantage of the general definition in the odds strategy. As a simple example, let's assume that the used car dealer knows three of the last potential customers and thinks he knows from experience that each of these three has a probability of outbidding the previous maximum price independently of one another . If at least has the value (or the corresponding at least the value ), the odds strategy now shows that it is optimal to bet on at least one further increase in supply. Generalizations for an unknown number of potential customers are also possible using an integral version (B. 2000) of the odds strategy. ${\ displaystyle r_ {k} = {\ tfrac {p_ {k}} {q_ {k}}}}$ ${\ displaystyle p}$ ${\ displaystyle p}$ ${\ displaystyle {\ tfrac {1} {4}}}$ ${\ displaystyle r_ {k}}$ ${\ displaystyle {\ tfrac {1} {3}}}$

literature

F. Thomas Bruss : The art of making the right decision . In: Spectrum of Science . June 2005. Spektrum der Wissenschaft Verlagsgesellschaft mbH, pages 78–84, ISSN 0170-2971 .
F. Thomas Bruss: Sum the odds to one and stop , Annals of Probability , Volume 28, pages 1384-1391, 2000.

Web links

Bruss algorithm http://www.p-roesler.de/odds.html

Individual evidence

^ Bruss, Louchard: The Odds-algorithm based on sequential updating and its performance . AAP, No. 41, 2009, pp. 131-153. (ps)

[1] Bruss, Louchard: The Odds-algorithm based on sequential updating and its performance . AAP, No. 41, 2009, pp. 131-153. (ps)