Quellen für algorithmische evolutionäre Spieltheorie

Ich benutze den Titelbegriff sehr locker.

Die evolutionäre Spieltheorie, einschließlich ihrer mathematischen Grundlagen, ist in erheblichem Umfang erforscht. Mir wurde "Evolutionary Games and Population Dynamics" empfohlen, aber ich habe mich noch nicht damit befasst.

Es gibt auch viel Arbeit zur algorithmischen Spieltheorie, was ein beliebtes Thema auf dieser Seite ist.

Was ich sehen möchte, ist eine Arbeit, die rechnerische Komplexität oder Konvergenzaussagen über bestimmte evolutionäre Dynamiken macht.

Beispiele (sehr lose formuliert):

1. Können wir angesichts einer Population und eines Evolutionsschemas ein wahrscheinlichkeitstheoretisches Bedauern für die langfristige Optimalität der Population angeben (im Vergleich zum besten produzierten Individuum?). Dies scheint stark mit Ensembles von Experten und Banditenproblemen zu tun zu haben. Was ist mit nicht stationären Einstellungen?
2. Welche Aussagen können wir angesichts einer Reihe von Populationen verschiedener Arten, die in ihrer Umgebung interagieren und so ziemlich jedes Multiplayer-Spiel spielen, über die eventuelle Stabilität ihrer Strategien oder Strategiedistributionen angesichts ihrer Evolutionsstrategien treffen?
3. In jeder Umgebung mit vielen "Nischen" (wie ich verstehe eine weit verbreitete Form der Formulierung), entweder in Bezug auf die direkte Beziehung zur Umwelt oder in Bezug auf die Beziehungen zu anderen Arten, welche Aussagen können wir über die Verteilung der Populationen treffen über diese Nischen.
4. Jedes Problem, das ich nicht gefragt habe, aber sollte - ich komme mit wenig AGT, TCS, genetischen Algorithmen, evolutionärer Spieltheorie oder populationsbiologischem Hintergrund darauf zu; Ich stelle meine Fragen aus Sicht der Optimierung / des maschinellen Lernens / der Statistik, die falsch oder unvollständig sein können.

Dies ist eines der Themen, bei denen ich schon länger nach Verbindungen gesucht habe. Sie scheinen jedoch nicht allgegenwärtig zu sein. Die Leute, die sich mit theoretischer Biologie und Ökonomie beschäftigen und EGT verwenden, halten normalerweise an der Theorie dynamischer Systeme fest und verwenden nicht die algorithmische Linse. Daher sind die meisten Ergebnisse vom AMath / Physik-Stil und nicht von den Algorithmen und dem diskreten Mathematik-Stil. Wenn Sie bereit sind, den Ansatz dynamischer Systeme zu verfolgen, dann gibt es eine Umfrage von Hofbauer und Sigmund, die kürzer und aktueller ist als ihr Buch (ich erwähne es und einige vorübergehende Kommentare in einer früheren Antwort ).

Eine der Stellen, an denen die Replikatordynamik für komplexitätsbezogene Ergebnisse verwendet wurde, ist von Marcello Pelillo und Co-Autoren als Heuristik zum Lösen von Max-Clique (reduzieren Sie Max-Clique auf quadratische Programmierung, lösen Sie quadratische Programmierung, indem Sie die Replikatordynamik als Ihre Heuristik verwenden). :

[1] Immanuel M. Bomze und Marcello Pelillo [2000]. Msgstr "Annäherung der Maximalgewichtsgruppe unter Verwendung der Replikatordynamik." IEEE-Transaktionen in neuronalen Netzen 11 (6)

[2] Marcello Pelillo und Andrea Torsello [2006]. "Payoff-Monotonic Game Dynamics und das Maximum Clique Problem." Neural Computation 18: 1215-1258.

$\Sigma^P_2$$\Sigma^P_2$

[3] Kousha Etessami und Andreas Lochbihler [2008] "Die rechnerische Komplexität evolutionär stabiler Strategien". Internationales Journal für Spieltheorie , 37 (1): 93-113. (Erstmals verfügbar im Jahr 2004 als ECCC Tech Report TR04-055).

[4] Vincent Conitzer [2013] "Die exakte rechnerische Komplexität evolutionär stabiler Strategien". Die 9. Konferenz für Web- und Internetökonomie (WINE) . ( pdf ).

Viele der interessanten EGT-Fragen beziehen sich heute auf Spiele auf Grafiken, und obwohl es einige coole dynamische Systemergebnisse gibt, wie (siehe auch diese Frage für Erweiterungen dieses Ansatzes):

[5] Hisashi Ohtsuki und Martin Nowak [2006] "Die Replikatorgleichung auf Graphen." _ Journal of Theoretical Biology_, 243 (1), 86-97 ( link , blog post )

Die meiste Arbeit beschäftigt sich mit agentenbasierter Modellierung (siehe diese Antwort für einen Kontext zur Modellierung der Ausbreitung von Krankheiten). Diese Modelle sind für Komplexitäts- und Konvergenzaussagen in der Regel viel positiver. Weitere Informationen finden Sie in folgendem Buch:

[6] Yoav Shoham und Kevin Leyton-Brown [2009], "Multiagent-Systeme: Algorithmische, spieltheoretische und logische Grundlagen", Cambridge University Press.

Ich denke, maschinelles Lernen ist ein ziemlich einfacher Weg, sich der EGT zu nähern, da es eine natürliche Mitte zwischen der relevanten Physik (statistische Mechanik) und der Informatik ist. Dies wurde definitiv getan, es würde ein bisschen dauern, bis ich eine gute Referenz gefunden hätte, aber eine zufällige Referenz (was auch zeigt, dass EGT-Leute andere populäre Gleichgewichtskonzepte in Betracht gezogen haben, wie das korrelierte Gleichgewicht):

[7] Sergiu Hart und Andreu Mas-Colell [2000], "Ein einfaches adaptives Verfahren, das zu einem korrelierten Gleichgewicht führt", Econometrica 68 (5): 1127-1150

[8] Antonella Ianni [2001], "Lernen korrelierter Gleichgewichte in Bevölkerungsspielen", Mathematical Social Sciences 42 (3): 271-294.

[9] Ludek Cigler und Boi Faltings [2011], "Erreichen korrelierter Gleichgewichte durch Multi-Agent-Lernen", AAMAS 2011: 509-516

Ich hoffe auf jeden Fall, dass andere spezifischere Antworten geben, da dies eine Frage ist, über die ich schon immer mehr wissen wollte.

Wie andere gesagt haben, gibt es weniger als Sie erwarten würden. Ein paar tangential verwandte Artikel:

"Multiplikative Gewichte in Koordinationsspielen und Evolutionstheorie" von Chastain, Livnat, Papadimitriou und Vazirani. Diese Arbeit argumentiert, dass evolutionäre Dynamik (in einem einfachen Modell) einem Koordinationsspiel zwischen Genen entspricht, das mit dem Lernalgorithmus für multiplikative Gewichte gespielt wird. Sie analysieren die 2-Gen-Variante in einem vereinfachten Modell.

Beachten Sie, dass der Algorithmus für multiplikative Gewichte eine natürliche Dynamik ist, von der bekannt ist, dass sie in Nullsummenspielen, nichtatomaren Potentialspielen und einigen anderen zum Nash-Gleichgewicht konvergiert (siehe z. B. Freund und Schapire ).

"Der Preis der stochastischen Anarchie" von Chung, Ligett, Pruhs und mir (seit einiger Zeit). Hier untersuchen wir stochastisch stabile Zustände eines Spiels, die mit ESS zusammenhängen. Wir machen uns keine Sorgen über die Komplexität, sie zu finden, aber wir zeigen, dass in einigen Spielen der Preis für Anarchie im Vergleich zu beliebigen Nash-Gleichgewichten niedriger ist als für stochastisch stabile Gleichgewichte.

Ich habe von der Schule in Ashlock gelernt . Das große Mitnehmen, das ich bekam, war, wie nützlich es war, die zu nehmen$n^2$ -Ergebnistabelle zwischen Agenten zu verwenden und die Zeilen mithilfe von K-Means in Strategiegruppen für die Analyse zu gruppieren.