Proseminar  Wintersemester 97/98
Thema: Spieltheorie, Referent: Rainer Badenbach
 

Gliederung:

1. Kurze Einführung zur Spieltheorie
1.1 Kategorien nach denen Spiele eingeteilt werden
1.2 Definition des Begriffs ‘Strategie’

2. Theorie der Zweipersonen Nullsummenspiele
2.1 Klärung des Begriffs
2.2 Unterscheidung
      

  • stabile Spiele
          
  • instabile Spiele
    2.3 Lösungskonzept für Zweipersonen Nullsummenspiele
          
  • stabile Spiele
          
  • instabile Spiele

    3. Gefangendilemma
          

  • Erklärung des Problems
          
  • iterativer Fall
     
     

    - Literraturverzeichnis
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     

    1.Kurze Einführung zur Spieltheorie

    Früher waren Spiele nichts mehr als eine Freizeitbeschäftigung. Doch die Wissenschaft hat erkannt, daß sich mit Hilfe der theoretischen Grundlagen von Spielen Konfliktsituationen und Probleme im Alltag lösen lassen.
    Den Zusammenhang zwischen Spielen und ökonomischen Problemen wurde erstmals 1943 durch von Neumann und Morgenstern dargestellt. Die Spieltheorie findet immer dort eine Anwendung, wo die verschiedenen, zum Teil entgegengesetzten, Interessen mehrerer Parteien aufeinandertreffen.

    Definition: Ein Spiel ist ein mathematisches Modell für eine Konfliktsituation.

    Zurück zur Gliederung
     

    1.1 Kategorien nach denen Spiele eingeteilt werden

    Es gibt eine Vielzahl verschiedener Arten von Spielen. Für jede Art existieren Methoden, um das günstigste Verhalten eines Spielers im Spielablauf zu ermitteln. Zur schnellen und exakten Bestimmung dieser Methoden ist eine Einteilung der Spiele wichtig. Der Vorteil, Spiele in Kategorien einzuordnen, ist also der, daß man Folgerungen ziehen kann, die allgemein anwendbar sind.
    Die Spiele werden nach folgenden Kriterien eingeteilt :

  • Anzahl der Personen bzw. Parteien, die am Spiel beteiligt sind.(Schach: zwei)

  • Wie wird mit dem Gewinn bzw. Verlust verfahren ?
       Manchmal ist der Gewinn den ein Spieler erhalten könnte höher als sein möglicher Verlust.
       (Lotterie)
       Der Verlust des einen Spielers kann auch immer der Gewinn des anderen sein. (Poker)

  • Liegt ein Spiel mit Zufallseinfluss vor ? (Schach: nein; Würfeln: ja)

  • Welche Informationen über den Gegner sind vorhanden ?
       Es stellt sich die Frage, ob dem Spieler genau bekannt ist, welche Möglichkeiten seine
       Gegner zu jedem Zeitpunkt  im Spiel haben. (Dame: vollständig informiert)
     
     
     
    Zurück zur Gliederung
     
     
     
     
     
     
     
     
     
     

    1.2 Definition des Begriffs ‘Strategie’

    Im herkömmlichen Sprachgebrauch wird eine Möglichkeit ein Spiel nach einem bestimmten Vehalten oder in eine gewisse Richtung zu bestreiten als Strategie bezeichnet. Innerhalb der Spieltheorie muß die Strategie zu jedem Zeitpunkt im Spiel den nächsten Schritt bzw. Zug aufzeigen können.
    Die Darstellung aller möglichen Züge vom Anfang bis zum Ende des Spiels, läßt sich eindeutig durch einen Baum beschreiben. Durch jeden verschiedenen Weg von der Wurzel, über die einzelnen Knoten, zu einem Endkontenpunkt hin, wird ein anderer Spielausgang beschrieben. Durch einen dieser Spielzüge, sind die Strategien der Spieler (für eine Partie) genau beschrieben.
    Je nach dem, wie viele Verzweigungen von einem Knoten ausgehen, so viele verschiedene Züge hat der Spieler zu diesem Zeitpunkt zu Verfügung.

    Definition:

    Eine Strategie ist ein (vollständiger Verhaltens -) Plan, der für jede mögliche Position (Verzweigung des Baumes ) eine Fortsetzung vorsieht.
    Die im allgemeinen sehr große Anzahl von Strategien ergibt sich aus der Vielzahl vorhergehender Züge, auf die reagiert werden muß.
     
    Zurück zur Gliederung
     

    2.Theorie der Zweipersonen Nullsummenspiele

    2.1 Klärung des Begriffs

    Wie der Name schon sagt, gibt es zwei Spieler. Spiele, in denen die Interessen der Spieler entgegengesetzt sind, werden als Nullsummenspiele bezeichnet. Der Ausdruck Nullsumme beschreibt, daß im gesamten Spiel nichts dazukommt und nichts verloren geht. Will man gewinnen, muß man von einem anderen Mitspieler gewinnen. Die Summe der Gewinne ist immer null (ein Verlust ist ein negativer Gewinn).

    Zurück zur Gliederung
     
     
     

    2.2 Unterscheidung

  • stabile Spiele

    Wie schon bekannt, besitzt jeder Spieler verschiedene, anwendbare Strategien. Bei stabilen Spielen kennt jeder seine optimale Strategie, um sein Risiko zu minimieren. Also weicht keiner von dieser  Strategie ab. Sonst würde der Gegner einen Vorteil erlangen. Der Gewinn bzw. Verlust des jeweiligen Spielers ist am Ende immer derselbe.
    Diese Zahl  wird auch Wert des Spiels oder fester Sattelpunkt genannt.
     

     

  • instabile Spiele

    Bei stabilen Spielen ist die Entscheidung des Spielers im Grunde unabhängig von der Entscheidung seines Mitspielers. Wäre dies immer der Fall, könnte man die Spieltheorie als langweilig und überflüssig bezeichnen. Die Mehrzahl der Spielsituationen haben keinen festen Wert oder Sattelpunkt. Sie werden als instabil bezeichnet. Hier hängt die beste Strategie für einen Spieler von seinem Gegner ab.

    Zurück zur Gliederung
     
     

    2.3 Lösungskonzept für Zweipersonen Nullsummenspiele

    Ein Lösungskonzept sollte jeden Spieler anweisen, welche Strategie er zu wählen hat. Um ein solches Konzept aufzustellen, werden die Zweipersonen Nullsummenspiele als Matrixspiele dargestellt. Die m verschiedenen Strategien Si des Spielers P1 werden den m Zeilen einer Matrix  zugeordnet. Analog ordnet man den n verschiedenen Strategien Tj des Spielers P2 die n Spalten der gleichen Matrix  zu. Wählt nun P1 die Strategie Si  (Zeile i) und P2 zugleich die Strategie Tj (Spalte j), so ist mit dem resultierenden Element ai j der Gewinn von P1 beschrieben. Diesen Gewinn kann man als Auszahlung der Höhe aij von P2 an P1 deuten. Deshalb heißt die sich ergebende Matrix auch Auszahlmatrix.
    Diese Matrix wird immer bei der Lösung von stabilen bzw. instabilen Zweipersonen Nullsummenspielen erstellt. Hierzu eine Auszahlmatrix in allgemeiner Form:
     
     
     

    T1     .    Tj     .   Tn
       S1   a11      .     .     .   a1n
        .     . .     .     .     .
       S2     .     .    aij     .     .
        .     .     .     .     .     .
        S3    am1     .     .     .   amn
     

  • stabile Spiele

    Der Wert bzw. Sattelpunkt des Spiels kann erst durch die Betrachtung der Auszahlmatrix ermittelt werden.
    Die Vorgehensweise wird an der Beispielmatrix A gezeigt.
    Spielmatrix A:

     

        T1     T2      T3   MAX
        S1     -1      2      3      -1
        S2     -2      1      1      -2
        S3     -2     -3     -1      -3
      MIN     -1      2      3
     

    P1 nimmt an, daß sein Gegner optimal spielt. Egal welche Strategie P1 wählt, P2 minimiert den Gewinn von P1 immer. P2 wählt in jeder Zeile die niedrigste Zahl und passt seine Strategie an.

    Wählt P1:                                  Antwortet P2:                             Gewinn für P1:
          S1                                                 T1                                                -1
          S2                                                 T1                                                -2
          S3                                                 T2                                                -3
     

    P1 erhält hier drei ungünstige Fälle (Minima). Das Maximum der Minima (Max-Min hier: -1) ist für P1 die beste Alternative. Also wird P1 immer  die Strategie S1 wählen.
     

    Analog verhält sich Spieler P2. Er glaubt das P1 optimal spielt.
    P1 wählt in jeder Spalte die höchste Zahl und passt seine Strategie an.

    Wählt P2:                                  Antwortet P1:                             Gewinn für P2:
          T1                                                 S1                                                -1
          T2                                                 S1                                                 2
          T3                                                 S1                                                 3
     

    P2 erhält hier drei Maxima. Das Minimum der Maxima (Min-Max hier: -1) ist für P2 die beste Möglichkeit. Also wählt P2 immer T1.

    Insgesamt gesehen:

             P1 wählt immer S1
             P2 wählt immer T1
             Der Wert des Spiels ist immer -1

    Allgemeiner formuliert:

    Ein Spiel ist stabil, falls Zeilenminimum = Spaltenmaximum.
  • instabile Spiele

    Spielmatrix B:
     
     

        T1     T2      T3   MAX
        S1     -3      0      3      -3
        S2      2      3     -1      -1
        S3      0      2     -2      -2
      MIN      2      3      3
     

     

    Die meisten Spiele besitzen keinen Sattelpunkt. Hierzu betrachte man die Spielmatrix B. Zunächst geht man nach dem gleichen Schema vor, wie es bei den stabilen Spielen geschehen ist. Doch es stellt sich heraus:

                      Max-Min =/ Min-Max
                     -1 =/ 2
    Derartige Spiele werden als instabil bezeichnet.
    Zum besseren Verständnis, sei hier noch ein Gedankenexperiment dargestellt.
    Ein Beispiel einer instabilen Folge:

    P1 wählt S1 - P2 antwortet mit T1 - P1 wählt daraufhin S2 - P2 kontert mit T3 - P1 antwortet mit S1
     S1 - T1 - S2 - T3 - S1 ... (die Folge beginnt von vorne)

    Ein Lösungskonzept gestaltet sich hier wesentlich komplexer, als bei den stabilen Spielen. Die Lösung liegt in der sogenannten gemischten Strategie.
    Bei jedem Spielbeginn wählt man möglichst zufällig eine seiner Strategien aus. Diese Wahl ist aber an vorher definierte Wahrscheinlichkeiten gebunden, die aussagen, wie häufig eine Strategie vorkommen sollte. Das Ziel ist es, die Wahrscheinlichkeiten pi bzw. qj so zu bestimmen, daß das maximale Risiko minimiert wird.
    Zunächst berechnet man für jeden Spieler die sich aufgrund der Wahrscheinlichkeiten ergebenden mittleren Gewinne für jede Strategie des Gegners. Dann betrachtet man den minimalen Gewinn (aus Sicht des jeweiligen Spielers) und wählt die Wahrscheinlichkeiten so, daß dieser maximal wird (Max-Min, Min-Max).

    Dabei ist Ej  der mittlere Gewinn von P1, falls P2 die Strategie Tj wählt, und P1 seine Strategien mit den Wahrscheinlichkeiten pi wählt. Entsprechendes gilt für Fi von P2.
     
     

    Spieler P1                                                           Spieler P2
    E1 = p1a11 + p2a21 + ... + pmam1  (T1)               F1 = q1a11 + q2a12 + ... + qma1n  (S1)
    :                                                                               :
    E1 = p1a1j + p2a2j + ... + pmamj  (Tj)                   Fi = q1ai1 + q2ai2 + ... + qmain        (Si)
    :                                                                               :
    E1 = p1a1n + p2a2n + ... + pmamn  (Tn)                Fm = q1am1 + q2am2 + ... +qmamn (Sm)
     
     
     
     
     
     

    Max-Min-Strategie: Wähle pk so, daß das           Min-Max-Strategie: Wähle qk so,daß das
    minimale Ej = u maximal wird                               maximale Fi = w minimal wird.

    Vorher sollte man die Matrix durch Addition einer Konstanten positiv machen.
     
     p1a11 + p2a21 + ... + pmam1  >=  u-min             q1a11 + q2a12 + ... + qma1n       <= w- max
     :                                                                             :
     p1a1n + p2a2n + ... + pmamn >=  u                     q1am1 + q2am2 + ... + qmamn  <=  w
     p    + p       + ... +  pm       =  1                        q1        + q     + ... + qm      =  1
     

     
    Zusätzlich soll sein : umax = wmin
    Die Ungleichungssysteme werden nun mit 1/u und 1/w normiert.
    Zur Lösung dieser Ungleichungssysteme sei auf die Fachliteratur zur Linearoptimierung verwiesen.
     
    Zurück zur Gliederung 
     
     
     
     
     

    3. Gefangenendilemma

  • Erklärung des Problems

    Eine weit verbreitete und bekannte Spielsituation ist das Gefangenendilemma.
    Es handelt sich hier um ein Zweipersonen Nichtnullsummenspiel. Die Situation wird im folgenden beschrieben.
    Zwei Männer, die unter Verdacht stehen, zusammen ein Verbrechen begannen zu haben, werden von der Polizei verhaftet und in verschiedene Zellen eingesperrt. Beide können entweder ein Geständnis ablegen oder schweigen. Die möglichen Konsequenzen ihrer Handlung sind:

    1. Wenn der eine gesteht und sein Partner nicht, so wird der, der gestanden hat als Zeuge der
        Anklage freigelassen und der andere kommt für 20 Jahre ins Gefängnis.
    2. Wenn beide gestehen, müssen beide auf 5 Jahre ins Gefängnis.
    3. Wenn beide schweigen, müssen beide wegen unerlaubten Waffenbesitzes - eines weniger
        schwerwiegenden Anklagepunktes - auf 1 Jahr ins Gefängnis.
     
     

    Es bildet sich folgende Spielmatrix C:
     
     
    gestehen nicht gestehen
    gestehen 5 Jahre, 5 Jahre Freilassung, 20 Jahre
    nicht gestehen 20 Jahre, Freilassung 1 Jahr, 1 Jahr
     
     

    Sehen wir uns das Gefangendilemma aus der Perspektive eines der beden Angeklagten an.
    Er muß seine Entscheidung treffen, ohne zu wissen, wie sein Partner handeln wird.
    Angenommen, der Partner gesteht: unser Mann kann nun entweder schweigen und auf 20 Jahre ins Gefängnis gehen, oder gestehen und 5 Jahre im Gefängnis verbringen. Wenn der Partner schweigt, kann er ebenfalls schweigen und ein Jahr absitzen, oder gestehen und somit die Freiheit erlangen. Es ist anscheinend in jedem Fall das beste, wenn er gesteht !
    Wo liegt dann das Problem ?

    Das Paradoxe ist, daß zwei naive Gefangene schweigen, und nur ein Jahr sitzen. Zwei gescheite, spieltheoretisch bedachte, Gefangene gestehen und 5 Jahre sitzen. In der Zeit können sie dann viel über die Spieltheorie nachdenken.

    Noch eine weitere Überlegung:

    Jeder Spieler hat grundsätzlich zwei Möglichkeiten: er kann kooperativ oder nicht-kooperativ handeln. Wenn alle Spieler kooperativ handeln, ist dies für jeden einzelnen günstiger, als wenn alle nicht-kooperativ handeln. Gleichgültig aber, welche Strategie die anderen Spieler verfolgen, ist es für einen Spieler immer besser, nicht-kooperativ zu spielen.

    Zurück zur Gliederung
     
     
     
     

  • iterativer Fall

    Wenn das Spiel nur einmal gespielt wird, bleibt den Gefangenen fast keine andere Wahl, als zu gestehen.
    Was passiert aber wenn das Spiel öfters gespielt wird ?

    Nehmen wir an unsere Gefangenen leben ewig, und das Spiel wird 20 mal gespielt.
    Wenn einer der Angeklagten im ersten Spiel gesteht, so gibt er  seinem Partner den Anlaß, im zweiten Spiel auch zu gestehen. So werden die Gefangenen wahrscheinlich in allen weiteren Spielen  gestehen. Günstiger wäre es zu zeigen, daß man, zur Kooperation gewillt ist und nicht zu gestehen, in der Hoffnung, daß der Partner den richtigen  Schluss daraus zieht.
    Diese Strategie könnte zu einem kooperativen Ergebnis führen. Allerdings gibt es da ein Problem.
    Im zwanzigsten Spiel könnte der Gefangene wieder gestehen, weil dies die letzte Partie ist.
    Aber das ist noch nicht alles. Wenn es sinnlos ist, im zwanzigsten Jahr zu kooperieren, dann hat es auch keinen Zweck im neunzehnten Jahr zu kooperieren usw.
    Somit sollte man doch nicht kooperieren.
    Erst wenn das „Gefangenendilemma“ im unbegrenzten Zeitraum gespielt wird, kommt die Kooperation voll zur Geltung.
    Als Beispiel seien hier zwei Firmen erwähnt, die kooperieren. Die Konkurrenzunternehmen wissen wohl, daß sie nicht ewig im Geschäft bleiben werden. Aber sie können im allgemeinen nicht absehen, wann Fusionierung oder Bankrott ihren Konkurrenzkampf  beendet. Denn niemand weiß, wann die letzte Runde stattfinden wird !
    Bei den meisten Spielen ist man zufrieden, wenn man sagen kann, was ein vernünftiger Spieler tun sollte. Das Gefangenendilemma unterscheidet sich hier erheblich von anderen Spielen.
    Man sollte sich hier nicht die Frage stellen:
    „welche Strategie sollte eine vernünftige Person wählen“ sondern
    „wie können wir die Anwendung einer kooperativen Strategie rechtfertigen ?“
     
     
     

    Literaturverzeichnis:
     

  • Einführung in die Spieltheorie (Manfred Holler)

  • Strategie des Spiels (Max  Woitschach)

  • Introduction to Game Theory (Peter Morris)

  • Lehr - und Übungsbuch Mathematik: BAND IV

  • Skript: Hauske (Matrix A,B; Definition Strategie übernommen)

     
    Zurück zur Gliederung