Nash-Gleichgewichte, Fixpunkte und wie man mit Comportamiento Gregario Elite-Universitäten schafft.


Heute noch ein Beispiel zur Anwendung von Fixpunkten in der Spieltheorie. (Womit das Thema “Fixpunktsätze” erst mal abgeschlossen wird, nächste Woche geht es wieder weiter mit Flächen.)

Ein Nash-Gleichgewicht in einem “Spiel” ist ein strategisches Gleichgewicht, von dem ausgehend kein einzelner Spieler für sich einen Vorteil erzielen kann, indem er einseitig von seiner Strategie abweicht.

Ein Beispiel:
Seit kurzem gibt es ja Zulassungsverfahren an Universitäten. Auch unter spieltheoretischen Aspekten ein interessantes Thema.
(Das folgende Beispiel ist, mit ein paar geringfügigen Änderungen, dem Buch von Roger McCain entnommen.)

In Deutschland gibt es dieses Jahr, grob geschätzt, 300000 Studienanfänger. Es gibt 139 Universitäten. “The universities are not players in the game — just mindless, predictable automata.” Die Studenten werden nach einem Punktesystem bewertet, wobei der beste 300000 Punkte bekommt, der zweitbeste 299999 Punkte und so weiter. Wir nehmen der Einfachheit halber an, daß jede Universität 2000 Studenten aufnimmt, und zwar die 2000 besten, die sich dort beworben haben. Jeder Student möchte erreichen, daß er an einer Universität mit möglichst hoher durchschnittlicher Punktzahl (der Mitstudenten) studiert.

Wenn sich z.B. die 2000 besten Studenten alle an der Universität Oldenburg einschreiben würden (also die mit 300000, 299999, …, 298001 Punkten), dann wäre diese durchschnittliche Punktzahl für Oldenburger Studenten 299000,5.

Jeder Student bewirbt sich also an einer Universität. Er weiß, an welcher Stelle im Punktsystem er steht und damit, welche Universität ihn nehmen würde.

Dieses Spiel hat (139)! verschiedene Nash-Gleichgewichte. Diese entsprechen den verschiedenen Reihenfolgen unter den Universitäten.
Zum Beispiel:

1. Die 2000 besten Studenten bewerben sich in Oldenburg,
2. Die nächsten 2000 Studenten bewerben sich in Hohenheim,
3. Die darauffolgenden 2000 Studenten bewerben sich in Hildesheim

und so weiter, jede Gruppe von 2000 Studenten in der Rangfolge bewirbt sich jeweils an derselben Universität. Jede Universität nimmt alle Bewerber auf und es ist klar, daß dann kein Student durch eine andere Bewerbung seine Lage verbessern kann:
– bewirbt er sich auf einer besseren Universität, wird er abgelehnt,
– bewirbt er sich auf einer schlechteren Universität, landet er auf einer Uni mit schlechterem Durchschnittswert.
Wir befinden uns also in einem Nash-Gleichgewicht.

Zu jeder der (139)! möglichen Rangfolgen der Universitäten gibt es ein solches Nash-Gleichgewicht.

“In other words, this game is a coordination game. So long as each group of students in the same thousand all apply to the same university, we have an equilibrium — and it doesn’t matter which university that is. If the best 1000 students happened to apply to Podunk State, Podunk State would be the best university in the country, and Harvard and MIT would be so much chopped liver. (Notice that it also doesn’t depend on the quality of the faculty, the facilities, or the food in the lunchroom. All that matters is agreement among the students).”

Natürlich funktioniert das in Wirklichkeit anders, schon weil in der öffentlichen Wahrnehmung der Ruf einer Universität eher von den Wissenschaftlern als von den Studenten abhängt.
Eine Frage, die sich aber natürlich aufdrängt, ist, ob vielleicht die Börse nach ähnlichen Prinzipien funktioniert 🙂

Wie auch immer, am Beispiel sieht man jedenfalls, was ein Nash-Gleichgewicht ist: jeder, der als Einzelner sein Verhalten ändert, verschlechtert seine Situation.

John Nash bewies in seiner Dissertation, für die er mehr als 40 Jahre später den Wirtschafts-Nobelpreis erhielt, das es in bestimmten nicht-kooperativen Zwei-Personen-Spiele immer Nash-Gleichgewichte gibt.

Nash’s Beweis benutzt den Fixpunktsatz von Kakutani. In seiner allgemeinen Formulierung (wie man sie für Nash’s Arbeit benötigt) besagt dieser, daß jede (abgeschlossene, knvexe) Korrespondenz auf einer konvexen, kompakten Menge A im Rn einen Fixpunkt hat. (Eine Korrespondenz ist eine Abbildung von A in die Potenzmenge von A. Genaueres hier.)

Wir hatten in den letzten Wochen schon einige Anwendungen von Fixpunktsätzen besprochen. Wenn im Fixpunktsatz von Kakutani die Korrespondenz eine Funktion im üblichen Sinne ist, dann bekommt man gerade den Fixpunktsatz von Brouwer (siehe TvF 33), aus dem sich z.B. (TvF 34) auch die Existenz von Preisgleichgewichten ergab und der auch außerhalb der Wirtschaftswissenschaft in Strategiespielen eine Rolle spielt.

Heute beschäftigen sich die Wirtschaftswissenschaften mit verschiedenen ‘Verfeinerungen’ von Nash-Gleichgewichten, z.B. den vom Bonner Nobelpreisträger R.Selten untersuchten Trembling hand perfect equilibria (Zuckende-Hand-Gleichgewichten).

Teil 1, Teil 2, Teil 3, Teil 4, Teil 5, Teil 6, Teil 7 , Teil 8, Teil 9 , Teil 10 ,Teil 11, Teil 12, Teil 13, Teil 14, Teil 15, Teil 16, Teil 17, Teil 18, Teil 19, Teil 20, Teil 21, Teil 22, Teil 23, Teil 24, Teil 25, Teil 26, Teil 27, Teil 28, Teil 29, Teil 30, Teil 31, Teil 32, Teil 33, Teil 34, Teil 35, Teil 36, Teil 37, Teil 38, Teil 39, Teil 40, Teil 41

Kommentare (6)

  1. #1 Joerg
    29. November 2008

    Diese Reihe bekommt eigentlich viel zu wenig Kommentare, aber was soll man schreiben außer das es shclicht gut ist. Ich war nicht von Anfang an dabei, aber trotzdem lerne ich in jedem Beitrag etwas, das mein fernes fernes Topologie-Wissen aus Ana I erweitert.

  2. #2 da
    29. November 2008

    Sehr interessante Themen!

  3. #3 Thilo Kuessner
    30. November 2008

    Danke für die Blumen 🙂

  4. #4 Ulrich
    5. Dezember 2008

    @ Thilo:
    John Nash bewies in seiner Dissertation, für die er mehr als 40 Jahre später den Wirtschafts-Nobelpreis erhielt, das es in bestimmten kooperativen Zwei-Personen-Spiele immer Nash-Gleichgewichte gibt.

    Eigentlich: in bestimmten NICHTkooperativen N-Personen Spielen!

    Nash’s Beweis benutzt den Fixpunktsatz von Kakutani.

    In seiner Diss benutzte er den Fixpunktsatz von Brouwer. Den von Kakutani verwendete er in seinem PNAS-paper 1950.

    Heute beschäftigen sich die Wirtschaftswissenschaften mit verschiedenen ‘Verfeinerungen’ von Nash-Gleichgewichten, […]

    Nicht wirklich. Die Suche nach sinnvollen Nash-refinements ist vorbei. Man kennt die einschlägigen Kandidaten und bis auf die altbewährten (strict, perfect, subgame-perfect, evolutionarily stable) hat sich keines so richtig durchgesetzt.

  5. #5 Thilo Kuessner
    5. Dezember 2008

    Sorry, das mit kooperativ – nicht-kooperativ war ein Tippfehler, den ich eben mal korrigiert habe. Ich hoffe, durch das Beispiel war trotzdem klar, was gemeint ist.

    Der letzte Satz im Artikel ist vielleicht mißverständlich. Ich wollte nicht den Eindruck erwecken, daß Spieltheorie heute in den Wirtschaftswissenschaften ein zentrales Forschungsthema ist, sondern nur, daß es nach Nash noch weitere Entwicklungen gab. (Immerhin hat Selten für sein Gleichgewichtskonzept ja noch 1994 den Nobelpreis bekommen. Ist natürlich auch schon wieder ein paar Jahre her.) Ich hätte aber wohl erwähnen sollen, daß man im Gegensatz zu den 40er Jahren heute nicht mehr hofft, soziale Zusammenhängen wirklich 1:1 mittels Spieltheorie beschreiben zu können.

  6. #6 Ulrich
    5. Dezember 2008

    Ich wollte nicht den Eindruck erwecken, daß Spieltheorie heute in den Wirtschaftswissenschaften ein zentrales Forschungsthema ist, […]

    Meine Anmerkung bezog sich ausschließlich auf die Beschäftigung mit Verfeinerungen des NG. Die Spieltheorie insgesamt ist durchaus ein aktuelles Thema. (Vielleicht weniger die Weiterentwicklung der Theorie selbst, doch als Werkzeug ist sie voll im Einsatz.)

    Aber ich bin natürlich befangen… 😉