Inhaltsverzeichnis

1  Einleitung  3

2  Terminologie und De nitionen  3

3  Existenz eines Gleichgewichts  7

3.1  Existenzbeweis unter Verwendung des Fixpunktsatzes von Brouwer  7

3.2  Existenzbeweis unter Verwendung des Fixpunktsatzes von Kaku-  

tani   9

4  Nash-Equilibrium in streng kompetitiven Spielen  10

5  Einblick in kooperative Spiele  13

6  Schlusswort und Ausblick  13

2

1 Einleitung

Die Spieltheorie (engl. game theory) ist ein Teilgebiet der Mathematik, das sich mit der Modellierung und Untersuchung von Gesellschaftsspielen, von im weitesten Sinn gesellschaftsspielähnlichen Interaktionssystemen sowie mit den in solchen Systemen eingesetzten Strategien beschäftigt. Dabei ist die Spieltheorie weniger eine zusammenhängende Theorie als vielmehr ein Instrument zur Analyse von strategischen Entscheidungssituationen. Lösungen von Spielen, die sich dadurch auszeichnen, dass die Spieler ihre Strategieentscheidungen nicht revidieren wollen wenn ihnen die Lösung empfohlen wird, werden als Gleichgewicht bezeichnet. Im Rahmen dieser Arbeit soll insbesondere auf ein allgemein akzeptiertes Konzept zur Lösung von nicht-kooperativen Spielen eingegangen werden, das Nash-Gleichgewicht. In einem weiteren Schritt wird genauer auf eine oft verwendete Art von Spielen, die sogenannten streng kompetitiven Spiele oder auch Nullsummenspiele, eingegangen und kurz angedeutet, wie die Theorie der nicht-kooperativen Spiele auf jene der kooperativen erweitert werden kann.

2 Terminologie und De…nitionen

Wir präsentieren hier die Basiskonzepte wie auch die notwendigen De…nitionen zum allgemeinen Verständnis der Spieltheorie. Die Herleitung der Idee und der Lösung von nicht-kooperativen Spielen folgen daraus implizit.

De…nition 1 Ein strategisches n-Personen Spiel G kann als Tripel

G :=< n; (( i ) i2n ; (a i ) i2n >

geschrieben werden. Dabei setzt sich das Spiel aus n Spielern zusammen, wobei jeder Spieler i über eine endliche Anzahl von reinen Strategien ii 2 i verfügt = 1; 2; :::; m. Die ii können in einer Menge i R ^m , der Strategiemenge des

n die entsprechende Produktmenge beziehungsweise das kartesische Produkt aus den Strategiemengen der einzelnen Spieler. Weiters wird jedem Spieler i eine stetige, quasikonkave ¹ Auszahlungsfunktion a i : i2n i ! R zugeordnet, welche die n-Tupel der Strategien nach R abbildet. 2

¹ Sei D R ⁿ konvex und f : D R ⁿ ! R: Wir sagen, dass f quasikonkav ist, falls die

Menge fx 2 D : f (x) > ag konvex ist für alle a 2 R. f ist quasikonvex, falls fx 2 D : f (x) 6 ag

konvex ist für alle a 2 R.

² Anstelle von Auszahlungsfunktionen sprechen manche Autoren (vgl. Osborne und Ru-

binstein, 1994) auch von Präferenzrelationen. Präferenzrelationen können als eine Verallge-

meinerung von Auszahlungsfunktionen angesehen werden.

3

Implizit wird in dieser De…nition angenommen, dass sich die gewählten Strategien in Spielausgängen niederschlagen, die dann zu verschiedenen Auszahlungen führen. Für eine explizite Modellierung kann der direkte Einbau von Spielausgängen hilfreich sein.

De…nition 2 (gemischte Strategie oder Randomisierung) Eine gemischte Strategie s i eines Spielers i ist eine Kombination seiner reinen Strategien ii 2 i und wird ebenfalls als ein Element von i betrachtet. Wir schreiben

P P

c ii ii 2 i mit c ii > 0 und s i = c ii = 1. Die gemischten Strategien s i

können also als Linearkombinationen angesehen werden. Wir unterstellen von nun an, dass die Menge i der s i eine nicht-leere, kompakte und konvexe Teilmenge des Euklidischen Raumes ist. 3

Bemerkung 3 Wir bemerken, dass eine pure Strategie ii auch immer als eine gemische Strategie s i geschrieben werden kann.

Beispiel 4 Ein Unternehmen i kann als Output die Menge i1 = 0 und i2 =

M produzieren sowie jede Menge zwischen 0 und M : 0 6 s i 6 M . Die Strategiemenge i = [0; M ] ist konvex, weil jede konvexe Kombination zwischen 0 und

M , das heisst M + (1 )0 = M mit 0 6 6 1, produziert werden kann. Da die Menge nach oben und unten beschränkt ist und 0 und M enthalten sind, ist i auch kompakt.

Die allgemeine Formulierung und die hohe Abstraktion erlauben es, diese De…nition in einer Reihe von Situationen anzuwenden. Ein Spieler kann ein Individuum sein oder eine beliebige andere Entscheidungseinheit, wie zum Beispiel eine Regierung, ein Verwaltungsrat, eine marxistische Revolutionsarmee, ja sogar sogar eine Blume oder ein Tier. Allerdings sind die Anwendungsmöglichkeiten dadurch beschränkt, dass jedem Spieler eine Auszahlungsfunktion zugeordnet werden muss. Als Auszahlungsfunktionen oder Präferenzrelationen können jedoch bereits die einfachen Gefühle eines Spieler bezüglich verschiedener Endzustände oder im Falle eines nicht-menschlichen Organismus die Wahrscheinlichkeit des reproduktiven Erfolgs verwendet werden.

Selbstverständlich bevorzugt Spieler i Strategie ii gegenüber ii falls

a i (:::; ii ; :::) > a i (:::; ii ; :::)

bei gegebenen j für j = 1; :::; i 1; i + 1; :::; n. Weiters ist es einfach einzusehen, dass a i problemlos auf gemischte Strategien erweitert werden kann. a i

³ Die Hauptidee der Einführung gemischter Strategien ist es, die diskreten puren Strategi-

en zu „stetig“ zu machen. Ritzberger (2003) erwähnt ebenfalls, dass gemischte Strategien

als Wahrscheinlichkeitsverteilungsfunktionen oder Verteilungsfunktion von puren Strategien

verstanden werden können.

4

ist dann ebenfalls linear in den gemischten Strategien (vlg. Ritzberger, 2003).

Wir schreiben s für ein n-Tupel von gemischten Strategien. Falls

s := (s 1 ; s 2 ; :::; s n )

dann ist

a i (s) := a i (s 1 ; s 2 ; :::; s n )

So ein n-Tupel s kann als Punkt in einem Vektorraum angesehen werden - dem Produktraum der Vektorräume, die die gemischten Strategien enthalten. Weiters führen wir die Substitutionsnotation

(s; t i ) := (s 1 ; :::; s i1 ; t i ; s i+1 :::; s n )

ein. Nachfolgend geben wir mehrere verschiedene Kriterien für ein Gleichgewicht (vgl. Nash, 1951).

De…nition 5 (Gleichgewicht) Ein n-Tupel s ist genau dann ein Gleichgewicht von G =< n; (( i ) i2n ; (a i ) i2n > falls für alle Spieler i gilt:

Wenn s = (s 1 ; s 2 ; :::; s n ) und s i die pure Strategie ii benutzt, also c ii > 0, sagen wir, dass s die pure Strategie ii benutzt. Wegen der Linearität von a i (s 1 ; s 2 ; :::; s n ) in s i gilt:

De…nieren wir a ii (s) := a i (s; ii ), so ergibt sich trivialerweise folgende notwendige und hinreichende Bedingung, dass s ein Equilibrium ist:

a i (s) = max (a ii (s)) (3)

P P

Wenn s = (s 1 ; s 2 ; :::; s n ) und s i = c ii ii , dann ist a i (s) = c ii a ii (s). Damit

also die Formulierung (3) hält, muss c ii = 0 sein, falls a ii (s) < max (a ii (s)).

Dies ist gleichbedeutend zu sagen, dass s die pure Strategie ii nicht benutzt, es sei denn, es handelt sich um eine optimale pure Strategie für Spieler i.Wir schreiben also