Odds-Strategie

Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Bitte hilf mit, die Mängel dieses Artikels zu beseitigen, und beteilige dich bitte an der Diskussion!

Die Odds-Strategie (abgeleitet von Odds) bzw. der Bruss-Algorithmus oder die Bruss-Strategie (nach dem Entwickler des Verfahrens Franz Thomas Bruss) ist ein mathematisches Verfahren aus der Entscheidungstheorie, das es ermöglicht, mit großer Wahrscheinlichkeit eine optimale „Gelegenheit“ aus einer Folge von Ereignissen auszuwählen.

Die Strategie kann angewendet werden, wenn eine zeitliche Abfolge von unabhängigen Ereignissen vorliegt, von denen einige als „Gelegenheiten“ gelten, und bei Eintreten einer Gelegenheit nicht bekannt ist, ob später noch eine bessere Gelegenheit folgt. Ein Beispiel ist die Situation eines Gebrauchtwagenhändlers oder Immobilienmaklers, der bei Vorliegen eines Kaufangebots nicht weiß, ob später ein weiterer Kaufinteressent ein besseres Angebot macht.

Ein spezieller Fall für die Anwendung der Odds-Strategie ist das Sekretärinnenproblem, in dem der/die beste Kandidat(in) ausgewählt werden soll. Die Odds-Strategie ist wesentlich allgemeiner anwendbar, da sie eine beliebige Definitionen "interessanter Ereignisse" zulässt. Der Algorithmus zur Berechnung der Strategie ist außerdem selbst optimal.^[1]

Definitionen

Um die Odds-Strategie anwenden zu können, muss die Realität mathematisch modelliert werden. Dazu wird eine Folge von n Ereignissen angenommen, zum Beispiel könnte jedes Ereignis ein Kaufangebot sein. Die Ereignisse werden mit dem Index k von 1 bis n durchnummeriert: E₁, E₂, ... E_k, ... E_n

Jedes Ereignis E_k ist mit einer bestimmten Wahrscheinlichkeit p_k eine „Gelegenheit“.

Wenn p_k die Wahrscheinlichkeit dafür ist, dass E_k die gesuchte Gelegenheit ist, dann ist q_k = 1 − p_k die Wahrscheinlichkeit dafür, dass sie es nicht ist.

Ihren Namen hat die Strategie vom Quotienten $r_k = \frac{p_k}{q_k}$, der englisch Odds genannt wird.

Algorithmus

Die Strategie besteht darin, ab einem bestimmten Index s, dem „Stoppindex“ die erste Gelegenheit wahrzunehmen. Im Beispiel des Gebrauchtwagenhändlers heißt das, dass er die Angebote der ersten s-1 Kunden nicht annimmt und ab dem Ereignis E_s die erste Gelegenheit wahrnimmt, also demjenigen Kunden verkauft, der als erster ab dem s-ten ein besseres Angebot als alle seine Vorgänger macht.

Der Stoppindex s wird bestimmt, indem die odds rückwärts aufgeschrieben werden: r_n, r_n-1, r_n-2 usw. Dabei werden sie aufsummiert, und zwar solange, bis die Summe 1 erreicht wird. Dasjenige k, bei dem diese Summe erreicht wird, bildet den Stoppindex.

Erfolgswahrscheinlichkeit

Diese Strategie ist mathematisch beweisbar die beste unter all den Strategien, die unter gleichen Annahmen eine optimale Gelegenheit wählen müssen.

Die Wahrscheinlichkeit dafür, dass die beste Gelegenheit genutzt wird, berechnet sich aus der Summe R_s der r_k und der Wahrscheinlichkeit Q_s dafür, dass unter den in Frage kommenden Ereignissen keine Gelegenheit ist.

$R_s = \sum_{k=n}^s r_k$

$Q_s = \prod_{k=n}^s q_k$

Dann ist die Erfolgswahrscheinlichkeit $W = R_s \cdot Q_s$.

Beispiel

k	pk	qk	rk	$\sum_{i=n}^k r_i$
16	0,0625	0,9375	0,0667	0,0667
15	0,0667	0,9333	0,0714	0,1381
14	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
8	0,1250	0,8750	0,1429	0,8682
7	0,1429	0,8571	0,1667	1,0349

Angenommen, der Gebrauchtwagenverkäufer weiß, dass sich in einem Monat durchschnittliche 16 Kunden für ein Auto interessieren, und er möchte natürlich demjenigen Kunden verkaufen, der den höchsten Preis bietet. Ein Ereignis ist für den Gebrauchtwagenhändler also dann eine „Gelegenheit“, wenn es besser ist als alle vorherigen. Für das erste Angebot gilt das mit Sicherheit, also ist p₁ = 1. Für das zweite Angebot ist $p_2 = \frac{1}{2}$, wenn jede Ankunftsreihenfolge als gleichwahrscheinlich vorausgesetzt wird. Allgemein gilt dann $p_k = \frac{1}{k}$.

Daraus folgt $q_k = \frac{k-1}{k}$ und $r_k = \frac{p_k}{q_k} = \frac{1}{k-1}$.

Da der Gebrauchtwagenhändler durchschnittlich 16 Kunden pro Monat hat, ist n = 16. Die nebenstehende Tabelle zeigt, dass der Stoppindex 7 ist, weil bei k = 7 die Summe 1 erreicht wird.

Der Gebrauchtwagenhändler muss also bis zum siebten Angebot warten, und dann das erste annehmen, das besser ist als alle vorherigen.

Die Erfolgswahrscheinlichkeit ist $W = R_s \cdot Q_s = 1{,}0349 \cdot 0{,}3750 = 0{,}3881$, also zirka 39 %. Mit anderen Worten: Der Gebrauchtwagenhändler verkauft das Auto in 39 % aller Fälle zum besten Preis.

Verallgemeinerungen

Das vorherige Beispiel ist das "Sekretärinnenproblem". Die Lösung ist weniger interessant, sobald der Gebrauchtwagenhändler Zusatzinformationen hat. Hier zeigt sich der Vorteil der allgemeinen Definition der $r_k = \frac{p_k}{q_k}$. Nehmen wir als einfaches Beispiel an, der Gebrauchtwagenhändler kennt drei der letzten potentiellen Kunden und glaubt aus Erfahrung, dass jeder den bisherigen Höchstpreis (unabhängig) mit Wahrscheinlichkeit p überbietet. Wenn p zumindest 1/4 ist (also die entsprechenden odds zumindest 1/3) zeigt nun die Odds-Strategie, dass es optimal ist, zumindest auf eine weitere Angebotserhöhung zu setzen. Verallgemeinerungen für eine unbekannten Anzahl von potentiellen Kunden sind ebenfalls möglich mittels einer Integralversion (Bruss 2000) der Odds-Strategie.

Siehe auch

Verwandte Themen, bei denen man aus Teilinformation die optimale Entscheidung des Restproblems treffen kann:

• 37-%-Regel
• Gefangenenparadoxon
• Sekretärinnenproblem
• Umtauschparadoxon
• Ziegenproblem
• Zwei-Zettel-Spiel

Literatur

• F. Thomas Bruss: Die Kunst der richtigen Entscheidung. In: Spektrum der Wissenschaft. Juni 2005. Spektrum der Wissenschaft Verlagsgesellschaft mbH, Seiten 78–84. ISSN 0170-2971

• F. Thomas Bruss: Sum the odds to one and stop, Annals of Probability,Band 28, Seiten 1384-1391,

2000.

Einzelnachweise

1. ↑ Bruss, Louchard: The Odds-algorithm based on sequential updating and its performance. AAP, Nr. 41, 2009, S. 131-153. (ps)

Weblinks

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