Czym jest teoria gier algorytmicznych? Wyjaśnione przykładami

W 1999 roku, kiedy Nisan i Ronen wnieśli swoje pomysły do ​​artykułu, świat był świadkiem nowej koncepcji Algorithmic Mechanism Design. Próbuje zanegować Cenę Anarchii, gdzie interes własny zawsze skutkuje zdegradowanym systemem.

Ich artykuł dowiódł, że wiele egoistycznych stron może ustanowić produktywny system w równowadze. Tak więc zamiast patrzeć na degradującą się gospodarkę, spojrzelibyśmy na opiekę społeczną i maksymalizację dochodów.

Algorytmiczna teoria gier (AGT) opiera się na zrozumieniu Algorithmic Mechanism Design (AMD) .

Podczas gdy AMD opisuje, że interes własny może prowadzić do dobrego systemu, AGT ma na celu przeanalizowanie i zaprojektowanie strategicznego układu, który opisuje działania zainteresowanych uczestników.

Zanim przyjrzymy się, jak AGT działa w środowisku strategicznym, przyjrzyjmy się, jak działa teoria gier!

Zrozummy teorię gier za pomocą przykładu

W idealnym świecie, w którym każdy ruch jest wyrachowanym przedsięwzięciem, teoria gier nie miałaby takiego sensu jak dzisiaj.

Pomysł obliczenia następnego ruchu inteligentnych, racjonalnych obywateli jest zarówno ekscytujący, jak i przerażający.

Teoria gier mówi, że w każdej sytuacji społecznej rywalizujące strony mogą podejmować racjonalne decyzje, oceniając słuszność możliwości i szacując ruch netto konkurenta.

Choć może się to wydawać hazardem, teoretycy przywrócili dającą się wytłumaczyć strategię, która wykorzenia przekonanie, że jest to hazard.

Najczęściej przytaczanym przykładem jest dylemat więźnia.

Dowiedz się: 8 najlepszych projektów, które każdy programista powinien wypróbować bezbłędnie

Wyjaśnienie dylematu więźnia

Założenie jest proste – gdy policja złapała dwóch skazanych i przesłuchała ich w sprawie przestępstwa, żaden z nich nie przerwał ich milczenia.

Tak więc prokurator okręgowy postanowił to uprościć, stawiając przed nimi trzy warunki, ponieważ siedzą obok siebie.

• Warunek 1: Jeśli żadne z nich nie przyzna się do przestępstwa, trafiają do więzienia na sześć lat.
• Warunek 2: Jeśli jeden z nich wypuści drugiego, sygnalista może swobodnie wędrować, podczas gdy drugi wchodzi przez dziesięć lat.
• Warunek 3: Jeśli oboje przyznają się, trafiają do więzienia na rok.

Natychmiast po zapoznaniu się z warunkami są zabierani do osobnego pokoju, aby podejmować decyzje.

Możemy przekazać te dane w formie macierzy jako takiej;

Źródło

Rozwiązanie tego problemu jest proste;

Każdy więzień rozważy powiedzenie prawdy o zbrodni. Żaden z nich nie może ściśle powiedzieć, że drugi pozostanie cicho. Poddając się więc prawdopodobieństwu, oboje postanawiają przyznać się do przestępstwa i trafiają do więzienia tylko na rok.

Teoria gier jest potężną bronią w rękach tego, kto ją dzierży. Możemy rozszyfrować nawet najbardziej złożone sytuacje, rozumiejąc naturę liczb i umiejscowienie układu społecznego.

Algorytmiczna teoria gier

Rozważmy teraz diagram Venna teorii gier i informatyki. Wyobraź sobie drastyczny wzrost poziomu dokładności, dla którego warto sporządzać wykresy prawdopodobieństwa uzyskania odpowiedzi.

I to właśnie robi Algorytmiczna Teoria Gier (AGT) !

Próbuje rozwiązywać współczesne problemy poprzez znalezienie idealnej równowagi między algorytmami komputerowymi a teorią gier.

Mówiąc prościej, Algorytmiczna Teoria Gier próbuje określić równowagę społeczno-ekonomiczną pomiędzy wykonaniem zadania. Wykorzystuje również zasady równowagi Nasha; stwierdza, że ​​gdy uczestnicy znajdą strategię, która im odpowiada, nie będą chcieli od niej odejść, dopóki nie przestanie ona działać na ich korzyść.

Weźmy mały przykład, aby zrozumieć działanie algorytmicznej teorii gier.

Wróćmy do szkoły, kiedy graliśmy w takie gry, jak Kho-Kho, Ice & Water, Chain-Cut itp. Każda z tych gier ma piękny wygląd i mechanizm.

Rozważmy na przykład lód i wodę;

• Jest kilku graczy i jeden łapacz. Łapacz ma zamienić wszystkich w lód.
• Inni gracze mają moc, aby po dotknięciu kogoś z powrotem zawrócić do wody.
• Są wolne strefy, w których gracze mogą odpocząć przez 30 sekund.

Teraz, jeśli przyjrzysz się uważnie, zobaczysz, że każda z tych zasad tworzy mechanizm gry i określa jej projekt.

• Gracze mogą grać w tę grę tak długo, jak uznają ją za interesującą. Tutaj The Nash Equilibria opisuje, że dopóki gracze uznają, że ich strategia działa, a gra jest interesująca, będą grać.
• Racja gracza to nie dać się złapać. I działa na tej racji, rozumiejąc ustawienia. Wdraża podejście oparte na celu, w którym wygrywa grę, nie dając się złapać. Jest to powszechnie znane jako projektowanie mechanizmów lub teoria gier odwróconych.
• Teraz, w przypadku gdy każdy gracz bierze pod uwagę tylko jeden motyw – „nie dać się złapać” – i nie bierze pod uwagę drugiej jego części – „ratowania innych graczy”, wtedy ta koncepcja nazywa się Ceną Anarchii. Wyjaśnia, w jaki sposób wydajność dowolnego systemu ulegnie pogorszeniu z powodu samolubnych zachowań graczy.

Teraz z trzech wymienionych powyżej koncepcji wyłania się mnóstwo innych koncepcji. Chociaż wszystkie one są całkowicie lub umiarkowanie związane z teorią gier, tworzą funkcjonalną podstawę algorytmicznej teorii gier.

Zamówienie: 42 ekscytujące pomysły i tematy dotyczące projektów w Pythonie dla początkujących

Teraz pojawia się pytanie: „Jak reprezentujemy środowisko strategiczne pod względem algorytmów?”

Przyjrzyjmy się teraz, jak możemy użyć Pythona do zdefiniowania strategicznego środowiska i zrozumienia implementacji Nashpy w danej sytuacji.

Wyobraź sobie, że grasz z jednym ze swoich przyjaciół w grę w papier-kamień-nożyce. Każdy z was ma jedną z trzech opcji;

• Głaz
• Papier
• Nożyce

A rubryką na wygraną w grze jest

• Kamienie kruszą nożyczki
• Nożyczki tną papiery
• Papier obejmuje skałę

A to oznacza, że ​​jeśli obaj gracze zaprezentują rocka, będzie to oznaczać zmiany.

Możemy to przedstawić w postaci macierzy 3×3, w której Aij jest;

Źródło

Uwaga: tutaj i oraz j to tury rozgrywane przez dwóch graczy.

Tutaj,

• Zero oznacza, że ​​oboje graliście w ten sam przedmiot (kamień-rock lub papier-papier)
• Jeden reprezentuje, że jeden z was przebił drugiego (jak nożyce do skał)
• Minus Jeden oznacza, że ​​któryś z was przegrał, ponieważ drugi cię przebił (jak papier skalny)

Teraz, aby przedstawić to na Nashpy, napiszesz kod, który wygląda mniej więcej tak;

Źródło

Końcowe przemyślenia

Algorytmiczna teoria gier jest idealną zasadą w dzisiejszym świecie, w którym rywalizacja wynika z własnego interesu, a zwycięstwo jest osiągnięciem własnego interesu.

Tak więc, jako współcześni menedżerowie, nauczyciele, dyrektorzy ds. informatyki lub biznesmeni, jeśli rozumiesz dominację algorytmicznej teorii gier, pozwól mi zmienić cytat Severusa Snape'a z Harry'ego Pottera;

„Algorytmiczna teoria gier może nauczyć Cię, jak butelkować sławę, warzyć chwałę, a nawet powstrzymywać straty”.

Zrozumienie algorytmicznej teorii gier może pomóc w radzeniu sobie z liczbami bardziej zdecydowanie niż kiedykolwiek. W obecnej epoce, w której decydujemy o szczegółach, aby opracować zrównoważony plan, AGT okazuje się aspektem transformacyjnym.

Wiemy już, że Data Science może przekształcić firmy w lukratywną arenę, ale AGT może podnieść próg.

Załóżmy, że nadal sceptycznie podchodzisz do teorii gier i tego, że data science jest dziś najbardziej lukratywną i konkurencyjną profesją.

Jeśli jesteś zainteresowany nauką o danych, sprawdź IIIT-B i upGrad's PG Diploma in Data Science, który jest stworzony dla pracujących profesjonalistów i oferuje ponad 10 studiów przypadków i projektów, praktyczne warsztaty praktyczne, mentoring z ekspertami z branży, 1- on-1 z mentorami branżowymi, ponad 400 godzin nauki i pomocy w pracy z najlepszymi firmami.