Początki teorii gier ewolucyjnych (TGE) sięgają lat 60ych XX wieku. Pierwotnie TGE rozwijała się w oparciu o idee i przykłady wzięte z biologii. Zasadniczym jej elementem bylo spostrzeżenie że biologiczne przystosowanie (fitness) gatunków zależy od interakcji które można opisać językiem teorii gier. Gracze (osobniki, geny) nie zmieniali swych strategii (np. cech w jakie geny wyposażają organizm, przykładowo gresywna, pokojowa), nie musieli wiedziec że graja w grę, a zmiana udziału strategii w populacji brała się z różnego tempa reprodukcji graczy używajacych poszczególonych strategii. W tym kontekście TGE jest związana z darwinowska teoria ewolucji, której jednym z podstawowych postulatów jest założenie że udział procentowy osobników o lepszym przystosowaniu rośnie w populacji.

J. Maynard Smith jako pierwszy w latach 60ych zaproponował wyjaśnianie zachowań zwierząt za pomocą teorii gier. O ile w interakcjach międzyludzkich gracze, agenci, to ludzie, zespoły, instytucje, mający świadomośc uczestniczenia w grze, o tyle w przypadku świata zwierzęcego, ogólniej w biologii, opisywane obiekty nie mają świadomości uczestnictwa w interakcjach które nazywamy teoriogrowymi, nie mają świadomości podejmowania decyzji, i idea opisu takich interakcji za pomocą formalizmu teorii gier miała w owym czasie charakter rewolucyjny. Jedną z inspiracji leżących u źródeł TGE były obserwacje konfliktów w świecie zwierzęcym, np. walk rytualnych, walk o terytorium, o samicę, czy o przewodnictwo w stadzie.

W naukach biologicznych powstały odrębne działy wykozystujące formalizm teorii gier, takie jak biologia ewolucyjna, ekologia ewolucyjna, patrz np. [3]. Rozwijają sie zastosowania TGE w ekonomii, patrz np. [15, 33, 26], w psychologii i w naukach społecznych. W ekonomii gracze to podmioty gospodarcze, wypłaty to zyski, a strategie to np. sposoby działania na rynku. W naukach społecznych stosuje się TGE w szczegolności do opisu, powstawania i utrzymywania się postaw kooperacyjnych i altruistycznych w społeczeństwach (ludzi, zwierzat), do opisu powstawania i ewolucji norm społecznych.

O ile w biologii czestości strategii zależą od temp reprodukcji, a mutacje mają podłoże genetyczne, to w naukach społecznych i w ekonomii zależą od możliwości imitacji jednych graczy przez drugich, oraz od możliwości indywidualnego i grupowego uczenia się (learning), a mutacje to np. eksperymenty, innowacje, przypadkowe błędy czy zachowania idiosynkratyczne. W ekonomii, naukach behawioralnych, stosujemy równania dynamiki imitacji, dynamiki najlepszej odpowiedzi, dynamiki wielokrotnego testowania i inne. Będzie to tematem wykładu XV.

Podstawowym pojęciem klasycznej TG jest równowaga Nasha. TG w zasadzie nie precyzuje czy, i która (gdy jest więcej niż jedna) RN jest grana, osiągana, i jeżeli gracze grają RN, to jak do niej doszli. Teoria Gier Ewolucyjnych (TGE) próbuje odpowiedzieć na te pytania. Podejście ewolucyjne polega na opisie jak zachodzą zmiany składu takich układów, jakie są stany asymptotyczne procesów ewolucyjnych, jaka jest ich stabilność itp.

Podstawowy scenariusz ewolucyjny:

Podstawowy scenariusz ewolucyjny jest to eksperyment myślowy, wywód teoretyczny:

1. rozpatrujemy dużą populacja jednakowych graczy

2. każdy posiada jedną, niezmienną strategię

3. zakładamy łączenie losowe w pary, w parach jest jednorazowo rozgrywana 2-osobowa gra symetryczna

4. każdy gracz rodzi potomstwo (reprodukcja aseksualna), wypłata z gry jest to liczebność potomstwa.

5. potomstwo dziedziczy strategię rodzica.

6. wracamy do p. 1.

Gra ewolucyjna jest to gra strategiczna rozgrywana w populacji osobników zgodnie z scenariuszem ewolucyjnym.

Podstawową rolę w prezentacji podstaw ewolucyjnej teorii gier będzie miala gra Jastrząb–Gołąb.

Rozważamy scenariusz ewolucyjny z grą Jastrząb–Gołąb. Mamy dużą populację składającą się z osobników A=J, i B=G, o częstościach odpowiednio p i 1-p, których losowo łączymy w pary w każdej jednostce czasu. Każda para rozgrywa jedną grę Jastrząb-Gołąb. Chcemy opisać jak będzie ewoluował skłąd procentowy Jastrzębi i Gołębi w populacji. Niech p=p⁢t oznacza częstość Jastrzębi w chwili t.

Średnie wypłata osobników grających J i G w chwili t wynoszą odpowiednio

Założenie ze scenariusza ewolucyjnego, że wynikiem gry sa wypłaty w grze są mierzone liczebnością potomstwa, (dziedziczącego strategię rodzica) odpowiada paradygmatowi teorii Darwina: przystosowanie (fitness) jest mierzone liczebnością potomstwa. Teoriogrowym odpowiednikiem przystosowania jest wypłata. Założenie to formalnie formułujemy jako postulat:

Tempa urodzin a,b są liniowymi funkcjami średnich wypłat osobników J, G:

gdzie W0 jest stałym, niezależnym od interakcji tempem urodzin (baseline fitness), który dodajemy by uniknąć ujemnych temp urodzin. Zauważmy że w przeciwieństwie np. do rozpadu promieniotwórczego, tempa urodzin są (przez zależność od składu populacji) zależne od czasu. Otrzymujemy

W szczególności, jeżeli p – częstość J w danej chwili jest niższa od p* (i różna od zera), to częstość J rośnie w procesie ewolucyjnym. Analogicznie, jeżeli p>p*,⁢⁢p≠1, to częstość J maleje. dla p=p* nie zmienia się. Oznacza to że skład procentowy populacji dąży do p*=vc niezależnie od składu początkowego [o ile p⁢0∈0,1, wpp. populacja składa się cały czas tylko z graczy G lub tylko z graczy J]. Wartość p* można więc nazwać stanem równowagi. Populacja J-G o równowagowym składzie p*=v/c nie zmienia składu w scenariuszu ewolucyjnym. Odchyłka procentowego udziału każdego typu od składu równowagowego uruchamia ewolucję do składu równowagowego.

Powyższy model ewolucyjny przestawimy w języku rownań różniczkowych. Niech N⁢t - liczebność układu w t, p=p⁢t–częstość strategii J, a=a⁢t,b=b⁢t - tempa urodzin odpowiednio graczy J, G. W czasie Δ⁢t≪1 urodzi się w przybliżeniu a⁢Δ⁢t⁢p⁢t⁢N⁢t Jastrzębi, b⁢Δ⁢t⁢1-p⁢t⁢N⁢t Gołębi. Tempo zmiany p:

gdzie p*:=v/c. Dla Δ⁢t→0 otrzymujemy równanie różniczkowe ewolucji częstości Jastrzębi

Punkty p=p*, p=0 i p=1 są punktami stałymi (punktami równowagowymi) powyższej dynamiki w omawianym scenariuszu ewolucyjnym. Pierwszy z nich jest atraktorem, dwa pozostałe to repellery.

Model dynamiki replikatorowej jest podstawowym i najbardziej znanym różniczkowym modelem TGE.

Rozważamy scenariusz ewolucyjny: GS: <{1,2},Ai,ui>,i=1,…n, n - liczba strategii czystych,

Ni⁢t - liczba (masa) graczy grających strategią i (masa podpopulacji i),

N⁢t=∑i=1nNi⁢t - liczebność populacji (masa całej populacji),

xi=xi⁢t=Ni/N–częstość graczy grających i, częstość strategii i,

x=x1,x2,…⁢xn=∑k=1nek⁢xk∈Δ, - stan populacji w chwili t, ek - k-ty wersor w ℜn,⁢Δ - sympleks jednostkowy. Gracze są nierozróżnialni, więc wersor ma tylko jeden indeks (ogólnie mieliśmy eik - k-ty wersor gracza i-tego).

u⁢ei,x–wypłata strategii i gdy populacja jest w w stanie x. Jest to z definicji wartość oczekiwana zmiennej losowej–wypłaty gracza grającego strategią i z losowym partnerem z populacji w stanie x (i.e. x jest rozkładem tej zmiennej losowej); xk jest prawdopodobieństwem wylosowania gracza grającego strategią k,⁢k=1,…⁢n). Równoważnie można powiedzieć że jest to wypłata gracza grającego i z losowo wybranym partnerem grającym strategią mieszaną x.

u⁢x,x=∑i=1nxi⁢u⁢ei,x - średnia wypłata w populacji (średnia wypłata losowego gracza).

W rozważanym scenariuszu ewolucyjnym postulat ten formalizujemy w następujący sposób:

Tempo wzrostu liczby osobników grających strategię i w populacji w stanie x jest proporcjonalne (u nas–dla uproszczenia–równe) do wypłaty strategii i gdy populacja jest w stanie x.

Obliczamy

Dzieląc przez N otrzymujemy

Przypomnijmy że w podstawowym scenariuszu ewolucyjnym gracze grają w symetryczną grę dwuosobową o macierzy wypłat A. Mamy więc

RDR przyjmuja postać

gdzie A jest macierzą wypłat rozważanej symetrycznej GS.

RDR mają ciekawe własności matematyczne. Udowodnimy interesujące twierdzenie łaczące ”statyczne” pojęcie równowagi Nasha z ”dynamicznym” pojęciem punktu krytycznego (punktu stałego) RDR.

Oto kilka innych interesujących zależności między powyższymi pojęciami. Scisłe sformułowania i dowody tych i innych ciekawych faktów wiążących strategie Nasha i punkty krytyczne RDR można znależć np. w monografiach [11, 39].

John Maynard Smith w latach 1970-ych wprowadził pojęcie strategii ewolucyjnie stabilnej (ESS), uzupełniając warunek rownowagi Nasha o dodatkowy warunek stabilności. ESS odgrywa w TGE porównywalną rolę do Równowagi Nasha w klasycznej TG. Nieformalnie ESS jest to taki profil populacji, który jest odporny na inwazję (dostatecznie) małej grupy mutantów o odmiennym fenotypie. Fenotyp to np. cecha budowy ciała (wielkość osobnika, kolor skóry), agresja, altruizm, sygnał wysyłany innym zwierzęciom itp. Fenotypy są dziedziczone.

ϵ0 nazywamy barierą inwazyjną.

(i) to warunek RN, (ii)–warunek ”stabilności”. Gdyby (ii) nie było spełnione, strategia σ mogłaby ”opanować” populację σ⌃ w wyniku neutralnego dryfu.

Tak więc strategia σ⌃ jest ewolucyjnie stabilna jeżeli 1. σ⌃ jest najlepszą odpowiedzią na siebie [a zatem profil σ⌃,σ⌃ jest RN]. 2. jeżeli inna strategia σ jest najlepszą odpowiedzią na σ⌃ to u⁢σ⌃,σ>u⁢σ,σ, czyli granie σ⌃ przeciwko σ daje wyższą wypłatę niż σ przeciwko σ. Jeżeli śladowe ilości mutantów grają σ w populacji grającej σ⌃, to ich udział w populacji maleje do zera.

Natychmiastową konsekwencją tego twierdzenia jest

Dla gry HD (7.4) i strategii σ⌃=v/c,1-v/c obliczamy σ⌃⁢A⁢σ-σ⁢A⁢σ=12⁢c⁢v-c⁢x2>0 dla x≠vc.

Jedną z wad pojęcia ESS jest fakt że nie dla wszystkich klas gier ważnych w teorii i w zastosowaniach ESS istnieje.