Algorytmy obliczania równowagi Nasha.

10

Przeszukałem forum, aby sprawdzić, czy zostało to już zadane, i chociaż omawiamy teorię gier algorytmicznych, nie mogłem znaleźć rozwiązania tego konkretnego problemu. Próbuję dowiedzieć się, jaki jest najbardziej znany algorytm obliczania przybliżonej (mieszanej strategii) równowagi Nasha w skończonej grze n-person. Oczywiście algorytmem tym byłby PPAD. Bardziej interesuje mnie szybkość / wydajność niż doskonała dokładność algorytmu.

Dzięki, Philip

ds.algorithms gt.game-theory Philip White
źródło
Pomożemy Ci lepiej, jeśli podasz więcej szczegółów. Na przykład, jaką wartość masz na myśli? Czy masz na myśli jakąś specjalną strukturę funkcji wypłaty? Czy naprawdę potrzebujesz równowagi Nasha, czy może wystarczyłaby równowaga skorelowana? Szukasz czegoś z dobrymi możliwościami do udowodnienia, czy czegoś o dobrych osiągach praktycznych? n
Warren Schudy,

Odpowiedzi:

7

Krótka odpowiedź jest taka, że ​​chociaż istnieją pewne algorytmy wielomianowe pozwalające na znalezienie przybliżonej równowagi Nasha, wszystkie znajdują stosunkowo słabe przybliżenia - prawdopodobnie nie są wystarczająco dobre, jeśli faktycznie próbujesz znaleźć algorytm do gry. Więcej jest znanych z gier dla dwóch graczy niż dla gier dla wielu graczy.

Jeśli rzeczywiście próbujesz znaleźć (przybliżoną) równowagę Nasha, jedną z łatwych do zakodowania rzeczy, które możesz wypróbować, jest symulacja gry, przy czym każdy gracz używa algorytmu losowej większości ważonej (http://en.wikipedia.org/ wiki / Randomized_weighted_majority_alameterm). Nie gwarantuje się, że zadziała, ale w wielu przypadkach zadziała (I jest zagwarantowane w niektórych klasach gier, takich jak gry o sumie zerowej). W szczególności, jeśli proces ten w ogóle zbiegnie się, gwarantuje się, że zbiegnie się do równowagi Nasha. Niebezpieczeństwo polega na tym, że nie zbiegnie się ono i będzie trwać wiecznie - ale nawet w tym przypadku empiryczna historia gry będzie zbieżna z zestawem zgrubnie skorelowanych równowag.

Aaron Roth
źródło
Zacząłem przyglądać się artykułowi wymienionemu w powyższej odpowiedzi. Nie wszystko zrozumiałem (lub większość na pierwszy rzut oka) ... czy możesz wyjaśnić, dlaczego przybliżenie jest „stosunkowo słabe?” Czy mógłbyś też krótko wyjaśnić, czym jest „zgrubna skorelowana równowaga”? Wiem, czym jest skorelowana równowaga, ale co to znaczy dla takiego równania. być grubym. Wreszcie, co masz na myśli przez „empiryczną historię gry się zbiegnie ... [itd.]”? W jaki sposób coś, co nigdy nie jest zbieżne, może zbiegać się w zbiór CCE? Dzięki za odpowiedź, teraz szukam artykułu w Wikipedii.
Philip White,
Aby zapoznać się z niektórymi podstawami
Aaron Roth
Jeśli chcesz skorelowanych równowag, a nie zgrubnych, skorelowanych równowag, możesz skorzystać z ucznia bez wewnętrznego żalu. Na przykład (wtyczka bezwstydna) cs.brown.edu/~ws/papers/regret.pdf . Istnieją również algorytmy do obliczania skorelowanych równowag bezpośrednio w czasie wielomianowym.
Warren Schudy,
10

n

Joseph O'Rourke
źródło
4

Jeśli interesują Cię algorytmy faktycznie zaimplementowane w oprogramowaniu, jest kilka takich, które znam:

  1. pakiet GAMBIT (http://www.gambit-project.org/doc/index.html) implementuje kilka algorytmów równowagi Nasha dla normalnej postaci dla dwóch graczy i dla wielu graczy, aw niektórych przypadkach rozbudowanych gier formalnych.

  2. GameTracer (http://dags.stanford.edu/Games/gametracer.html) implementuje algorytmy GNM i IPA Govindana i Wilsona dla normalnych gier typu n-player.

  3. W przypadku dużych gier normalna reprezentacja postaci jest problematyczna, ponieważ rozmiar rośnie wykładniczo w liczbie graczy. Zamiast tego, jeśli funkcja użyteczności gry ma pewną strukturę, możesz użyć „zwięzłej reprezentacji” (np. Gry graficzne, gry symetryczne, gry akcji), aby wyrazić ją przy użyciu znacznie mniejszej przestrzeni; a ponadto struktura może być często wykorzystywana do przyspieszania obliczeń. Pod względem oprogramowania AGG Solver (http://agg.cs.ubc.ca) dostosowuje algorytm GameTracer GNM i algorytm simpdiv GAMBIT do reprezentacji w grze graficznej (AGG). (Oświadczenie: Jestem zaangażowany w rozwój tego oprogramowania.)

Albert
źródło