Spieltheorie - Erwartete Kosten für Erfolg

04.03.2020, 18:20

Shinoro

Spieltheorie - Erwartete Kosten für Erfolg

Hallo zusammen,

stehe gerade vor folgender Fragestellung:
In einem Spiel soll ein Gegenstand in seiner Stufe verstärkt werden. Basis Level ist 0, höchste Stufe ist 5. Der Spieler kann, für einen festen Betrag k, versuchen den Gegenstand zu verbessern. Die Kosten je Versuch sind unabhängig von der Stufe.

Chance auf erreichen einer Stufe:
Stufe 0 --> Stufe 1: 35%
Stufe 1 --> Stufe 2: 30%
Stufe 2 --> Stufe 3: 25%
Stufe 3 --> Stufe 4: 20%
Stufe 4 --> Stufe 5: 8%

Bei erfolgreicher Verbesserung, steigt der Gegenstand um 1 Stufe, bei Misserfolg sinkt er wieder auf die vorherige Stufe (nicht unter 0).

Der Spieler hat nicht nur die Möglichkeit den Gegenstand selbst zu verbessern, sondern alternativ den fertigen Stufe 5 Gegenstand für Betrag y zu kaufen.

Frage: Wie entscheidet man, welche Option günstiger ist?

Habe versucht es mit einem Baumdiagramm zu lösen, aber weiß leider nicht wie ich mit der Rekursion umgehen soll.

Alternativ habe ich folgenden Ansatz:
Sei $\begin{eqnarray*} k \in \mathbb{N} \end{eqnarray*}$ die Kosten pro Versuch, $\begin{eqnarray*} y \in \mathbb{N} \end{eqnarray*}$ die Kosten für den direkten Kauf des fertigen Stufe 5 Gegenstands.

Chancen auf Erfolg:
$\begin{eqnarray*} x_{0} = \frac{35}{100}, x_{1} = \frac{30}{100}, x_{2} = \frac{25}{100}, x_{3} = \frac{20}{100}, x_{4} = \frac{8}{100} \end{eqnarray*}$

Sei $\begin{eqnarray*} s_{n} \end{eqnarray*}$ die Summe der Kosten bis Stufe $\begin{eqnarray*} n \end{eqnarray*}$ .

$\begin{eqnarray*} S_{0} = \frac{1}{x_{0}} * k = \frac{k}{x_{0}} \end{eqnarray*}$

$\begin{eqnarray*} S_{n} = \frac{k}{x_{n}} + S_{n-1} \end{eqnarray*}$

Wenn $\begin{eqnarray*} S_{n} < y \end{eqnarray*}$ dann selbst versuchen, sonst kaufen.

Ist mein Ansatz korrekt? Oder hat jemand vielleicht einen Vorschlag für "einfachere" Alternativen?
Hoffe das ist so okay mit latex, habe damit noch nie gearbeitet :p

Danke schon mal im Voraus smile

04.03.2020, 22:18

Dopap

Auf diesen Beitrag antworten »

Ich würde die $\begin{eqnarray*} x_i\quad i=0,1...,4 \end{eqnarray*}$ in $\begin{eqnarray*} p_i \end{eqnarray*}$ wegen probability umbenennen.
und mit Erwartungswerten arbeiten
und rückwärts beginnend mit

$\begin{eqnarray*} E_5=p_4k+(1-p_4)E_4 \end{eqnarray*}$

$\begin{eqnarray*} E_4=p_3k+(1-p_3)E_3 \end{eqnarray*}$

... u.s.w. bis $\begin{eqnarray*} E_0 \end{eqnarray*}$ auftaucht

wäre so mein spontaner Einfall verwirrt

05.03.2020, 00:06

Ulrich Ruhnau

Auf diesen Beitrag antworten »

Ich bin beim Vorschlag von Dopap skeptisch und fange erst einmal mit $\begin{eqnarray*} E_1 \end{eqnarray*}$ an. Sei $\begin{eqnarray*} p=p_0 \end{eqnarray*}$

$\begin{eqnarray*} E_1=k(p+2pq+3pq^2+4pq^3+\dots) \end{eqnarray*}$ wobei $\begin{eqnarray*} q=1-p \end{eqnarray*}$ .

Um diese Summe auszurechnen, definiere ich

$\begin{eqnarray*} R(q)=1+q+q^2+q^3+q^4+\dots=\frac 1{1-q} \end{eqnarray*}$

Ableiten dieser Funktion ergibt:

$\begin{eqnarray*} R'(q)=1+2q+3q^2+4q^3+\dots=\frac 1{(1-q)^2}=\frac 1{p^2} \end{eqnarray*}$

Also ergibt sich für unsern Erwartungswert

$\begin{eqnarray*} E_1=kp\frac 1{p^2}=\frac kp \end{eqnarray*}$

Das zeigt, daß Du mit Deiner Formel zumindest bei E_1 recht hast. Wenn Du nicht geschrieben hättest

Zitat:

Bei erfolgreicher Verbesserung, steigt der Gegenstand um 1 Stufe, bei Misserfolg sinkt er wieder auf die vorherige Stufe (nicht unter 0).

würde ich Dir auch bei $\begin{eqnarray*} E_2 \dots E_5 \end{eqnarray*}$ recht geben. Zum Anderen hat sich hier Dopaps Formel nicht bestätigt, denn $\begin{eqnarray*} E_0 = 0 \end{eqnarray*}$ . Deshalb muß ich eine neue Formel basteln.

Die Formel $\begin{eqnarray*} E_2=\frac {E_1}{p_1} \end{eqnarray*}$ ist ein möglicher Kandidat. Morgen geht es weiter.

05.03.2020, 10:55

Ulrich Ruhnau

Auf diesen Beitrag antworten »

Die Aufgabe ist für mich zu kniffelig um gleich eine Lösung zu präsentieren.
Mit Matlab habe ich ein 30-Zeilen-Programm geschrieben, nur allein um den folgenen Baum in Latex zu generieren, der darstellt, wie man von einem Level zum nächsten gelangt:
$\begin{eqnarray*} \begin{smallmatrix} && && && && && && && && && && 5 \\ && && && && && && && && &&\stackrel{p_4}\nearrow && \\ && && && && && && && && 4 && && \\ && && && && && && &&\stackrel{p_3}\nearrow && &&\stackrel{q_4}\searrow && \\ && && && && && && 3 && && && && 3 \\ && && && && &&\stackrel{p_2}\nearrow && &&\stackrel{q_3}\searrow && && && \\ && && && && 2 && && && && 2 && && \\ && && &&\stackrel{p_1}\nearrow && &&\stackrel{q_2}\searrow && && && && && \\ && && 1 && && && && 1 && && && && \\ &&\stackrel{p_0}\nearrow && &&\stackrel{q_1}\searrow && && && && && && && \\ 0 && && && && 0 && && && && && && \\ &&\stackrel{q_0}\searrow && && && && && && && && && \\ && && 0 && && && && && && && && \end{smallmatrix} \end{eqnarray*}$ Kann mir vielleicht einer hier sagen, wie man solche Baumdiagramme einfacher produziert?
Um hier weiter zu kommen, muß ich das Problem noch weiter anschauen.

05.03.2020, 13:05

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von Ulrich Ruhnau
Die Aufgabe ist für mich zu kniffelig um gleich eine Lösung zu präsentieren.

Die Idee von Dopap, das über ein Gleichungssystem zu lösen, ist doch in Ordnung. Nur ist sein Gleichungssystem nicht korrekt.

Es sei $\begin{eqnarray*} p_i \end{eqnarray*}$ die Wahrscheinlichkeit, von der Stufe $\begin{eqnarray*} i \end{eqnarray*}$ zur Stufe $\begin{eqnarray*} i+1 \end{eqnarray*}$ zu gelangen. Es Sei $\begin{eqnarray*} E_i \end{eqnarray*}$ der Erwartungswert für die Zahl der Versuche, um von der Stufe $\begin{eqnarray*} i \end{eqnarray*}$ zur Stufe $\begin{eqnarray*} 5 \end{eqnarray*}$ zu gelangen. Die Erwartungswerte sind also bei mir anders nummeriert als bei Dopap und sie enthalten noch nicht den Kostenfaktor $\begin{eqnarray*} k \end{eqnarray*}$ . Es ergibt sich folgendes Gleichungssystem:

$\begin{eqnarray*} E_0=1+p_0E_1+(1-p_0)E_0 \end{eqnarray*}$

$\begin{eqnarray*} E_1=1+p_1E_2+(1-p_1)E_0 \end{eqnarray*}$

$\begin{eqnarray*} E_2=1+p_2E_3+(1-p_2)E_1 \end{eqnarray*}$

$\begin{eqnarray*} E_3=1+p_3E_4+(1-p_3)E_2 \end{eqnarray*}$

$\begin{eqnarray*} E_4=1+(1-p_4)E_3 \end{eqnarray*}$

Die Lösung des Gleichungssystem ergibt:

$\begin{eqnarray*} E_0=\frac {12753}{7} \end{eqnarray*}$

Für den Erwartungswert der Kosten ist das mit $\begin{eqnarray*} k \end{eqnarray*}$ zu multiplizieren.

05.03.2020, 14:05

Dopap

Auf diesen Beitrag antworten »

meine schnelle Simulation ergibt im Schnitt $\begin{eqnarray*} 8.66 k \end{eqnarray*}$ Kosten bis zum für das Erreichen der letzten Stufe.

Kommt mir ein wenig Wenig vor verwirrt

edit: p mit q verwechselt unglücklich

05.03.2020, 14:12

Huggy

Auf diesen Beitrag antworten »

Das kann ja gar nicht sein. Selbst wenn man schon auf Stufe 4 wäre und von der Stufe nicht mehr zurückfallen könnte, bräuchte man im Mittel 12.5 Versuche, um von dort auf Stufe 5 zu kommen, also 12.5 k Kosten.

05.03.2020, 14:26

Dopap

Auf diesen Beitrag antworten »

alles klar, leider überall p mit q verwechselt unglücklich

05.03.2020, 16:06

Ulrich Ruhnau

Auf diesen Beitrag antworten »

Zitat:

Original von Huggy
$\begin{eqnarray*} E_0=1+p_0E_1+(1-p_0)E_0 \end{eqnarray*}$

$\begin{eqnarray*} E_1=1+p_1E_2+(1-p_1)E_0 \end{eqnarray*}$

$\begin{eqnarray*} E_2=1+p_2E_3+(1-p_2)E_1 \end{eqnarray*}$

$\begin{eqnarray*} E_3=1+p_3E_4+(1-p_3)E_2 \end{eqnarray*}$

$\begin{eqnarray*} E_4=1+(1-p_4)E_3 \end{eqnarray*}$

Hallo Huggy,

könntest Du uns mal erklären, wie Du deine Gleichungen herleitest? Ich hoffe, daß Du mit meinem Baumdiagramm einverstanden bist. Außerdem habe ich mit Matlab einfach mal dein Gleichungssystem als Matrix eingegeben und gelöst. Ich erhalte:

$\begin{eqnarray*} \begin{pmatrix} 1 \\ 1 \\1\\1\\ 1\end{pmatrix}=\begin{pmatrix}0.35&-0.35& 0.00& 0.00& 0.00\ -0.70& 1.00&-0.30& 0.00& 0.00\ 0.00&-0.75& 1.00&-0.25& 0.00\ 0.00& 0.00&-0.80& 1.00&-0.20\ 0.00& 0.00& 0.00&-0.92& 1.00\end{pmatrix}\begin{pmatrix} E_0\\E_1\\E_2\\E_3\\E_4 \end{pmatrix} \quad \end{eqnarray*}$ $\begin{eqnarray*} \quad \begin{pmatrix} E_0\\E_1\\E_2\\E_3\\E_4 \end{pmatrix} = \frac 17\begin{pmatrix}12753 \\ 12733 \\12663\\12425\\ 11438\end{pmatrix} \end{eqnarray*}$

was keineswegs im Widerspruch zu dem steht, was Du bereits geschrieben hast.
Auch meine Simulation mit einer Million Versuchen hat ergeben, daß die relative Abweichung von Deinem theoretischen Wert knappe $\begin{eqnarray*} 10^{-5} \end{eqnarray*}$ betragen hat.

05.03.2020, 16:37

Dopap

Auf diesen Beitrag antworten »

nach meiner Korrektur ergeben sich $\begin{eqnarray*} \approx 1808 k \end{eqnarray*}$ Kosten bei 3000 Runden, während der genaue Wert von Huggy 1821.857 beträgt. smile

Die $\begin{eqnarray*} E_i \end{eqnarray*}$ sind Unterprogramme und werden mit den angegebenen Wkt's angesprungen bis E5 erreicht wird, wobei jeder Sprung mit k zu Buche schlägt.
Gestartet wird in E0

05.03.2020, 17:15

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von Ulrich Ruhnau
könntest Du uns mal erklären, wie Du deine Gleichungen herleitest?

Das Grundprinzip ist einfach. Man nimmt an, man würde die Erwartungswerte $\begin{eqnarray*} E_i \end{eqnarray*}$ kennen und lautet aus den Übergängen zwischen den Stufen Beziehungen zwischen den $\begin{eqnarray*} E_i \end{eqnarray*}$ her. Nehmen wir an, man befindet sich auf Stufe 0 und man sucht den Erwartungswert $\begin{eqnarray*} E_0 \end{eqnarray*}$ . Man macht auf jeden Fall einen Versuch. Das ist die $\begin{eqnarray*} 1 \end{eqnarray*}$ auf der rechten Seite der ersten Gleichung und analog auch bei den folgenden Gleichungen. Jetzt kommt man mit Wahrscheinlichkeit $\begin{eqnarray*} p_0 \end{eqnarray*}$ auf die Stufe 1, deren Erwartungswert $\begin{eqnarray*} E_1 \end{eqnarray*}$ ist. Zu der $\begin{eqnarray*} 1 \end{eqnarray*}$ ist daher $\begin{eqnarray*} p_0E_1 \end{eqnarray*}$ zu addieren. Mit Wahrscheinlichkeit $\begin{eqnarray*} (1-p_0) \end{eqnarray*}$ bleibt man im Zustand 0. Dafür ist dann $\begin{eqnarray*} (1-p_0)E_0 \end{eqnarray*}$ zu addieren. Fertig ist die erste Gleichung:

$\begin{eqnarray*} E_0=1+p_0E_1+(1-p_0)E_0 \end{eqnarray*}$

Die anderen Gleichungen folgen analog. In der letzten Gleichung habe ich den Summanden $\begin{eqnarray*} p_4E_5 \end{eqnarray*}$ wegen $\begin{eqnarray*} E_5=0 \end{eqnarray*}$ weggelassen.

Zitat:

Ich hoffe, daß Du mit meinem Baumdiagramm einverstanden bist.

Ja.

05.03.2020, 18:27

Ulrich Ruhnau

Auf diesen Beitrag antworten »

Zitat:

Original von Huggy
Jetzt kommt man mit Wahrscheinlichkeit $\begin{eqnarray*} p_0 \end{eqnarray*}$ auf die Stufe 1, deren Erwartungswert $\begin{eqnarray*} E_1 \end{eqnarray*}$ ist. Zu der $\begin{eqnarray*} 1 \end{eqnarray*}$ ist daher $\begin{eqnarray*} p_0E_1 \end{eqnarray*}$ zu addieren. Mit Wahrscheinlichkeit $\begin{eqnarray*} (1-p_0) \end{eqnarray*}$ bleibt man im Zustand 0. Dafür ist dann $\begin{eqnarray*} (1-p_0)E_0 \end{eqnarray*}$ zu addieren. Fertig ist die erste Gleichung:

$\begin{eqnarray*} E_0=1+p_0E_1+(1-p_0)E_0 \end{eqnarray*}$

Mit Satz 1 und 3 bin ich durchaus einverstanden. Aber Deine Sätze 2 und 4 erschließen sich mir nicht logisch. Warum willst Du addieren? Warum gerade $\begin{eqnarray*} p_0E_1 \end{eqnarray*}$ oder $\begin{eqnarray*} (1-p_0)E_0 \end{eqnarray*}$ ?

05.03.2020, 18:51

Huggy

Auf diesen Beitrag antworten »

Mir ist nicht klar, weshalb dir das nicht klar ist. Wenn man mit Sicherheit $\begin{eqnarray*} (p_0=1) \end{eqnarray*}$ in den Zustand 1 käme, würde doch gelten:

$\begin{eqnarray*} E_0=1+E_1 \end{eqnarray*}$

Wenn man aber nur bei einem Anteil $\begin{eqnarray*} p_0 \end{eqnarray*}$ der Versuche von 0 nach 1 kommt, ist auch nur für diesen Anteil $\begin{eqnarray*} E_1 \end{eqnarray*}$ zu addieren. Bei einem Anteil $\begin{eqnarray*} (1-p_0) \end{eqnarray*}$ der Versuche bleibt man im Zustand 0. Also ist mit diesem Anteil $\begin{eqnarray*} E_0 \end{eqnarray*}$ zu addieren.

Ich weiß nicht, wie ich das besser erklären soll. Aber vielleicht hilft es, mal den Übergang von Stufe 4 nach Stufe 5 zu betrachten unter der Annahme, dass man nicht unter Stufe 4 zurückfallen kann. Dann hätte man die Gleichung

$\begin{eqnarray*} E_4=1+p_4E_5+(1-p_4)E_4 \end{eqnarray*}$

Wegen $\begin{eqnarray*} E_5=0 \end{eqnarray*}$ ergibt das

$\begin{eqnarray*} E_4 =\frac 1 {p_4} \end{eqnarray*}$

Das hast du ja oben mit mehr Aufwand auch hergeleitet.

06.03.2020, 08:00

Ulrich Ruhnau

Auf diesen Beitrag antworten »

Zitat:

Original von Huggy
$\begin{eqnarray*} E_0=1+p_0E_1+(1-p_0)E_0 \end{eqnarray*}$

Hallo Huggy, nach langem Überlegen und einmal darüber Schlafen fällt bei mir endlich der Groschen. Ich würde so argumentierten:

Die Kosten $\begin{eqnarray*} E_0 \end{eqnarray*}$ , die man im Schnitt hat, den Gegenstand von Level 0 auf Level 5 zu verbessern, betragen den nächsten Einsatz also 1 (oder k) plus die Kosten, die man erwartungsgemäß nach seinem Einsatz hat. Mit der Wahrscheinlichkeit von $\begin{eqnarray*} p_0 \end{eqnarray*}$ sind das die Kosten $\begin{eqnarray*} E_1 \end{eqnarray*}$ und mit der Wahrscheinlichkeit von $\begin{eqnarray*} 1-p_0 \end{eqnarray*}$ die Kosten $\begin{eqnarray*} E_0 \end{eqnarray*}$ .

Neue Frage »

Antworten »

Spieltheorie - Erwartete Kosten für Erfolg

Verwandte Themen