[ Pobierz całość w formacie PDF ]
Tom 58 2009
Numer 3–4 (284–285)
Strony 443–458
K
rzysztof
A
rgAsińsKi
Instytut Nauk o Środowisku
Uniwersytet Jagielloński
Gronostajowa 7, 30-387 Kraków
E-mail: krzysztof.argasinski@uj.edu.pl
METODY TEORII GIER EWOLUCYJNYCH
WSTĘP
W biologii ewolucyjnej oraz związanych
z nią dziedzinach często mamy do czynienia
z hipotezami, które sprawiają wrażenie para-
doksów. W takich sytuacjach metody oparte
na analizach czysto opisowych przestają być
skuteczne i należy się odwołać do bardziej
ścisłych narzędzi. Od dawna dla biologów za-
stanawiającym faktem było występowanie w
przyrodzie konfliktów zrytualizowanych, czyli
takich, w których nie odbywa się prawdziwa
walka, tylko konkurujące osobniki straszą się
nawzajem, aż któryś z nich oddali się. W roz-
grywkach tych rzadko dochodzi do poważ-
nych obrażeń wśród uczestniczących osobni-
ków. Przykładami takich zachowań są walki
godowe, obrona terytorium czy ustalanie po-
zycji w grupie. Pierwotnie uznawano je za
przykłady świadczące o działaniu dla „dobra
gatunku”. Jak wiadomo to tłumaczenie oka-
zało się fałszywe (patrz artykuł Ł
omnicKiego
„Poziomy doboru, adaptacje” w tym zeszycie
KOSMOSU). Wobec tego problem powrócił
jako otwarty. Należało znaleźć uzasadnienie
tłumaczące go na poziomie interakcji poje-
dynczych osobników. To zainspirowało Joh-
na Maynarda Smitha do wykorzystania metod
teorii gier w celu wyjaśnienia tego zjawiska.
Tak narodziła się nowa dziedzina nauki —
teoria gier ewolucyjnych. Jest to relatywnie
młody kierunek, powstały w drugiej połowie
lat 70. XX w., będący więc wciąż w fazie in-
tensywnego rozwoju.
Teoria gier ewolucyjnych, która wyrosła z
klasycznej teorii gier, ma na celu badanie me-
chanizmów doboru naturalnego oraz dynami-
ki procesów społecznych. Teoria ta znalazła
bardzo szerokie pole zastosowań, głównie
dzięki wpływowi paradygmatu ewolucyjne-
go na wiele pozornie niezwiązanych ze sobą
dziedzin wiedzy, począwszy od biologii, psy-
chologii i nauk społecznych, aż po informa-
tykę i badania nad sztuczną inteligencją. Jest
ona owocem spotkania się dwóch odrębnych
i posiadających poważny dorobek działów
matematyki. Z jednej strony jest to klasycz-
na teoria gier, mająca fundamenty osadzo-
ne w pracach Johna von Neumanna, Oskara
Morgensterna czy Johna F. Nasha, z drugiej,
matematyczne modele genetyki populacyjnej.
Teoria doboru naturalnego stworzona przez
Darwina, zmatematyzowana została przez oj-
ców neodarwinizmu Sewalla Wrighta, Johna
B. Haldane’a i Ronalda S. Fishera. Następnie
rozwijana była przez ich następców, z któ-
rych jako najważniejszych należałoby wymie-
nić George’a Price’a i Williama Hamiltona,
których teoria dostosowania włącznego (ang.
inclusive fitness) zrewolucjonizowała współ-
czesną biologię i odbiła się szerokim echem
w psychologii, antropologii i naukach spo-
łecznych. Hamilton rozważał pojęcie ewolu-
cyjnej stabilności. Wprowadzając pojęcie stra-
tegii nieeliminowalnej (ang. unbeatable stra-
tegy) wytyczył właściwy kierunek dalszych
dociekań. Wreszcie uczeń Haldane’a, były
inżynier lotniczy John Maynard Smith, wraz
z Georgem Price’m, publikuje w 1973 r. arty-
kuł pod tytułem
The logic of animal conflict
,
w którym pojawia się fundamentalne pojęcie
strategii ewolucyjnie stabilnej (ESS). Moment
444
K
rzysztof
A
rgAsińsKi
ten można uznać za narodziny teorii gier
ewolucyjnych. W 1982 r. ukazuje się książ-
ka Maynarda Smitha pod tytułem
Evolution
and the theory of games
. Stanowi ona synte-
zę prac wcześniej publikowanych w różnych
czasopismach i jest jedną z pierwszych mo-
nografii na temat teorii gier ewolucyjnych.
Potem nastąpił gwałtowny rozwój teorii dzię-
ki pracy takich naukowców jak Josef Hofbau-
er, Martin Nowak czy Ross Cressman. Nastą-
piło swoiste sprzężenie zwrotne i metody
stworzone na potrzeby biologii zaczęły być
wykorzystywane w ekonomii, czyli na polu
zajmowanym przez klasyczną teorię gier.
CZYM JEST GRA DLA MATEMATYKA?
Aby zrozumieć czym jest gra dla matema-
tyka, zajmijmy się najprostszym przypadkiem
gier dwuosobowych. Struktura matematycz-
na opisująca grę wygląda wtedy następująco:
mamy
zbiór strategii czystych
(
s
1
,
…
,
s
n
), gdzie
przez strategie czyste rozumiemy elemen-
tarne akcje podejmowane przez graczy
(np. kooperacja, zdrada, atak, ucieczka). W
przypadku, kiedy obydwaj gracze dokonają
wyboru swoich strategii, możemy określić
wypłatę
w grze. Tak więc
funkcją wypłat
nazywamy funkcję
W
(
s
x
,
s
y
)
,
której argumen-
tami są strategie obydwu graczy, natomiast
wartością jest wypłata jaką otrzymuje gracz
x
stosujący strategię
s
x
w konfrontacji z gra-
czem
y
stosującemu strategię
s
y
. Klasyczna
teoria gier, wywodząca się od von Neuman-
na i Morgensterna, opiera się na założeniu
racjonalności graczy. Oznacza to, że każdy
z graczy biorących udział w grze dąży do
osiągnięcia jak największego wyniku. Wyni-
ka to z faktu, że pierwotnie teoria gier była
projektowana jako narzędzie ekonomiczne,
służące wsparciu procesów decyzyjnych w
sytuacjach biznesowych. Tak więc głównym
celem teorii stało się dostarczenie kryteriów
wyboru strategii zapewniających maksymal-
ną wypłatę. Należy zauważyć, że cel ten
przyświeca obydwu graczom, oraz że wypła-
ta danego gracza zależy od strategii przyjętej
przez drugiego. Zatem charakteryzacja opi-
sująca optymalne strategie powinna trakto-
wać obydwu graczy jako integralny układ i
uwzględniać strategie przyjęte przez każde-
go z nich. Dochodzimy więc do fundamen-
talnego pojęcia
równowagi Nasha
.
Układem
strategii w równowadze Nasha nazywamy
strategie
s
x
i
s
y
,
takie że
W
(
s
x
,
s
y
) >
W
(
s
,
s
y
)
dla
s
różnego od
s
x
swojej strategii, przy założeniu, że nie zmieni
jej przeciwnik.
Dochodzimy teraz do problemu istnienia
równowag w poszczególnych grach. Okazuje
się, że w przypadku skończonej liczby stra-
tegii czystych, często nie da się wybrać pary
strategii, które byłyby w równowadze. Aby
rozwiązać ten problem, należy wprowadzić
tzw.
strategie mieszane
. W skrócie mówiąc,
strategia mieszana jest to wektor
S
=
(
a
1
,
…
,
a
n
)
,
taki że współczynniki
a
i
sumują się do
jedynki. W klasycznej teorii gier wartości
a
i
interpretujemy jako prawdopodobieństwa, z
jakimi dany gracz może zagrać
i-
tą strategię
czystą. Wypłatą strategii mieszanej
S
1
=
(
a
1
1
,
…
,
a
1
n
) (górny indeks oznacza numer strate-
gii, nie potęgę) przeciwko
S
2
= (
a
2
1
,
…
,
a
2
n
)
jest wartość oczekiwana:
W
(
S
1
,
S
2
) =
a
1
1
W
(
s
1
,
S
2
) + ... +
a
1
n
W
(
s
n
,
S
2
)
,
gdzie
W
(
s
i
,
S
2
) =
a
2
1
W
(
s
i
,
s
1
) + ... +
a
2
n
W
(
s
i
,
s
n
)
dla każdego
i
.
Ujmując to słowami, wyli-
czamy średnie ważone uwzględniające czę-
stości występowania strategii czystych w da-
nych strategiach mieszanych. Poniżej pojawi
się również inna interpretacja, bardzo istotna
z punktu widzenia gier ewolucyjnych, któ-
re nie są konfliktami dwuosobowymi, lecz
rozgrywają się pomiędzy osobnikami nale-
żącymi do danej populacji. W danej grze, w
strategiach mieszanych może istnieć wiele
układów strategii w równowadze (nawet nie-
skończenie wiele).
Powyższy aparat pojęciowy służy opisowi
konfliktów pomiędzy dwoma konkurującymi
graczami. Jest on intuicyjnym przedstawie-
niem fundamentalnych idei wywodzących się
z prac von Neumanna, Morgensterna i Nasha
i stanowiących podstawy teorii gier. Struktu-
ry te w prosty sposób można rozszerzyć na
bardziej złożone przypadki gier z udziałem
większej liczby graczy. Wtedy funkcje wy-
płat powinny zależeć od strategii wybranych
przez każdego z nich. Liczba graczy może
być dowolnie duża (oczywiście należy mieć
na uwadze złożoność obliczeniową pozwala-
i
W
(
s
y
,
s
x
) >
W
(
s
,
s
x
)
dla
s
różnego od
s
y
Zatem gdy układ jest w równowadze Na-
sha, żadnemu z graczy nie opłaca się zmienić
Metody teorii gier ewolucyjnych
445
Przypadek2strategiiczystych
1
a
punktydlaktórych
a+a=1
1 3
1
a
1
a
a
1
a)
b)
Przypadek3strategiiczystych
a
Ryc. 1. Intuicyjne przedsta-
wienie współrzędnych opi-
sujących częstości względne
(b), w odniesieniu do kla-
sycznego układu współrzęd-
nych kartezjańskich (a).
Zbiory wszystkich możliwych
wartości częstości względnych
są to figury złożone punktów
których współrzędne kartezjań-
skie (wykresy a) sumują się do
jedynki (tzw. simpleksy).
punktydlaktórych
a+a+a=1
1 2 3
a
1
1
a
2
1
a
1
a
2
a
1
a)
b)
jącą na rozwiązanie danego problemu). Wte-
dy koncepcja równowagi jest dokładnie taka
sama. Układ jest w równowadze, jeśli żadne-
mu z graczy nie opłaca się zmienić swojej
strategii, pod warunkiem, że nie zmienią jej
inni. W wiele konfliktów angażuje się tylu
graczy, że wpływ akcji pojedynczego z nich
jest tak mały, że można go pominąć. W takiej
sytuacji funkcja wypłat zależy od uśrednionej
strategii charakteryzującej całą populację. Jest
to strategia mieszana, tylko że w tym przy-
padku współczynniki
a
i
oznaczają wartości
prawdopodobieństwa spotkania gracza sto-
sującego
i
-tą strategię czystą. Wtedy strategię
mieszaną
s
nazywamy
profilem populacji
lub
średnią strategią populacji
. W ogólnym przy-
padku
S
jest profilem w równowadze
, jeśli
W
(
S
,
S
)
≥
W
(
s
,
S
)
dla dowolnej strategii
s
różnej od
S
.
Zatem średnia wypłata żadnej strategii
nie może przewyższać średniej wypłaty w
populacji
W
(
S
,
S
). Można udowodnić, że w
tym przypadku każda strategia czysta wcho-
dząca w skład strategii
S
(czyli taka, że jej
a
i
> 0) osiąga taką samą wypłatę. Jeśli gracz za-
cznie grać strategią czystą nie wchodzącą w
skład
S
,
to jego wypłata się pogorszy. W tym
przypadku, ponieważ działanie pojedynczego
gracza jest nieistotne, dopiero zmiana strate-
gii przez większą frakcję graczy może spowo-
dować pogorszenie średniej wypłaty. Wobec
tego globalny stan populacji
S
jest opłacalny
dla każdego gracza z danej populacji i leży
w jego interesie, aby się nie zmieniał. Siłą
rzeczy profil populacji określa również pro-
porcje występowania osobników grających
poszczególnymi strategiami w populacji. W
tym przypadku dla każdej strategii proporcje
wynoszą:
a
i
=
m
i
/
(m
1
+ ... +
m
n
)
gdzie
m
i
—
liczba
osobników grających
i
-tą strategią.
Dzięki temu stany populacji możemy
przedstawiać na wykresach. Wszyscy ze szko-
ły przyzwyczajeni są do układu współrzęd-
nych kartezjańskich (wykresy z lewej strony
na Ryc. 1), ale w tym przypadku wygodniej-
szy będzie inny sposób. Ponieważ współczyn-
niki
a
i
sumują się do jedynki, zbiór wszyst-
kich możliwych stanów populacji można
przedstawić w postaci tzw. simpleksu (patrz
Ryc. 1, wykresy z prawej strony), czyli wie-
lokąta, którego wierzchołki odpowiadają sta-
nom homogenicznym (wszystkie osobniki
grają tą samą strategią). Zatem w przypadku
rozpatrywania dwóch strategii czystych bę-
dzie to odcinek <0, 1>, trzech strategii trój-
kąt, a czterech czworościan foremny. Dany
stan będzie po prostu punktem należącym
do wnętrza lub brzegu wielokąta. Intuicyjnie
podobny do simpleksów charakter mają na
przykład diagramy wyboru koloru w progra-
3
3
446
K
rzysztof
A
rgAsińsKi
mach graficznych, gdzie na trójkącie mamy
umieszczone kolory o różnym udziale skła-
dowych (czerwieni, zieleni, i niebieskiego),
wierzchołki odpowiadają czystym składowym,
natomiast inne kolory znajdują się wewnątrz.
Dzięki temu zmiany stanu populacji w czasie
mogą być przedstawione jako odpowiednie
krzywe na wykresie.
Dochodzimy teraz do następującego pro-
blemu. W przypadku gier z liczbą graczy
większą niż dwa (w szczególności nieskoń-
czoną), warunek charakteryzujący stany w
równowadze obejmuje sytuację, w której po-
jedynczy gracz wybiera swoją strategię przy
ustalonych strategiach pozostałych graczy. Z
tego wynika, że racjonalnemu graczowi nie
opłaca się zmiana strategii w konflikcie z
innymi racjonalnymi graczami, jeśli gra znaj-
duje się w stanie równowagi. Oczywiście w
życiu nie mamy do czynienia z hiperracjonal-
nymi jednostkami. W szczególności trudno
tego wymagać od wszystkich organizmów ży-
wych, które również angażują się w konflikty
między sobą w codziennej walce o przetrwa-
nie. Zauważmy, że w sytuacji, w której gracze
mogą z jakiś przyczyn zmieniać swoje strate-
gie, konsekwencje mogą być bardzo poważ-
ne. W przypadku, gdyby pewna znacząca licz-
ba graczy odstąpiła od swoich strategii, dany
układ mógłby przestać być opłacalny dla po-
zostałych graczy, co zmusiłoby ich do zmiany
strategii. W efekcie ustaliłby się nowy układ
w równowadze, który również jest narażony
na rozbicie przez spontaniczną zmianę stra-
tegii pewnej liczby graczy. Mamy zatem pro-
blem odporności stanów zrównoważonych
na zaburzenia. Przez zaburzenie rozumiemy
nagłą zmianę strategii przez pewną frakcję
graczy. W naturze przyczyną zaburzeń może
być na przykład skłonność do popełniania
przez graczy błędów przy wyborze strategii.
W przypadku zastosowań czysto biologicz-
nych jest to pojawienie się mutantów w ob-
rębie populacji lub migracja z zewnątrz (in-
wazja), tudzież katastrofy eliminujące nielo-
sowo pewną liczbę graczy. Widać więc, że w
podejściu ewolucyjnym musimy się pożegnać
z założeniem racjonalności graczy. W ramach
nowego paradygmatu zadaniem teorii jest
badanie, w jaki sposób i które stany będą
wybierane przez proces ewolucyjny, a nie
jak w klasycznej teorii gier dostarczanie kry-
teriów wyboru strategii. Może okazać się, że
stany maksymalizujące wypłatę są nieodpor-
ne nawet na drobne zaburzenia. W związku
z tym odporność profili na zaburzenia staje
się kwestia zasadniczą. W następnym punk-
cie zajmiemy się metodami, które stanowią
rozwiązanie tego problemu.
PoJĘcie eWoLUcyJneJ stABiLnoŚci
Zajmijmy się teraz bardziej formalnym
ujęciem ewolucyjnego podejścia do teorii
gier. Pierwotnie teoria gier ewolucyjnych
była po prostu przeniesieniem metod eko-
nomicznych na grunt biologii, z pewnymi
modyfikacjami wynikającymi z argumentów
przedstawionych powyżej. Wprowadzenie za-
cznijmy więc od zapoznania się z pierwotny-
mi problemami, które wymagały tych metod,
czyli od modeli doboru naturalnego. W tym
przypadku przez strategie czyste rozumie-
my cechy fenotypowe osobników (wzorce
zachowań, cechy morfologiczne), natomiast
wypłata jest interpretowana jako darwinow-
skie dostosowanie (fitness, czyli najczęściej
liczba potomstwa). Osobniki nie podejmują
żadnych decyzji, wchodzą w interakcje i po-
noszą tego konsekwencje. W zależności od
posiadanej strategii mają różną liczbę potom-
stwa, które dziedziczy po nich strategię czy-
stą
1
. W wyniku tych różnic względne propor-
cje występowania danych strategii czystych
w populacji (profile-strategie mieszane) zmie-
niają się z pokolenia na pokolenie. W ten
sposób działa proces ewolucyjny odpowie-
dzialny za zmiany i wybór profilu populacji.
Pewne stany populacji nie będą się zmieniać
pod wpływem działania tego procesu. Łatwo
zauważyć, że muszą to być stany, w których
każda strategia ma taką samą wypłatę (czyli
liczbę potomstwa), co nasuwa analogię do
równowagi Nasha. Budowa modelu polega
na opisaniu danego konfliktu (np. pomiędzy
osobnikami agresywnymi i płochliwymi, czy
osobnikami produkującymi potomstwo w
różnych proporcjach płci). Najpierw okre-
śla się strategie, jakimi będą się posługiwać
osobniki, aby na nich opisać funkcje wypłat,
1
Dla uproszczenia przyjęto, że każdy osobnik może stosować jedynie strategię czystą. Problem można też sformu-
łować dla sytuacji, gdy osobnik może stosować strategie mieszane, ale zapis staje się bardziej złożony, gdyż mamy
dwa poziomy mieszania: osobniczy i populacyjny.
Metody teorii gier ewolucyjnych
447
które możliwie realistycznie opisują kształt
interakcji pomiędzy nimi, oraz wywoływa-
ne przez nie zmiany dostosowania (fitness).
Następnie potrzebne są kryteria charaktery-
zujące stany populacji faworyzowane przez
dobór naturalny. Dochodzimy do najważniej-
szego w teorii gier ewolucyjnych pojęcia sta-
bilności ewolucyjnej. Najpierw zapoznamy
się z najprostszym przypadkiem.
że mutant
s
nie jest w stanie zdominować
populacji osobników
S
, natomiast drugi, że
odwrotna sytuacja jest możliwa. Jest to naj-
prostsza charakteryzacja opisująca strategie
tworzące homogeniczne populacje odporne
na spontaniczne pojawianie się mutantów.
Rycina 2 pokazuje przykładowe trajektorie
procesu ewolucyjnego w przypadku istnienia
dwóch strategii ewolucyjnie stabilnych (stra-
tegie czyste
a
1
i
a
2
).
STANY EWOLUCYJNIE STABILNE
Strategia ewolucyjnie stabilna (ang. evo-
lutionarily stable states, ESStates) jest pod-
stawowym pojęciem dość łatwym do intu-
icyjnego zrozumienia. Jednakże w przyrodzie
często mamy do czynienia z populacjami, w
obrębie których osobniki o pewnych stra-
tegiach aby egzystować muszą wchodzić w
interakcje z osobnikami o całkiem odmien-
nych strategiach (np. fenotypach). W takich
sytuacjach to nie pojedyncze strategie mają
być faworyzowane przez proces ewolucyj-
ny, tylko pewne szczególne stany populacji,
w których będą współistnieć w określonych
proporcjach osobniki o odmiennych strate-
giach. Mówimy wtedy o
stanach ewolucyjnie
stabilnych
:
S
jest
stanem ewolucyjnie stabilnym
, jeżeli
W
(
S
,
s
) >
W
(
s
,
s
) dla każdego stanu
s
≠
S
w
pewnym otoczeniu
S
.
Tym razem mamy tylko jeden warunek,
który mówi, że średnia wypłata osobnika z
podpopulacji o średniej strategii
S
, znajdującej
się w populacji o średniej strategii
s
będzie
wyższa niż średnia wypłata w całej populacji,
jeżeli
s
jest pewnym odchyleniem proporcji
STRATEGIA EWOLUCYJNIE STABILNA
Na termin ten (ang. evolutionarily sta-
ble strategy, ESS) często można się natknąć
podczas lektury tekstów z zakresu biologii
ewolucyjnej. W skrócie mówiąc, oznacza on
strategię, która będzie faworyzowana przez
dobór i nie będzie eliminowana przez konku-
rencyjne strategie. Mało kto pamięta dziś, że
jest to pojęcie po raz pierwszy użyte przez
m
AynArdA
-s
mithA
i P
rice
’a
(1973) i ma ono
ściśle zdefiniowany matematyczny sens. Przy-
pomnijmy, że w tym przypadku wypłata jest
interpretowana jako darwinowskie dostoso-
wanie osobnika przejawiającego daną strate-
gię. Załóżmy więc, że mamy daną pierwotną
populację złożoną z osobników o strategii,
na przykład jakimś sposobie zachowania,
oznaczanej przez
S
.
W środowisku zamieszki-
wanym przez osobniki
S
mogą z jakichś przy-
czyn pojawić się mutanty przejawiające inną
strategię
s
. Poniższe warunki charakteryzują
strategię, która będzie odporna na inwazję
dowolnej konkurencyjnej strategii
s
należącej
do uprzednio zdefiniowanego zbioru strate-
gii:
a
i
3
a1,a2-strategieewolucyjnie
stabilne
L-barierainwazyjna
2)
W
(
s
,
s
) <
W
(
S
,
s
) — warunek stabilności
jeśli w pierwszym warunku zachodzi rów-
ność. Pierwszy warunek oznacza, że osobnik
o strategii zmutowanej nie będzie miał więk-
szej liczby potomstwa, kiedy znajdzie się w
populacji złożonej z osobników o strategii
S
.
Warunek ten dopuszcza sytuację, w której
obydwie strategie mają taką samą wypłatę.
Wtedy ich proporcje w populacji nie zmie-
niają się, ponieważ liczba potomstwa osob-
nika nie zależy od jego strategii. Aby temu
zapobiec, musi być spełniony drugi warunek.
Oznacza on, że osobniki
S
będą sobie lepiej
radzić w populacji złożonej z osobników
s
.
W skrócie mówiąc, warunek pierwszy mówi,
L
a
1
a
2
Ryc. 2. Trajektorie ewolucji populacji, w której
występują trzy strategie.
Prosta L jest barierą inwazyjną rozdzielającą obszary
przyciągania strategii
a
1
i
a
2, które są ewolucyjnie
stabilne. Strategia a3 jest zawsze eliminowana z po-
pulacji.
Strategia
S
jest
ESS
jeśli dla innych strate-
gii (oznaczmy je przez
s
) zachodzą następują-
ce warunki:
1)
W
(
s
,
S
)
≤
W
(
S
,
S
) — warunek Nasha
[ Pobierz całość w formacie PDF ]