Die Mathe-Redaktion - 22.12.2014 10:04 - Registrieren/Login
Auswahl
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Oktober 2014

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 256 Gäste und 20 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Kleine_Meerjungfrau Monkfish epsilonkugel
Mathematik » Stochastik und Statistik » Spiel: Augenzahl nicht überschätzen
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Spiel: Augenzahl nicht überschätzen
SirJective
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 07.09.2004
Mitteilungen: 1773
Aus: Münchner Norden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2012-02-08 22:55


Betrachten wir folgendes Spiel.

Es gibt einen Spielleiter und n Spieler, n >= 2. Der Spielleiter würfelt insgeheim mit einem fairen k-seitigen Würfel, k >= 2, mit den Augenzahlen 1 bis k. Jeder Spieler gibt insgeheim einen Tipp für die gewürfelte Augenzahl ab. Dann werden die gewürfelte Augenzahl und alle n Tipps aufgedeckt.

Unter all den Spielern, die die gewürfelte Augenzahl nicht überschätzt haben, gewinnen diejenigen, die die höchste Augenzahl genannt haben. (Wer sich hier an "Der Preis ist heiß" erinnert fühlt, tut das zurecht.) Der Gewinn beträgt 1, und alle Gewinner teilen den Gewinn gleichmäßig unter sich auf.

Nun meine Frage: Was ist eine optimale Strategie für dieses Spiel, und wie hoch ist der erwartete Gewinn?

Gruß,
SirJective



-----------------
Grübelmeister der Drachengilde Diskreter Falter Rechenmeister im Vorgarten Bewahrer von Irrlichts Liebe <!--Lies diese Signatur nicht! Sie ist widersprüchlich.-->



  Profil  Quote  Link auf diesen Beitrag Link
SirJective
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 07.09.2004
Mitteilungen: 1773
Aus: Münchner Norden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, vom Themenstarter, eingetragen 2012-02-08 23:01


Für den Fall n=2 und k=2 kann man folgende Aufstellung machen:
A B | 1  2  | E_A E_B
----|-------|--------
1 1 | AB AB | 1/2 1/2
1 2 | A  B  | 1/2 1/2
2 1 | B  A  | 1/2 1/2
2 2 | -  AB | 1/4 1/4

Die ersten beiden Spalten enthalten alle Kombinationen der Tipps von Spieler A und B, die folgenden zwei Spalten enthalten den Gewinner abhängig von der gewürfelten Augenzahl (es kann A allein gewinnen, oder B allein, oder beide zusammen, oder keiner von beiden), die letzten beiden Spalten enthalten den erwarteten Gewinn für Spieler A und B bei der jeweiligen Tipp-Kombination. Da es passieren kann, dass keiner gewinnt, ist die Summe der erwarteten Gewinne nicht immer gleich 1.

An dieser Aufstellung sieht man, dass der Tipp 1 einem Spieler einen erwarteten Gewinn von 1/2 garantiert, während der Tipp 2 einen erwarteten Gewinn liefert, der vom Tipp des anderen Spielers abhängt, aber 1/2 niemals überschreitet.

Für beide Spieler ist es also optimal, immer 1 zu tippen.

Gruß,
SirJective



  Profil  Quote  Link auf diesen Beitrag Link
SirJective
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 07.09.2004
Mitteilungen: 1773
Aus: Münchner Norden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2012-02-08 23:13


Für n=2 und k=3 ist die Tabelle etwas größer:
A B | 1  2  3  | E_A E_B
----|----------|--------
1 1 | AB AB AB | 3/6 3/6
1 2 | A  B  B  | 2/6 4/6
1 3 | A  A  B  | 4/6 2/6
2 1 | B  A  A  | 4/6 2/6
2 2 | -  AB AB | 2/6 2/6
2 3 | -  A  B  | 2/6 2/6
3 1 | B  B  A  | 2/6 4/6
3 2 | -  B  A  | 2/6 2/6
3 3 | -  -  AB | 1/6 1/6

Die letzten beiden Spalten kann man auch als Matrix darstellen, vielleicht sieht man manches besser so. Dargestellt ist (E_A, E_B) in Abhängigkeit vom Tipp von A und B:
fed-Code einblenden

Für keinen Spieler ist es optimal, 3 zu tippen, da sowohl der Tipp 1 als auch der Tipp 2 einen erwarteten Gewinn liefern, der niemals schlechter, aber manchmal besser ist, als der für Tipp 3. Also wird keiner der beiden Spieler die 3 tippen.

Nun komme ich zu dem Schluss, dass wir eine Situation wie im Gefangenendilemma haben:
Wenn beide Spieler 1 tippen, gewinnen beide Spieler 1/2.
Wenn beide Spieler 2 tippen, gewinnen beide Spieler 1/3.
Wenn ein Spieler 1 tippt, kann der andere sich verbessern, indem er 2 tippt, und so 2/3 gewinnen. Da beide Spieler dies wissen, werden beide immer 2 tippen.

Wenn die Spieler kooperieren, ist die optimale Strategie, immer 1 zu tippen.

Wenn die Spieler nicht kooperieren (wovon ich ausgehe), dann ist die optimale Strategie, immer 2 zu tippen.

Gruß,
SirJective

[ Nachricht wurde editiert von SirJective am 08.02.2012 23:26:02 ]



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 3398
Aus: Gifhorn (NDS)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2012-02-09 11:37


Hallo SirJective,

mit solchen Fragen beschäftigt sich die Spieltheorie ausführlich. Der einfachste Fall ist das 2-Personen-Nullsummenspiel. Jeder Spieler hat gewisse Optionen (hier einen Tipp abgeben), beide Spieler wählen gleichzeitig aus, ohne zu wissen, was der andere wählt und (wichtig!) Abhängig von der Auswahl ergibt sich eine Auszahlung, die der eine Spieler an den anderen zu tätigen hat (das ist die Nullsummeneigenschaft).
Solche Spiele auch Matrixspiele genannt hat man gut im Griff.

Je nach Interpretation der Zielfunktion passt Dein Spiel aber selbst bei zwei Spielern nicht in diese Klasse. Nämlich dann, wenn jeder Spieler nur seine eigene Auszahlung maximieren will und nicht etwa die Differenz zum anderen.

Für solche Spiele (auch mit mehreren Spielern) gibt es die Theorie des Nash-Gleichgewichts. Sie besagt, dass es immer mindestens einen Gleichgewichtspunkt (in gemischten Strategien) gibt.
D.h. jeder Spieler hat eine gemischte Strategie (er wählt verschiedene Optionen mit einer bestimmten Wahrscheinlichkeit). Wenn sich nun alle Spieler an ihre Strategie halten, dann ist es für keinen vorteilhaft von der Strategie abzuweichen.
Das ist in deinem Beispiel der Fall, wenn beide Spieler Option 2 wählen. Über Situationen wie von Dir beschrieben gibt es viele Beiträge unter dem Stichwort "Gefangenen-Dilemma"

In der klassischen Spieltheorie ist der Ansatz, dass es in Nicht-Gleichgewichtspunkten stets einen Spieler gibt, der sich durch eine Strategieänderung verbessern kann. Solche Punkte sollten also nicht stabil sein können.
Modernere Ansätze gehen von der beobachteten Realität aus, in der Nicht-Gleichgewichtspunkte unter bestimmten Umständen durchaus auftreten (zwei Ganoven, die sich gegenseitig ein Alibi geben, obwohl jeder im Fall einer Kron-Zeugenaussage besser wegkäme; Personen, die einen eigenen Nachteil in Kauf nehmen, um negatives Verhalten anderer zu bestrafen usw.)
Es wird untersucht, welche Effekte zu einer Stabilisierung von Nicht-Gleichgewichtspunkten führen können -- Vertrauen, Kooperation, Saktionierung. Der Ansatz ist hier i.d.R. eine wiederholte Durchführung eines Spiels.

Untersuchst Du die Frage rein interessehalber oder hast Du eine Anwendung über das Würfelspiel hinaus?

Viele Grüße,
Kitaktus



  Profil  Quote  Link auf diesen Beitrag Link
chryso
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.02.2009
Mitteilungen: 10407
Aus: Österreich
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2012-02-09 11:55


Ich würde dir auch raten, dich einmal mit dem hochinteressanten Gebiet der Spieltheorie häher zu beschäftigen.

Der Name "Spieltheorie"*) suggeriert, dieses Gebiet wäre für die Praxis nicht so wichtig, tatsächlich spielt es in der Wirtschaft eine Riesenrolle.

Nehmen wir einmal den Erdölpreis. Wenn die erdölexportierenden Länder sehr viel ausführen, fällt der Preis in den Keller und sie verdienen weniger als bei einer geringen Produktion mit einem hohen Preis pro Barrel. Wenn nun EIN Land ausschert, hat es den Vorteil der hohen Ausfuhr und des hohen Preises. Wenn nun alle so denken, ....
Noch besser wäre das Beispiel für die Produktion anderer Waren (weil hier nicht die Resoucenverknappung mitspielt.) Ich habe nur dieses Beispiel genommen, da ich mich an genau dieses Scenario erinnere.

LG chryso

*) Hier stand "Titel", bezog sich aber nicht auf den Titel dieses Threads, sondern auf das Fachgebiet.



-----------------
 Die deutsche Rechtschreibung ist Freeware, sprich, du kannst sie kostenlos nutzen. Allerdings ist sie nicht Open Source, d.h. du darfst sie nicht verändern oder in veränderter Form veröffentlichen.
[ Nachricht wurde editiert von chryso am 09.02.2012 16:18:35 ]



  Profil  Quote  Link auf diesen Beitrag Link
Buri
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2003
Mitteilungen: 39205
Aus: Dresden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2012-02-09 12:31


2012-02-09 11:55 - chryso in Beitrag No. 4 schreibt:
1. ... raten, dich einmal mit dem hochinteressanten Gebiet der Spieltheorie häher zu beschäftigen.
2. Der Titel suggeriert, dieses Gebiet wäre für die Praxis nicht so wichtig ...
Hi chryso,
du überlegst hier nicht ganz richtig.
1. Das mußt du Christian ganz gewiß nicht vorschlagen, denn das hat er schon längst getan.

2. Nein, der Titel suggeriert das nur solchen Leuten, die irrtümlich glauben, Spieltheorie wäre eine Spielerei verkorkster Mathematiker.
Der Begriff "Spiel gegen die Natur" ist in realitätsbezogenen Überlegungen zur Anwendung der Spieltheorie gebräuchlich, und dies zeigt doch, dass es keine ausschließliche Theorie, sondern für praktische Anwendung überaus aufgeschlossen ist.

Möglicherweise lautete der Titel, auf den du dich beziehst, vorher anders.

An der überragenden Bedeutung der Spieltheorie für Wirtschaft und Finanzwesen zweifeln indessen die Experten (also auch Christian) nicht.
Gruß Buri



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 3398
Aus: Gifhorn (NDS)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2012-02-09 14:26


Die Spieltheorie hat so nebenbei auch einen hochpolitischen Aspekt. Ohne das ich das beweisen könnte, vermute ich, dass die Erkenntnisse der Spieltheorie einen deutlichen Einfluß auf politische Entscheidungen, insbesondere in schwelenden Krisensituationen (insb. dem kalten Krieg) gehabt haben und haben werden.
Die Spieltheorie liefert nicht nur Aussagen, wie man sich in einer bestimmten Situation verhalten sollte, sie gibt auch Anregung, wie man (auch durch einseitige Maßnahmen) die Situation zum eigenen Vorteil verändern kann.
Manche dieser Maßnahmen widersprechen dabei durchaus der Intuition. Hat man keine Null-Summen-Spiele, dann kann man seine Lage mitunter verbessern, indem man sich selbst einiger Möglichkeiten endgültig beraubt.
Das Heikle daran ist, das solche Manipulationen zum eigenen Vorteil nicht selten zu Lasten anderer gehen. Um mal ein fiktives Beispiel zu nennen. Ein Geiselnehmer (mit mehreren Geiseln) droht damit einzelne Geiseln zu verletzen oder zu töten, wenn seine Forderungen nicht zu einem bestimmten Zeitraum erfüllt sind. Der Verhandlungsführer der Polizei hat die Möglichkeit die Forderungen zu erfüllen, oder die Zeit ablaufen zu lassen. Beides erscheint ihm nicht gerade verlockend. Um seine Position zu stärken gibt er seinen Leuten die Anweisung, den Geiselnehmer sofort und ohne weitere Anweisung unter Beschuß zu nehmen, falls dieser gegen eine der Geiseln Gewalt anwendet. Von dieser Anweisung setzt er auch den Geiselnehmer in Kenntnis.
Die Situation hat sich jetzt für den Geiselnehmer geändert, er kann nun nicht mehr ohne weiteres eine Geisel verletzen, um seinen Forderungen Nachdruck zu verleihen, weil er die Reaktion mit großer Wahrscheinlichkeit nicht überlebt. Der Verhandlungsführer der Polizei hat seine Position verbessert, in dem er sich die Option genommen hat, im Falle eines Angriffs auf eine Geisel einfach nichts zu tun und abzuwarten.
Leidtragende sind die Geiseln, die im Fall einer Eskalation extrem gefährdet sind.

Kitaktus



  Profil  Quote  Link auf diesen Beitrag Link
rlk
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.03.2007
Mitteilungen: 8482
Aus: Wien
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2012-02-09 16:10


Hallo,
die Rolle der Spieltheorie im Kalten Krieg wird zum Beispiel in dem Buch Prisoner's Dilemma: John Von Neumann, Game Theory and the Puzzle of the Bomb von William Poundstone beschrieben.

Gruß,
Roland



  Profil  Quote  Link auf diesen Beitrag Link
SirJective
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 07.09.2004
Mitteilungen: 1773
Aus: Münchner Norden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2012-02-10 23:56


Hallo Kitaktus,

ich habe mich interessehalber schon ab und zu mit Spieltheorie beschäftigt, daher sind mir die Begriffe Nullsummenspiel, Nash-Gleichgewicht und Gefangengendilemma bekannt.

Auch habe ich schon für einfache Spiele optimale Strategien ermittelt und die Gewinnwahrscheinlichkeit berechnet. (Einige davon im Rahmen von Projekt Euler.)

Da es in meinem Spiel auch passieren kann, dass keiner der n Spieler gewinnt, ist es kein Nullsummenspiel. Mein Ziel als Spieler wäre, meinen eigenen Gewinn zu maximieren, ohne den Gewinn meiner Mitspieler zu beachten. Wie ich schon festgestellt hatte, kann ich durch Kooperation den erwarteten Gewinn maximieren, genau wie beim Gefangenendilemma.

Was mich zunächst interessiert, ist eine optimale Strategie für die Situation, dass kein Spieler einen anderen Spieler kennt, und auch nicht wiederholt dieselben Spieler miteinander spielen. Hier muss ich doch annehmen, dass ich als Spieler nichts über die Strategie der Mitspieler weiß, außer dass sie ihrerseits versuchen, eine optimale Strategie anzuwenden, oder?

Diese Frage stelle ich aus reiner Neugier - ich habe das Spiel bisher weder gespielt, noch eingehend untersucht.

Gruß,
SirJective



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 3398
Aus: Gifhorn (NDS)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2012-02-13 12:27


Hallo,

ich habe mich noch nie damit beschäftigt, wie man Nicht-Null-Summen-Spiele algorithmisch "löst". N
Mein völlig naiver Ansatz wäre:
1) zuerst dominierte Zeilen und Spalten zu ermitteln, um diese zu eliminieren
2) eventuell auch auf echt konvex-dominierte Zeilen/Spalten achten (das sind solche, die durch eine Konvex-Kombination anderer Zeilen/Spalten echt dominiert werden)
3) dann eine gemischte Strategie suchen, die eine maximale Mindestauszahlung ergibt (so wie im Nullsummenspiel); möglicherweise kann man mit 3) auch gleich 2) und 1) miterledigen.

Vermutlich müsste man diesen Vorgang aus Sicht beider Spieler mehrfach wiederholen. Immer wenn sich ein Spieler entscheidet, dass er eine bestimmte Option überhaupt nicht nutzen wird, kann das dazu führen, dass sich für den anderen Spieler eine veränderte Situation ergibt und er ebenfalls eine (oder mehrere) Optionen verwirft.

Eine Schwierigkeit, die ich noch sehe, ist die Frage, was ist überhaupt eine optimale Strategie. Es kann mehrere Nash-Gleichgewichte geben und wenn man das Spiel nur einmal spielt, kann man u.U. nicht erwarten, auf einem davon zu landen.

Aber wie gesagt, die Theorie zur praktischen Auflösung von Nicht-Null-Summen-Spielen ist mir nicht bekannt.

Kitaktus



  Profil  Quote  Link auf diesen Beitrag Link
Aaba-Aaba
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 12.11.2008
Mitteilungen: 55
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2012-02-16 22:50


Hallo,

es gibt aber jede Menge Situationen in der Wirtschaft, bei denen man nicht von Nullsummenspielen sprechen kann.

Zum Beispiel Enron und die Energiekrise in Kalifornien im Jahr 2000, die die Wahl von Gouverneur Schwarzenegger begünstigte.

en.wikipedia.org/wiki/2000_California_energy_crisis
"The crisis cost $40 to $45 billion."
( Die Krise kostete 40 bis 45 Milliarden US-Dollar. )

www.wsws.org/articles/2005/feb2005/enro-f09.shtml
"However, according to one report, Enron reaped at least
$1.6 billion in profits due to the California power shortages alone."
( Der Profit von Enron durch die Krise wird auf 1,6 Milliarden US-Dollar geschätzt. )

Enron hat also für Profite von 1,6 Millarden USD einen Schaden von 40 bis 45 Milliarden USD angerichtet. D.h. wenn die Relation 1,6 zu 40 Milliarden gilt, dann hat man für die Profite den 25-fachen Schaden angerichtet.

siehe auch Dokumentation:
www.amazon.de/Enron-Smartest-Arthaus-Collection-Dokumentarfilm/dp/B002DOSVJ8/ref=sr_1_1?ie=UTF8&qid=1328886191&sr=8-1

Gruß



  Profil  Quote  Link auf diesen Beitrag Link
Bozzo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.04.2011
Mitteilungen: 1819
Aus: Franken
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2012-02-17 04:07


Jedes Mehrpersonenspiel wird durch die Hinzunahme eines fiktiven Spielers mit nur einer Strategie zu einem Nullsummenspiel.  Nullsummenspiele sind daher eigentlich nur bei Zweipersonenspielen interessant.  Hier haben wir ein symmetrisches Spiel, da bin ich nicht sicher, ob die Nullsummeneigenschaft etwas nützen würde.



  Profil  Quote  Link auf diesen Beitrag Link
janschnei
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 05.01.2003
Mitteilungen: 500
Aus: Hannover
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2012-02-17 10:12


Beim kurzen Überfliegen der Diskussion hatte ich gerade folgenden Gedanken:

Angenommen, jeder Spieler will seine eigene Punktzahl maximieren und jeder Spieler ist rational, spielt also die optimale (gemischte) Strategie. Dann müsste die erwartete Punktzahl für alle Spieler nach Ablauf mehrerer Spiele gleich hoch sein. Dieser Wert ist aber gerade dann maximal, wenn in jedem Spiel Punkte vergeben wurden. Und das kann (ohne Absprachen der Spieler) nur erreicht werden, wenn alle Spieler immer 1 tippen. Diese Strategie wäre unabhängig von der Zahl der Spieler und der Art des Würfels.

Offensichtlich ist das beschriebene Szenario kein Nash-Gleichgewicht (für Würfel mit mehr als zwei Seiten), es sollte aber pareto-optimal sein. Letztlich ist man also wieder genau beim gleichen Problem, wie beim Gefangenen-Dilemma. Die Frage nach der optimalen Strategie ist so wohl stark abhängig von der Definition der Optimalität.



  Profil  Quote  Link auf diesen Beitrag Link
SirJective
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 07.09.2004
Mitteilungen: 1773
Aus: Münchner Norden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, vom Themenstarter, eingetragen 2012-02-19 13:56


Eine einfach zu prüfende Definition von Optimalität wäre folgende:

Die Strategie von Spieler A ist optimal, wenn das Minimum des erwarteten Gewinns für Spieler A über alle möglichen Strategien von Spieler B maximal ist. Mit anderen Worten, egal welche Strategie Spieler B wählt, die Strategie für Spieler A garantiert einen maximalen erwarteten Mindestgewinn.

Zum Beispiel für k=2 und n=4 ist folgende Strategie in diesem Sinne optimal (vorerst ohne Beweis):
Spieler A tippt "1" zu 50% und "3" zu 50%. Damit beträgt der erwartete Gewinn mindestens 3/8. Wenn Spieler B in seiner Strategie auch auf "1" oder "4" tippt, erhöht sich der erwartete Gewinn von Spieler A.

@Kitaktus:
Dein Ansatz liefert anscheinend eine in obigem Sinne optimale Strategie.
Und die gefundene Strategie (auch für andere Werte von n, die ich angeschaut habe) hat die Tippwahrscheinlichkeit 0% für Tipps, die durch einen anderen Tipp dominiert werden ("4"). Der andere 0%-Tipp hier, "2", wird aber nicht von irgendeiner Kombination der anderen Tipps dominiert.

Gruß,
SirJective

[ Nachricht wurde editiert von SirJective am 19.02.2012 14:08:32 ]



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 3398
Aus: Gifhorn (NDS)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2012-02-21 13:20


@SirJective:

Diese Definition von Optimalität ist nicht so ganz das Wahre. Folgendes Szenario ist ja möglich. Ich habe eine ganz tolle Option, die fast immer viel besser ist, als alles andere. Aber bei einer Wahl meines Gegenspielers schneidet sie leider sehr sehr schlecht ab.
Nach Deiner Definition müsste man sich jetzt eine andere Option suchen, die diese Katastophe verhindert.
Tatsächlich kann es aber sein, dass mein Gegensieler diese Option nie wählen würde, weil sie für ihn ganz schlecht ist.

Kitaktus



  Profil  Quote  Link auf diesen Beitrag Link
Bozzo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.04.2011
Mitteilungen: 1819
Aus: Franken
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2012-02-21 17:55


Die Max-Min-Strategie ist m. E. schon immernoch "die" optimale Strategie, wenn man keine Zusatzannahmen über den Gegner treffen kann.  Nash hat zwar mit die Idee eingeführt, daminierte Strategieen sollten das Geschehen nicht beeinflussen, aber in der Praxis hat sich gezeigt, dass sie durchaus als "Drohstrategien" von Interesse sein können.

Betrachte z. B. folgendes Spiel mit Auszahlungen (A,B):

A\B12
1(1,1)(-10,100)
2(-10,10)(-100,-1'000'000)


Das einzige Nash-Gleichgewicht liegt hier bei den Strategien (A,B)=(1,2) mit den Auszahlungen (-10,100).  Was aber passiert, wenn Spieler A ankündigt: "Ich habe hier ein Kartenspiel mit 52 Karten.  Mein Anwalt wird gleich eine Karte daraus ziehen.  Ist es das Pik-Ass, wird er für mich einleiten, dass ich Strategie 2 spiele.  Anderenfalls werde ich Strategie 1 spielen lassen.  Mein Anwalt hat die Weisung schriftlich und verbindlich von mir bekommen und muss sich daran halten.  Ich habe nachdem die Karte gezogen wurde keine Möglichkeit mehr auf die Strategie Einfluss zu nehmen."

Vorausgesetzt, Spieler B hält die Drohung für glaubwürdig, maximiert er danach seinen Gewinn durch Wahl der Strategie 1.  Durch diese Drohung konnte Spieler A die Auszahlung des Spiels von (-10,100) auf etwa (0.78,1.18) abändern, was ihm einen Gewinn von immerhin fast 11 gegenüber dem Nash-Gleichgewicht bringt.



  Profil  Quote  Link auf diesen Beitrag Link
SirJective
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 07.09.2004
Mitteilungen: 1773
Aus: Münchner Norden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, vom Themenstarter, eingetragen 2012-02-21 22:52


Hallo Kitaktus,

ich habe durch weitere Berechnungen festgestellt, dass es auch hier einen erheblichen Unterschied macht, wenn ich annehme, dass mein Gegenspieler bestimmte Optionen nicht wählen wird.

Ich betrachte nochmal n=2, k=4.

Wenn ich keine Annahmen über den Mitspieler treffe, dann ist die Max-Min-Strategie: 50% x 1, 50% x 3. (Mein Gewinn ist dann mindestens 0,375 und höchstens 0,5, sein Gewinn ist mindestens 0,25 und höchstens 0,5.)

Wenn ich annehme, das der Mitspieler selbst eine Strategie wählt, die auf die Tipps 1 und 3 beschränkt ist, dann ist die Max-Min-Strategie, zu 100% die 1 zu tippen.

Folgende Tabelle zeigt die Max-Min-Strategie für eine Auswahl von Optionen des Mitspielers.

Optionen des Gegnerseigene Max-Min-Strategie
12341234min-Gewinn
XXXX5005000,375
XXX-5005000,375
X-X-1000000,5
X---0100000,75
-X--0010000,5
--X-1000000,5


Die drei reinen Strategien (immer 1, immer 2, immer 3) verhalten sich also wie Stein-Schere-Papier zueinander, allerdings mit unterschiedlichen Gewinnen.

Eine interessante Strategie habe ich noch gefunden: 20% x 1, 40% x 2, 40% x 3. Hier ist mein Gewinn mindestens 0,3 und höchstens 0,6, und mein Mitspieler hat unabhängig von seinem Tipp 1, 2 oder 3 stets den erwarteten Gewinn von 0,4. Wenn ich diese Strategie wähle, dann kann mein Mitspieler nicht durch eigene Wahl seinen Gewinn verbessern, sondern nur meinen Gewinn beeinflussen.

Gruß,
SirJective



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 3398
Aus: Gifhorn (NDS)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2012-02-22 11:15


@Bozzo:

Prinzipiell hast Du recht. Tatsächlich versuchen Menschen in der Praxis nicht ausschließlich ihren eigenen Gewinn zu maximieren, sondern opfern einen Teil ihres Gewinnes, um anderen (mit Strafe) drohen zu können, falls sie sich auf bestimmte Weise verhalten.

Drei Einwände:
1) Es gibt einen Unterschied zwischen dem "normalen" Matrixspiel und einem Matrixspiel "mit Kommunikation". Bei einem normalen Matrixspiel ist das Aussprechen von Drohungen einfach nicht vorgesehen, genausowenig wie das Absprechen von kooperativen Strategien. Ist so etwas möglich, dann kann man das Problem eben nicht mit den "normalen" Methoden bearbeiten.

2) Selbst wenn man "drohen" erlaubt, kann es trotzdem Optionen geben, die ein Spieler nie sinnvoll wählen wird.
Ein Beispiel: (leider nicht mit so einer schönen Tabelle)
A\B 1     2
1 (9,9) (0,0)
2 (1,9) (1,0)

A kann sich mit Option 2 einen Gewinn von 1 sichern, während er mit Option 1 Gefahr läuft gar nichts zu bekommen, falls B Option 2 wählt. Aber warum sollte B denn Option 2 wählen? Das bringt ihm keinerlei Vorteil. A kann also getrost Option 1 wählen.

3) Ich kann das aus dem Stegreif nicht überschauen, ob solche Drohungen bei symmetrischen Spielen (wenn A und B ihre gewählten Optionen tauschen, dann vertauscht sich auch ihr Gewinn) überhaupt möglich sind.

Kitaktus



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 3398
Aus: Gifhorn (NDS)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, eingetragen 2012-02-22 11:53


@SirJective:

Die Elimination von Option 4 erscheint mir richtig, sie wird durch jede der anderen drei Optionen dominiert. Danach kann man m.E. keine weitere Option mehr streichen. Die Option 2 wird eben nicht dominiert, auch nicht durch eine Konvex-Kombination aus 1 und 3.

Deine gemischte Strategie (1/5 2/5 2/5) hat eine interessante Eigenschaft. Es ist die einzige Strategie p, für die gilt: Wenn beide Spieler Strategie p spielen, dann ist es für keinen von ihnen vorteilhaft, von der Strategie p abzuweichen.

Das erinnert mich daran, dass es in letzter Zeit einige Forums-Fragen zu diesem Thema, aber eben auf abstraktem Niveau, gegeben hat.
Das geht dann in Richtung:
fed-Code einblenden
Es scheint da also schon eine Theorie zu geben.

Kitaktus



  Profil  Quote  Link auf diesen Beitrag Link
SirJective
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 07.09.2004
Mitteilungen: 1773
Aus: Münchner Norden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, vom Themenstarter, eingetragen 2012-02-23 20:50


2012-02-22 11:53 - Kitaktus in Beitrag No. 18 schreibt:
Deine gemischte Strategie (1/5 2/5 2/5) hat eine interessante Eigenschaft. Es ist die einzige Strategie p, für die gilt:

Wenn beide Spieler Strategie p spielen, dann ist es für keinen von ihnen vorteilhaft, von der Strategie p abzuweichen.

Das ist genau die Definition eines Nash-Gleichgewichts. :-)



  Profil  Quote  Link auf diesen Beitrag Link
Bozzo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.04.2011
Mitteilungen: 1819
Aus: Franken
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, eingetragen 2012-02-24 01:32


Findet ein Spiel wiederholt statt, gibt es implizit auch immer einen Informationsaustausch.  Spieler A könnte in meinem vorherigen Beispiel auch einfach mal Strategie 2, spielen anstatt die Drohung auszusprechen.  Hätte vermutlich dieselbe Wirkung.

Mal eine Überlegung:  Ich Spiele zusammen mit n-1 anderen Spieler.  Ich kenne die Strategien, die diese spielen werden.  Unter diesen Umständen, gibt es eine für mich optimale Strategie.  Ich bin aber mit der Auszahlung unter dieser Strategie nicht zufrieden, weil Spieler k in dieser Situation ein höheren Profit erhält als ich.  Also spiele ich die Strategie von Spieler k, wodurch ich zwar meinen Gewinn mindere, aber aus Symmetriegründen dann den von Spieler k auch.  Spieler k kann sich nun überlegen, ob er seine Strategie weiter führt, oder auf meine zuvor optimale Strategie umsteigt, die ja für ihn jetzt auch optimal sein muss.  Ich habe also quasi mit ihm den Platz gewechselt, und er befindet sich nun in der Situation, in der ich zuvor war.

Bedeutet das nicht jetzt aus Symmetriegründen schon, dass das beste, was ein Spieler an Gewinn erwarten kann 1/n ist?  Und das könnten alle erreichen, indem jeder auf die 1 setzt -- auch wenn das kein Gleichgewichtspunkt ist.

Ich vermute, dass es durch die Symmetrie, und da es sich um ein "Fast-Null-Summen-Spiel" handelt, immer ein symmetrisches Nash-Gleichgewicht (bei dem alle dieselbe Strategie spielen) gibt, bei dem alle mit einem Gewinn von 1/n-ε wegkommen.

Man könnte um sie zu finden zunächst das Spiel auf eine zyklische Skala verlegen, also falls k gewürfelt wurde und niemand k oder niedriger getippt hat, gewinnen die, die den höchsten Tipp abgegeben haben.  Jetzt handelt es sich um ein echtes Nullsummenspiel.  Es ist außerdem noch symmetrischer, da jetzt alle Tippmöglichkeiten gleichberechtigt sind.  Gefühlsmäßig sollte damit die Strategie alle Möglichkeiten gleichwahrscheinlich zu setzen optimal sein.  Ausgehend davon kann man vielleicht irgendwie beschreiben, was nun passiert, wenn man die zyklische Skala wieder öffnet, und wie man dabei die Strategie anzupassen hat.  Hmm -- oder vielleicht bringt das auch nichts, keine Ahnung.

Eine andere Frage hab ich aber noch, die mir interessant erscheint.  Beim Spiel zu n.  Angenommen k Spieler schließen sich zusammen und verabreden den gemeinsam erzielten Gewinn untereinander gleichmäßig zu verteilen.  Können sie sich derart gegen die anderen Spieler verschwören, dass sie sich zusammen einen Gewinn von mehr als k/n sichern können?  Ich denke nicht, ich kann aber nicht sagen, warum ich das nicht glaube.



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 3398
Aus: Gifhorn (NDS)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, eingetragen 2012-02-24 10:56


2012-02-23 20:50 - SirJective in Beitrag No. 19 schreibt:
2012-02-22 11:53 - Kitaktus in Beitrag No. 18 schreibt:
Deine gemischte Strategie (1/5 2/5 2/5) hat eine interessante Eigenschaft. Es ist die einzige Strategie p, für die gilt:

Wenn beide Spieler Strategie p spielen, dann ist es für keinen von ihnen vorteilhaft, von der Strategie p abzuweichen.

Das ist genau die Definition eines Nash-Gleichgewichts. :-)


Nein. Für ein Nash-Gleichgewicht ist es nicht nötig, dass zwei Spieler die gleiche Strategie spielen. Im allgemeinen Fall können verschiedene Spieler völlig unterschiedliche Optionen haben, so dass es gar keine "gleichen Strategien" gibt. Hier hat man aber ein symmetrisches Spiel (vielleicht gibt es da auch eine andere Fachbezeichnung), d.h. wenn zwei Spieler ihre gewählten Optionen tauschen, dann vertauscht sich auch ihre Auszahlung. Dadurch vereinfacht sich manches.

Kitaktus

PS: Die oben angegebene Situation ist natürlich ein Spezialfall des Nash-Gleichgewichts.



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 3398
Aus: Gifhorn (NDS)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.22, eingetragen 2012-02-24 11:27


2012-02-24 01:32 - Bozzo in Beitrag No. 20 schreibt:
Findet ein Spiel wiederholt statt, gibt es implizit auch immer einen Informationsaustausch.  Spieler A könnte in meinem vorherigen Beispiel auch einfach mal Strategie 2, spielen anstatt die Drohung auszusprechen.  
Ja, deshalb untersucht man in letzter Zeit verstärkt solche wiederholten Spiele.

Mal eine Überlegung:  Ich Spiele zusammen mit n-1 anderen Spieler.  Ich kenne die Strategien, die diese spielen werden. Unter diesen Umständen, gibt es eine für mich optimale Strategie. Ich bin aber mit der Auszahlung unter dieser Strategie nicht zufrieden, weil Spieler k in dieser Situation ein höheren Profit erhält als ich.  Also spiele ich die Strategie von Spieler k, wodurch ich zwar meinen Gewinn mindere, aber aus Symmetriegründen dann den von Spieler k auch.  Spieler k kann sich nun überlegen, ob er seine Strategie weiter führt, oder auf meine zuvor optimale Strategie umsteigt, die ja für ihn jetzt auch optimal sein muss.  Ich habe also quasi mit ihm den Platz gewechselt, und er befindet sich nun in der Situation, in der ich zuvor war.

Bedeutet das nicht jetzt aus Symmetriegründen schon, dass das beste, was ein Spieler an Gewinn erwarten kann 1/n ist?  Und das könnten alle erreichen, indem jeder auf die 1 setzt -- auch wenn das kein Gleichgewichtspunkt ist.
Die Überlegung ist gut, hat aber eine entscheidende Lücke. Wenn Spieler k tatsächlich zu meiner alten Strategie wechselt, dann hätten wir die Plätze getauscht und ich hätte mich echt verbessert. Es ist aber möglich, dass Spieler k noch andere Optionen hat, die für ihn genauso gut sind und es ist apriori nicht klar, wie sich in diesen Fällen meine Auszahlung ändert. Folgendes Beispiel zeigt, dass die Schlußfolgerung tatsächlich falsch ist.
Wir spielen das Spiel aus dem Themenstart. Es gibt n mögliche Würfelergebnisse und n+1 Spieler. Jede Situation, in der genau eine Option von zwei Spielern gewählt wird, alle anderen Optionen nur von einem, stellt ein Nash-Gleichgewicht dar (ein auch in der Auszahlung unsymmetrisches!). Wenn ich einer der beiden Spieler bin, die den gleichen Tipp abgegeben haben, dann kann ich meinen Tipp zwar wechseln, beispielsweise auf den Tipp von Spieler k. Dabei sinkt tatsächlich die Auszahlung von k (von 1/n auf 1/(2n)). Würde er daraufhin meine alte Strategie übernehem, dann hätte ich mein Ziel erreicht. Er kann aber auch an seinem Tipp festhalten, wodurch sich für mich nichts zum besseren ändert.


Eine andere Frage hab ich aber noch, die mir interessant erscheint.  Beim Spiel zu n.  Angenommen k Spieler schließen sich zusammen und verabreden den gemeinsam erzielten Gewinn untereinander gleichmäßig zu verteilen.  Können sie sich derart gegen die anderen Spieler verschwören, dass sie sich zusammen einen Gewinn von mehr als k/n sichern können?  Ich denke nicht, ich kann aber nicht sagen, warum ich das nicht glaube.
Das obere Beispiel zeigt, dass sich Spieler tatsächlich verschwören können. Wenn meine n Gegenspieler sich verabreden alle verschiedene Tipps abzugeben, ist meine Auszahlung nur 1/(2n) und nicht 1/(n+1).
Die durchschnittliche Auszahlung der Verschwörer ist entsprechend höher. Betrachtet man das Szenario genauer, dann sieht man, dass sich die Mehrheit der Spieler stets zu ihrem Vorteil verschwören können.

Kitaktus



  Profil  Quote  Link auf diesen Beitrag Link
Bozzo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.04.2011
Mitteilungen: 1819
Aus: Franken
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.23, eingetragen 2012-02-24 14:00


Das ist ja fies.  Aber interessant!



  Profil  Quote  Link auf diesen Beitrag Link
SirJective
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 07.09.2004
Mitteilungen: 1773
Aus: Münchner Norden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.24, vom Themenstarter, eingetragen 2012-02-24 22:37


2012-02-24 10:56 - Kitaktus in Beitrag No. 21 schreibt:
Für ein Nash-Gleichgewicht ist es nicht nötig, dass zwei Spieler die gleiche Strategie spielen.

Meine Erwiderung war missverständlich. Ich hebe mal den Teil hervor, auf den ich mich bezog:

2012-02-23 20:50 - SirJective in Beitrag No. 19 schreibt:
2012-02-22 11:53 - Kitaktus in Beitrag No. 18 schreibt:
Es ist die einzige Strategie p, für die gilt:

Wenn beide Spieler Strategie p spielen, dann ist es für keinen von ihnen vorteilhaft, von der Strategie p abzuweichen.

Das ist genau die Definition eines Nash-Gleichgewichts. :-)

So besser? Ein Nash-Gleichgewicht ist dadurch charakterisiert, dass es für keinen Spieler vorteilhaft ist, von seiner Strategie abzuweichen (solange kein anderer Spieler von seiner Strategie abweicht).

Es ging mir nicht darum, dass beide dieselbe Strategie spielen.

[ Nachricht wurde editiert von SirJective am 24.02.2012 22:38:08 ]



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 3398
Aus: Gifhorn (NDS)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.25, eingetragen 2012-02-24 23:40


Ja, es sind Nash-Gleichgewichte, aber eben spezielle.



  Profil  Quote  Link auf diesen Beitrag Link
SirJective hat die Antworten auf ihre/seine Frage gesehen.
Bewerte diesen Thread:
[Was sonst bewertet wurde]
 Neues Thema [Neues Thema]

 Antworten [Antworten]   

 Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2014 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]