Algorithmische Spieltheorie - nicht standardisierte Gleichgewichtskonzepte?

Ich beginne mein Studium der algorithmischen Spieltheorie und es scheint, dass das normalerweise verwendete Gleichgewichtskonzept das eines Fixpunkts in einem Graphen ist. Haben sich die Menschen jedoch mit alternativen Gleichgewichtskonzepten wie Grenzzyklen befasst? Ich kann mir vorstellen, dass ein "enger" Grenzzyklus - dh ein Zyklus in der Grafik von sehr kleiner Länge - als etwas angesehen werden könnte, das der Standarddefinition des Gleichgewichts "nahe" kommt.

Ich habe versucht, in Google Scholar zu stöbern, aber ohne Erfolg.

Eine, die ich mag, wird manchmal als "grobkorreliertes Gleichgewicht" bezeichnet. Dies ist tatsächlich der begrenzende Satz effizienter "No-Regret" -Dynamik.

Diese haben einige schöne Eigenschaften, nicht zuletzt, dass sie durch effiziente, entkoppelte Dynamik erreicht werden können, und schließen Nash-Gleichgewichte als Sonderfall ein (sind also als Vorhersage des Verhaltens "streng plausibler"). Was sie möglicherweise etwas ähnlicher macht als das, worüber Sie fragen, ist, dass diese Lerndynamik niemals zu einem festen Punkt konvergieren muss - tatsächlich können sie für immer zyklisch sein. Trotzdem ist es oft möglich, die schnelle Konvergenz der sozialen Wohlfahrt unter dieser Dynamik zu begrenzen (dh den Preis der Anarchie über grob korrelierte Gleichgewichte), und außerdem ist die soziale Wohlfahrt über grob korrelierte Gleichgewichte oft nicht schlechter als über Nash-Gleichgewichten.

Einige relevante Artikel:

http://portal.acm.org/citation.cfm?id=1374430

http://portal.acm.org/citation.cfm?id=1536414.1536485

http://portal.acm.org/citation.cfm?id=1536487

Möglicherweise suchen Sie nach etwas wie Sink Equilibria (z. B. http://arxiv.org/abs/0902.0382 ) - aber die Zykluslänge wird nicht berücksichtigt.

Dies ist wahrscheinlich nicht das, wonach Sie suchen, aber es ist möglich, ein ungefähres Nash-Gleichgewicht zu definieren, bei dem das Ziel darin besteht, Zustände zu finden, so dass die Dienstprogramme der Spieler nahe an denen liegen, die durch das Nash-Gleichgewicht definiert sind. Noam Nisan hat einen schönen Beitrag dazu (und da er manchmal hier rumhängt, wird er wahrscheinlich eine bessere Antwort für Sie haben).

Joseph Y. Halpern aus Cornell hielt kürzlich im CUNY Graduate Center einen Vortrag mit dem Titel: Beyond Nash Equilibrium: Lösungskonzepte für das 21. Jahrhundert. Vielleicht würde ihn seine Arbeit interessieren.

http://web.cs.gc.cuny.edu/~kgb/seminar.html

Hoffentlich ist dies nicht zu unangebracht für eine Antwort, da diese Frage unter dem Gesichtspunkt der evolutionären Spieltheorie (EGT) anstelle von AGT betrachtet wird.

Die Spieltheorie, wie sie ursprünglich von Neumann und Morgenstern formuliert wurde, war eine statische Theorie. Daher sind viele der populären Gleichgewichtskonzepte (Nash, Correlated usw.) von Natur aus statisch. Um über nicht statische Gleichgewichte zu sprechen, müssen wir eine Art Dynamik einführen. AGT tut dies häufig unter Berücksichtigung spezifischer Überlegungen (Algorithmen), die Agenten verwenden könnten, um zu ihren Entscheidungen zu gelangen.

Ein alternativer Ansatz, der von EGT angenommen wird, besteht darin, die Populationsdynamik einer großen Anzahl von Agenten mit sehr einfachen Entscheidungen zu berücksichtigen. Dies erzeugt normalerweise eine nichtlineare Dynamik in der Population und platziert EGT als Teil dynamischer Systeme. Daher sehen Sie alle verrückten Gleichgewichtskonzepte dynamischer Systeme wie Grenzzyklen oder chaotische Attraktoren als Gleichgewichtskonzepte. Diese instationären Gleichgewichte sind in der EGT gut untersucht, obwohl die Analyse häufig nur aus dynamischen Systemen und nicht algorithmisch erfolgt.

Wenn Sie sich für EGT interessieren, ist Hofbauers und Sigmunds Umfrage " Evolutionäre Spieldynamik " aus dem Jahr 2003 ein Standard (und zugänglicher) Ausgangspunkt.