Źródła algorytmicznej ewolucyjnej teorii gier

Używam tytułowego terminu w bardzo luźnym znaczeniu.

Dużo pracy poświęcono ewolucyjnej teorii gier, w tym jej matematycznym fundamentom. Polecono mi „Gry ewolucyjne i dynamika populacji”, ale jeszcze się w to nie zagłębiłem.

Istnieje również znaczna ilość pracy nad algorytmiczną teorią gier, która jest popularnym tematem na tej stronie.

Chciałbym zobaczyć pracę, która czyni złożoność obliczeniową lub stwierdzenia zbieżności dotyczące pewnej dynamiki ewolucyjnej.

Przykłady (sformułowane bardzo luźno):

1. Biorąc pod uwagę populację i schemat ewolucyjny, czy możemy wyrazić żal probabilistyczny związany z długoterminową optymalizacją populacji (w porównaniu z najlepszym wyprodukowanym osobnikiem?). Wydaje się, że odnosi się to silnie do zespołów ekspertów i problemów bandytów. A co z ustawieniami niestacjonarnymi?
2. Biorąc pod uwagę zestaw populacji różnych gatunków, które wchodzą w interakcje w ich środowisku, grając praktycznie w dowolną grę wieloosobową, jakie stwierdzenia możemy powiedzieć o ostatecznej stabilności ich strategii lub dystrybucji strategii, biorąc pod uwagę ich strategie ewolucyjne.
3. W każdym środowisku z wieloma „niszami” (rozumiem, że to zbyt ogólnokrajowy sposób wyrażania tego), zarówno pod względem bezpośredniego związku ze środowiskiem, jak i pod względem relacji z innymi gatunkami, jakie możemy powiedzieć o tym, jak populacje będą się rozprowadzać przez te nisze.
4. Jakikolwiek problem, którego nie zadałem, ale powinienem - przychodzę do tego z niewielkim AGT, TCS, algorytmami genetycznymi, ewolucyjną teorią gier lub biologią populacji; Zadaję moje pytania z punktu widzenia optymalizacji / uczenia maszynowego / statystyk, które mogą być niewłaściwe lub niepełne.

To jeden z tematów, w których szukałem połączeń przez jakiś czas. Nie wydają się jednak powszechne. Ludzie zajmujący się biologią teoretyczną i ekonomią, którzy używają EGT, zwykle trzymają się teorii systemów dynamicznych i nie noszą soczewki algorytmicznej. Dlatego większość wyników dotyczy stylu AMath / Physics, a nie algorytmów i dyskretnego stylu matematycznego. Jeśli chcesz zastosować podejście dynamiczne, skorzystaj z ankiety Hofbauera i Zygmunta, która jest krótsza i nowsza niż ich książka (wspominam o tym i kilka komentarzy w poprzedniej odpowiedzi ).

Jednym z miejsc, w których dynamika replikatora została wykorzystana w wynikach związanych ze złożonością, jest Marcello Pelillo i współautorzy jako heurysta w rozwiązywaniu problemu max-clique (redukowanie max-clique do programowania kwadratowego, rozwiązywanie programowania kwadratowego za pomocą dynamiki replikatora jako heurystyki) :

[1] Immanuel M. Bomze i Marcello Pelillo [2000]. „Zbliżanie maksymalnej masy klikowej za pomocą dynamiki replikatora”. Transakcje IEEE w sieciach neuronowych 11 (6)

[2] Marcello Pelillo i Andrea Torsello [2006]. „Dynamika gry Pay-Monotonic i problem maksymalnej klikalności”. Neural Computation 18: 1215-1258.

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

[3] Kousha Etessami i Andreas Lochbihler [2008] „Złożoność obliczeniowa strategii stabilnych ewolucyjnie”. International Journal of Game Theory , 37 (1): 93–113. (Po raz pierwszy dostępny w 2004 r. Jako raport techniczny ECCC TR04-055).

[4] Vincent Conitzer [2013] „Dokładna złożoność obliczeniowa strategii stabilnych ewolucyjnie”. 9. konferencja nt. Ekonomii sieci i Internetu (WINE) . ( pdf ).

Wiele interesujących dzisiaj pytań EGT dotyczy gier na wykresach i chociaż istnieją pewne fajne dynamiczne wyniki systemu, takie jak (zobacz także to pytanie dotyczące rozszerzeń tego podejścia):

[5] Hisashi Ohtsuki i Martin Nowak [2006] „Równanie replikatora na wykresach”. _ Journal of Theoretical Biology_, 243 (1), 86-97 ( link , post na blogu )

Większość pracy odbywa się w oparciu o modelowanie agentowe (zobacz tę odpowiedź w kontekście modelowania rozprzestrzeniania się choroby). Modele te są zwykle znacznie bardziej przyjazne dla stwierdzeń dotyczących złożoności i konwergencji. Więcej informacji znajdziesz w następującej książce:

[6] Yoav Shoham i Kevin Leyton-Brown [2009], „Systemy wieloagentowe: podstawy algorytmiczne, teoretyczne i logiczne”, prasa z Cambridge University.

Myślę, że uczenie maszynowe jest dość prostym sposobem podejścia do EGT, ponieważ jest to naturalny punkt pośredni między odpowiednią fizyką (mechaniką statystyczną) a informatyką. To zdecydowanie zostało zrobione, zajęłoby mi trochę znalezienie dobrego odniesienia, ale losowego (co pokazuje również, że ludzie z EGT rozważali inne popularne pojęcia równowagi, takie jak równowaga skorelowana):

[7] Sergiu Hart i Andreu Mas-Colell [2000], „Prosta procedura adaptacyjna prowadząca do skorelowanej równowagi”, Econometrica 68 (5): 1127-1150

[8] Antonella Ianni [2001], „Uczenie się skorelowanych równowag w grach populacji”, Mathematical Social Sciences 42 (3): 271–294.

[9] Ludek Cigler i Boi Faltings [2011], „Osiąganie skorelowanych równowag poprzez uczenie się wielu agentów”, AAMAS 2011: 509-516

Z pewnością mam nadzieję, że inni udzielą bardziej szczegółowych odpowiedzi, ponieważ to pytanie zawsze chciałem wiedzieć więcej.

Jak powiedzieli inni, jest mniej, niż można się spodziewać. Kilka artykułów stycznie powiązanych:

„Multiplicative Weights in Coordination Games and theory of Evolution” Chastaina, Livnata, Papadimitriou i Vazirani. Ten artykuł dowodzi, że dynamika ewolucyjna (w prostym modelu) jest równoważna grze koordynacyjnej między genami odtwarzanymi za pomocą algorytmu uczenia wag multiplikatywnych. Analizują wariant 2 genów w uproszczonym modelu.

Zauważ, że algorytm wag multiplikatywnych jest naturalną dynamiką znaną z konwergencji do równowagi Nasha w grach o sumie zerowej, grach o potencjale nieatomowym i niektórych innych (patrz np. Freund i Schapire )

„Cena anarchii stochastycznej” Chunga, Ligetta, Pruhsa i mnie (od niedawna). Tutaj badamy stochastycznie stabilne stany gry, które są związane z ESS. Nie martwimy się o złożoność ich znalezienia, ale pokazujemy, że w niektórych grach cena anarchii jest niższa w porównaniu z zestawem stochastycznie stabilnych równowag w porównaniu z dowolnymi równowagami Nasha.

$n^2$