Zwei-Zettel-Spiel

Das Zwei-Zettel-Spiel oder auch Zwei-Umschläge-Problem untersucht die Frage, mit welcher Strategie man die größere von zwei Zahlen finden kann, von denen nur bekannt ist, dass sie verschieden sind.

Problemstellung

Spieler 1 schreibt zwei beliebige, verschiedene Zahlen auf Zettel. Spieler 2 wählt zufällig einen davon aus, wobei beide Zettel gleich wahrscheinlich sind, und sieht sich die Zahl an. Spieler 2 muss nun entscheiden, ob die gewählte Zahl die größere ist. Besser als mit der Wahrscheinlichkeit 1/2 zu raten, scheint nicht möglich zu sein.

Diese Formulierung wurde 1987 von Thomas M. Cover gewählt.

Anwendungsbeispiele

Ein praktisches Beispiel ist das des Hausverkaufs mit zwei Interessenten, wobei man bei Ablehnung des Angebotes nicht mehr auf den Interessenten zurückkommen kann. Insofern erinnert die Problemstellung ein wenig an das Sekretärinnenproblem mit der Problemgröße n = 2. Weitere Möglichkeiten im täglichen Leben sind ein Sonderangebot im Supermarkt, eine Wohnung, eine Arbeitsstelle, der Partner fürs Leben etc. Stets steht man vor dem Dilemma, sich für oder gegen eine Alternative entscheiden zu müssen, ohne zu wissen, ob nicht noch eine bessere Gelegenheit kommt.

Algorithmus

Modellierung

Es seien X die zuerst gewählte Zahl (erstes Angebot) und Y die unbekannte zweite Zahl (zweites Angebot).

Bestimme zusätzlich eine (beliebige, zufällige und von den anderen beiden Zahlen unabhängige) dritte Zahl Z nach irgendeiner Wahrscheinlichkeitsverteilung, deren Dichte auf den reellen Zahlen nirgends verschwindet (etwa einer Normalverteilung).

Gilt nun $X\leq Z$, dann schätze X als kleinere Zahl; gilt X > Z, so schätze X als größere Zahl.

Voraussetzungen

Die Lösungsstrategie beruht auf den folgenden drei Annahmen:

• Es muss sichergestellt werden, dass $P(X < Y) = P(Y < X) = \tfrac 12$ gilt.
• Die Zufallsvariable Z muss eine Dichtefunktion besitzen, die auf der gesamten reellen Achse positiv ist.
• Die Zufallsvariable Z ist unabhängig von X und Y.

Berechnung der Erfolgswahrscheinlichkeit

Es können drei Fälle eintreten:

Fall A

$X \leq Z$ und $Y \leq Z$, also ist Z größer sowohl als X als auch Y, oder höchstens gleichgroß.

Dann fällt die Wahl wegen $X \leq Z$ auf Y.

Fall B

$X \leq Z \leq Y$ oder $Y \leq Z < X$, also liegt Z zwischen X und Y (einschließlich).

Dann fällt für $X \leq Z \leq Y$ die Wahl auf Y, für $Y \leq Z < X$ auf X.

Fall C

X > Z und Y > Z, also ist Z sowohl kleiner als X als auch Y.

Dann fällt die Wahl wegen X > Z auf X.

Da immer einer der Fälle A, B oder C eintritt, ist P(A) + P(B) + P(C) = 1.

In den Fällen A und C trifft man letztlich eine Zufallswahl und die Wahrscheinlichkeit, die größere der beiden Zahlen X oder Y zu wählen, ist gleich $\tfrac{1}{2}$. Im Fall B wählt man mit Sicherheit, also mit der Wahrscheinlichkeit 1, die größere der beiden Zahlen.

Die Wahrscheinlichkeit P(G), die größte Zahl zu treffen, ist daher

$P(G)=\tfrac{1}{2}\ P(A)+1\ P(B)+\tfrac{1}{2}\ P(C)=\tfrac{1}{2}\left[P(A)+P(B)+P(C)\right]+\tfrac{1}{2}P(B)=\tfrac{1}{2} + \tfrac{1}{2}P(B)$

P(G) ist somit größer als $\tfrac{1}{2}$, falls $\tfrac{1}{2}$P(B) größer als Null ist. Somit ergibt sich durch die Verfolgung der oben erläuterten Strategie eine Erhöhung der Wahrscheinlichkeit, die größere Zahl zu wählen, über $\tfrac{1}{2}$ hinaus.

Im Spezialfall, dass X und Y selbst als unabhängige Realisierungen einer stetigen Zufallsvariable mit identischer Verteilungsfunktion F gegeben sind, lässt sich die Erfolgwahrscheinlichkeit quantifizieren: Wenn g die Dichte von Z bezeichnet, so folgt

$P(G)=\tfrac{1}{2} + \int F(z) (1-F(z)) g(z) dz$.

Die optimale Wahl von Z

Es stellt sich die Frage, wie man Z optimal wählt.

P(G), die Wahrscheinlichkeit, die größere der beiden Zahlen zu treffen, wird dann maximal, wenn P(B) maximal wird, also die Wahrscheinlichkeit, ein Z zu finden, das zwischen X und Y liegt. Das theoretische Maximum P(B)=1 lässt sich aber nicht erreichen, da die Dichtefunktion von Z nirgends verschwinden darf. Für die genaue Wahl der Verteilung von Z lassen sich keine allgemeinen Regeln angeben, eine gute Wahl hängt von der konkreten Situation ab.

Beim Eingangsbeispiel des Hauskaufs beispielsweise gibt es eine Spannbreite, innerhalb derer die Zahlen sinnvoll erscheinen, allerdings sind - bei einem normalen Haus - beispielsweise Zahlen von kleiner als 10.000 oder von größer als 10 Millionen äußerst unwahrscheinlich. Sinnvollerweise sollte man den Erwartungswert von Z in der Nähe des Marktwerts des Hauses ansiedeln; die Varianz von Z sollte man umso kleiner wählen, je genauer man den Marktwert abschätzen kann.

Vorwissen

Je nach Vorwissen kann eine andere Strategie als die obige zweckmäßiger sein, beispielsweise bei einem Einkauf im Supermarkt: Wenn eine Kundin erkennt, dass ein Produkt zu einem Preis angeboten wird, der nie zuvor unterboten worden ist, wird sie die Wahrscheinlichkeit, dass dieses Produkt in einem anderen Laden günstiger angeboten wird, als sehr gering einschätzen, eine Anwendung der obigen Strategie wäre widersinnig. Ein Kunde hingegen, der dieses Produkt noch nie gekauft hat, und der auch sonst keine Vorinformationen hat, kann sehr wohl nach obiger Methode vorgehen.

Verwandte Themen

Zwei-Zettel-Spiel und Umtauschparadoxon

Das Zwei-Zettel-Spiel hat eine gewisse Ähnlichkeit mit dem Umtauschparadoxon. Während aber beim Zwei-Zettel-Spiel die Überraschung darin besteht, dass es eine sinnvolle Tauschstrategie gibt, kommt das Umtauschparadoxon scheinbar zur paradoxen Lösung, dass man immer tauschen soll. Das Umtauschparadoxon wird gelöst, indem man den Widerspruch in der Schlussfolgerung aufdeckt und wäre auch gelöst, wenn es egal wäre, welchen Umschlag man nimmt; das Zwei-Zettel-Spiel zeigt darüber hinaus, dass es tatsächlich sinnvolle Tauschstrategien gibt, die sich aber von der Strategie “tausche immer” unterscheiden.

Andere verwandte Themen

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

• Gefangenenparadoxon
• Odds-Strategie
• Sekretärinnenproblem
• Ziegenproblem

Literatur

• F. Thomas Bruss: Der Ungewissheit ein Schnippchen schlagen. In: Spektrum der Wissenschaft. 06/2000. Spektrum der Wissenschaft Verlagsgesellschaft, S. 106 pdf
• Cover, T. (1987): Open Problems in Communication and Computation. Problem 5.1: Pick the largest number. Springer Verlag, New York. (englisch). ISBN 3540966218 pdf.

Weblinks

• http://www.wissenschaft-online.de/abo/spektrum/archiv/4947