Blisko 60-letni dylemat teorii gier został rozwiązany

Profesor inżynierii elektrycznej i komputerowej na Uniwersytecie Kalifornijskim w Santa Cruz, od dawna pracuje z kolegami nad złożonym podzbiorem teorii gier zwanym grami różnicowymi. W związku z tym blisko 60 lat istniał dylemat, który w końcu został rozwiązany.

Blisko 60-letni dylemat teorii gier został w końcu rozwiązany
Blisko 60-letni dylemat teorii gier został w końcu rozwiązany123RF/PICSEL

Teoria gier to dział matematyki, który zajmuje się badaniem optymalnego zachowania w różnorodnych sytuacjach, jak na w przypadku konfliktu interesów. Znajduje swoje zastosowanie w wielu dziedzinach nauki, począwszy od ekonomii i informatyce a skończywszy na biologii i socjologii. Aby lepiej rozumieć, jak autonomiczne samochody poruszają się po sieci dróg, naukowcy korzystają właśnie z teorii gier. Ten model matematyczny ma za zadanie wyjaśniać, jak racjonalni agenci zachowują się strategicznie, aby osiągnąć swoje cele.

Gra „pogoń za ścianą"

Profesor Dejan Milutinovic wraz z kolegami od dawna zajmuje się złożonym podzbiorem teorii gier zwanym grami różnicowymi, który dotyczy graczy w ruchu. Jedną z tych gier jest tak zwana gra w „pogoń ze ścianą”, polega ona na tym, że szybszy prześladowca stara się złapać wolniejszego uciekiniera, który może poruszać się tylko wzdłuż ściany. Od czasu powstania tego prostego schematu nazwanego „pogoń ze ścianą”, istnieje dylemat, który nie został rozwiązany od blisko 60 lat. Mianowicie chodzi o zestaw pozycji, przy których uważano, że nie istnieje żadne optymalne rozwiązanie gry.

W najnowszej publikacji w czasopiśmie „IEEE Transactions on Automatic Control” Milutinovic i jego koledzy udowodnili, że wspomniany dylemat w rzeczywistości nie istnieje. Wprowadzili nową metodę analizy, dzięki której dowiedli, że zawsze istnieje deterministyczne rozwiązanie problemu gra w „pogoń za ścianą”.

Teoria Nasha

Jedną z najczęściej rozpoznawalnych koncepcji w teorii gier jest koncepcja Nasha. Koncepcja matematyka John Nash określa optymalną strategię gry dla wszystkich graczy w grze. Chodzi o to, aby zakończyć grę z jak najmniejszymi stratami u wszystkich graczy. Jeżeli gracz nie zdecyduje się podążać za tą koncepcją, będzie żałował, co motywuje do tego, aby przyjąć strategię równowagi. Czyli strategia każdego z graczy jest optymalna, przyjmując wybór jego oponentów za ustalony.

Jak to się ma do dylematu gry „pogoń za ścianą”? W tej grze, oprócz optymalnych rozwiązań klasycznej pary strategii równowagi Nasha, istnieje jeden zestaw pozycji graczy, który wywołuje dylemat przyjęty przez społeczność naukową jako fakt.

Dylemat

Milutinović i jego koledzy nie przyjęli tego faktu do wiadomości i postanowili rozwiązań ten dylemat raz na zawsze. Wykorzystali w tym celu koncepcję, która nie istniała, gdy wymyślono wspomnianą grę. Korzystając z rozwiązania równania Hamiltona – Jacobiego – Isaaca i wprowadzając analizę szybkości strat do rozwiązania pojedynczej powierzchni, doszli do wniosku, że optymalne rozwiązanie gry można określić we wszystkich okolicznościach gry i rozwiązać dylemat.

Mowa tutaj o równaniach różniczkowych cząstkowych pierwszego rzędu, opisujące ruch układu mechanicznego. W przypadku gry polegającej na układzie przyjętym w „pogoni za ścianą” brak dobrze zdefiniowanych pochodnych stwarza dylemat. W związku z czym, dzięki użyciu rachunku różniczkowego do znalezienia pochodnych tych funkcji i wprowadzeniu analizy szybkości strat, udało rozwiązać się dylemat.

Kiedy weźmiemy analizę wskaźnika strat i zastosujemy ją gdzie indziej, optymalne działania gry z klasycznej analizy nie zostaną naruszone. Bierzemy klasyczną teorię i rozszerzamy ją o analizę szybkości strat, więc rozwiązanie istnieje wszędzie. To ważny wynik pokazujący, że rozszerzenie nie jest tylko poprawką do znalezienia rozwiązania na pojedynczej powierzchni, ale fundamentalnym wkładem.
powiedział Milutinovic
W Japonii zakwitły wiśnie. Dla mieszkańców to czas radościHARUMI OZAWA / AFPTV / AFPAFP
Masz sugestie, uwagi albo widzisz błąd?
Dołącz do nas