23. Argasinski, Metody teorii gier ewolucyjnych(2009).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-

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

punktydlaktórych

a+a=1

1 3

a 1

Przypadek3strategiiczystych

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

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-

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:

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,

a 1

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

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: