Jako student informatyki zapoznałem się z teorią gier, ale nie widziałem zbyt wielu szczegółów na ten temat. Szukałem w Google i przeglądałem książki o teorii gier, które potwierdziły jej wykorzystanie w informatyce. Rozpocząłem formalne studium teorii gier z perspektywy ekonomisty. Teraz chcę poznać zastosowania teorii gier w informatyce. Jakie są ostatnie ważne osiągnięcia informatyków w takich dziedzinach, jak sztuczna inteligencja i teoria złożoności, które wykorzystują elementy teorii gier? Czy istnieje sposób podejścia do teorii gier bardziej zakorzeniony w informatyce niż w ekonomii?
reference-request
gt.game-theory
SM Shahinul Islam
źródło
źródło
Odpowiedzi:
Jednym z najbardziej znanych przykładów teorii gier w informatyce jest zasada minimax Yao . Niech będzie zbiorem danych wejściowych dla jakiegoś problemu i niech będzie zbiorem (deterministycznych) algorytmów dla tego problemu. Zasada Yao stwierdza, że gdzie oczekiwania po lewej i prawej stronie są uwzględniane w odniesieniu do dowolnego pożądanego rozkładu prawdopodobieństwa odpowiednio dla algorytmów i danych wejściowych.X A
Na przykład: Każdy deterministyczny algorytm sortowania oparty na porównaniu wymaga czasu średnio na sortowanie tablicy permutowanej równomiernie losowo. ( Dowód: W każdym binarnym drzewie z liści, co najmniej połowa liście mają głębokość co najmniej . ) zasada So Yao oznacza, że najgorszy przypadek przewidywany czas uruchomiony dowolny randomizowane porównanie oparte sortowania algorytm to także .Ω(nlogn) N (lgN)/2 □ Ω(nlogn)
Zasada minmax Yao łatwo wynika z twierdzenia von Neumanna o minimakach dla dwóch graczy , w których jeden gracz zapewnia dane wejściowe, a drugi algorytm.
źródło
Istnieje wiele teoretycznych charakterystyk gier dla klas złożoności. Najbardziej znany może być
AP = PSPACE (ustalenie, kto wygra deterministyczną grę, która trwa przez wielomianową liczbę ruchów, to pytanie kompletne dla PSPACE),
IP = PSPACE (w deterministycznej grze o wielomianowej długości, rozgrywanej przeciwko graczowi, który wykonuje losowe ruchy, z rozróżnieniem przypadków, w których Twoja szansa na wygraną wynosi> 0,9, a <0,1 to ukończenie PSPACE),
ale jest ich wiele, wiele więcej.
źródło
Teoria gier odegrała znaczącą rolę w rozwiązaniach „problemu pełnej abstrakcji” w semantyce języka programowania. W szczególności pierwszą w pełni abstrakcyjną semantykę dla PCF Plotkina podano za pomocą gier jako modeli.
Odpowiednie cytaty to:
Pełna abstrakcja na PCF , autorstwa Samsona Abramsky'ego, Radhy Jagadeesan i Pasquale Malacaria
i
On Full Abstraction for PCF: I, II i III , autorstwa JME Hyland i C.-HL Ong
które ukazały się w Information and Computation , tom 163, wydanie 2, 15 grudnia 2000 r.
źródło
Innym znanym przykładem użycia teorii gier w CS jest synteza: w syntezie otrzymujemy specyfikację na wejściach I i wyjściach O (np. W logice czasowej lub jako automat) i chcemy automatycznie wygenerować system (tj. stan przetwornika), co gwarantuje, że dla każdej sekwencji wejściowej środowiska obliczenia indukowane przez przetwornik spełniają specyfikację.
Jak się okazuje, synteza może być sformułowana jako gra między środowiskiem a systemem, w której zwycięska strategia dla systemu odpowiada przetwornikowi.
Bardzo ważnym narzędziem z teorii gier stosowanym w tym kontekście jest determinacja Borela, szczególnie gdy pracujemy nad nieskończonymi obliczeniami.
Możesz zacząć o tym czytać w ankiecie Moshe Vardi .
źródło
Łatwiej jest mi myśleć o zastosowaniach informatyki (technik) w teorii gier, niż na odwrót. Istnieje bardzo aktywna dziedzina algorytmicznej teorii gier, która koncentruje się na opracowywaniu wydajnych algorytmów (lub wyników złożoności), np. Dla równowagi Nasha, wartości Shapleya i innych takich standardowych koncepcji teoretycznych gier. Często te pojęcia są łatwe do zdefiniowania, ale zbyt trudne do obliczenia bezpośrednio z definicji. Ta praca rozciąga się przynajmniej na projektowanie mechanizmów, w których próbujemy manipulować regułami aukcji w celu zagwarantowania zachowania agentów (np. Chcielibyśmy, aby zgłaszali prawdziwe oferty) lub ogólnych wyników (np. Chcielibyśmy zagwarantować maksymalne dochód.)
Noam Nisan, Yoav Shoham, Tim Roughgarden i wielu innych mają fascynujące prace na temat projektowania mechanizmów z teoretycznego punktu widzenia; Vince Conitzer zastosował techniki AI do problemu w celu opracowania automatycznego projektu mechanizmu.
Jeśli chodzi o bardziej stosowaną sztuczną inteligencję, trudno myśleć o systemach wieloagentowych bez myślenia o nich jak o grach. Platforma Częściowo obserwowalna gra stochastyczna (POSG) jest często używana do omawiania ustawień dla wielu agentów; zgodnie z właściwymi kryteriami funkcji nagrody staje się DEC-POMDP.
źródło
Teoria gier kombinatorycznych odgrywa rolę w logice i informatyce, jak na przykład w grze Ehrenfeucht-fraïssé , która jest grą logiczną rozgrywaną na strukturach teoretycznych. W każdej turze pierwszy gracz wybiera element z jednej z dwóch struktur, a drugi musi wybrać element z drugiej, starając się zachować lokalne izomorfizmy między elementami wybranymi do tego momentu.
Główne twierdzenie dotyczące tej gry z grubsza mówi, że jeśli Gracz 2 ma strategię wygrywania w grze opartej na dwóch strukturach, to nie istnieje formuła logiczna pierwszego rzędu, która różnicowałaby te dwie struktury.
Ten wynik jest wykorzystywany w wielu wynikach wyrażania dla logiki pierwszego rzędu, a także dla innych logiki (istnieje zwłaszcza rozszerzenie twierdzenia na monadyczną logikę drugiego rzędu).
Te wyniki ekspresji mają z kolei silne zastosowanie w informatyce, np. Do weryfikacji formalnej, teorii baz danych itp.
źródło
Artykuł w kolumnie Distributed Computing Column 42 próbuje przybliżyć teoretyczną perspektywę do problemów z obliczeniami rozproszonymi.
Cytat z „Idit Keidar”, ówczesnego edytora:
Teoria gier i tolerancja na awarie oferują dwa różne warianty odporności systemów rozproszonych - ten pierwszy jest odporny na uczestników próbujących zmaksymalizować własne narzędzia, podczas gdy ten drugi zapewnia odporność na nieoczekiwane błędy. Ta kolumna przedstawia próby połączenia tych dwóch. Zawiera przegląd najnowszych prac, które zapewniają oba smaki solidności autorstwa Ittai Abraham, Lorenzo Alvisi i Joe Halpern. Ittai, Lorenzo i Joe dyskutują o tym, jak strategiczne zachowanie oparte na teorii gier można uwzględnić w rozproszonych protokołach odpornych na błędy. Stanowią one przekonujący argument za wprowadzeniem teoretycznej perspektywy gier na problemy z rozproszonymi komputerami.
źródło