Kiedy strategie -Nash Equilibrium zbiegają się ze strategiami Nash Equilibrium?

Równowagi Nasha ogólnie nie można obliczyć. -Nash równowaga jest zbiorem strategii, gdzie podane strategie rywalek, każdy gracz uzyska w ciągu maksymalnej możliwej oczekiwanego wypłat. Znalezienie równowagi Nash, biorąc pod uwagę i grę, jest .$\epsilon$$\epsilon$$\epsilon$$\epsilon$$\mathsf{PPAD}$

Idąc ściśle za definicjami, wydaje się, że nie ma szczególnego powodu, aby sądzić, że strategie danej Nash równowagi są gdziekolwiek bliskie strategiom dowolnej równowagi Nasha. Jednak często widzimy literaturę nieco niechlujnie używającą frazy „w przybliżeniu oblicz równowagę Nasha”, gdy oznacza to powiedzenie „oblicz równowagę przybliżoną Nasha”.$\epsilon$

Zastanawiam się, kiedy drugi oznacza pierwszy; to znaczy, dla jakich gier możemy się spodziewać Równowaga Nasha będzie „bliska” równowadze Nasha?$\epsilon$

Bardziej formalnie, załóżmy, że mam grę na graczy i sekwencję profili strategicznych .$n$$(s_1^{(1)},\dots,s_n^{(1)}), (s_1^{(2)},\dots,s_n^{(2)}), (s_1^{(3)},\dots,s_n^{(3)}), \dots$

Każda jest równowagą -Nash, a sekwencja zbiega się do zera.$(s_1^{(i)},\dots,s_n^{(i)})$$\epsilon_i$$\epsilon_1,\epsilon_2,\epsilon_3,\dots$

Moje pytania:

1. Kiedy (na jakich warunkach / założeniach) wszystkie strategie są zbieżne? Oznacza to, że dla każdego gracza , koniecznie się zbiegają.$j$$s_j^{(1)},s_j^{(2)},s_j^{(3)},\dots$

2. W jakich dalszych warunkach granica tej sekwencji jest w rzeczywistości równowagą Nasha w grze? (Wydaje mi się, że dalsze założenia nie powinny być potrzebne; tj. Jeśli wszystkie strategie się zbiegną, limit powinien wynosić NE).

3. Kiedy algorytm obliczania -równowaga Nasha koniecznie oznacza algorytm w przybliżeniu strategii obliczeniowych równowagi Nasha? Czy powyższe warunki są wystarczające?$\epsilon$

Dziękuję bardzo!

Edytuj 2014-03-19

Po przeczytaniu referencji w odpowiedzi Rahula bardziej rozsądne wydaje się raczej odległości między rozkładami niż zbieżnych sekwencji. Spróbuję więc sformułować pytania, a także przedstawić kilka ostatnich myśli.$\ell_1$

1. (Cóż, jest to zbyt zależne od algorytmu, aby naprawdę mieć odpowiedź. Bez ograniczeń algorytmu, możesz mieć dwie odrębne równowagi Nasha, a następnie, gdy podłączasz coraz mniejszy do algorytmu, odległość między kolejnymi wyniki mogą być nadal duże, ponieważ wyniki oscylują między równowagami.)$\epsilon$$\ell_1$

2. Załóżmy, że jest profilem strategii, tzn. Rozkładem produktów według strategii graczy. W przypadku jakich gier możemy powiedzieć, że jest -równowaga Nasha implikuje dla pewnej równowagi Nash , gdzie jako ? (Pamiętaj, że odwrotność obowiązuje, jeśli wypłaty są ograniczone przez ).$p$$p$$\epsilon$$\|p - q\|_1 \leq \delta$$q$$\delta \to 0$$\epsilon \to 0$$1$

   Jest to w rzeczywistości trudne, ponieważ w złożoności, co nazywamy „grą”, jest w rzeczywistości sekwencją gier sparametryzowanych przez , liczbę czystych strategii („akcji”). Więc jak , a względne stawki mają znaczenie. Oto prosty kontrprzykład pokazujący, że odpowiedź nie brzmi „wszystkie gry”. Załóżmy, że naprawiliśmy sekwencję malejących . Następnie dla każdego grę dwuosobową na działaniach, w których, jeśli gracz zagra pierwszą akcję, otrzyma wypłatę niezależnie od tego, co gra drugi gracz; jeśli gracz zagra drugą akcję, otrzyma wypłatę w wysokości$n$$n \to \infty$$\epsilon \to 0$$\epsilon_1,\epsilon_2,\dots$$\epsilon_n$$n$$1$$1-\epsilon_n$niezależnie od tego, co gra inny gracz; a jeśli gracz zagra jakąkolwiek inną akcję, otrzyma wypłatę niezależnie od tego, co gra inny gracz.$0$

   Zatem każda gra ma równowagę -e (obie grają drugą akcję), która jest maksymalnie daleko w odległości od jej jedynej równowagi Nasha (obie grają pierwszą akcję).$n$$\epsilon_n$$\ell_1$

   Zatem dwa interesujące pytania częściowe:

   1. Dla ustalonej gry i stałej , niezależnie od tego, czy dla „wystarczająco małego” obowiązuje powyższy warunek (wszystkie -equilibria są zbliżone do równowagi Nasha).$n$$\epsilon$$\epsilon$
   2. Być może w zasadzie to samo pytanie, ale czy warunek się utrzymuje, jeśli różnice w wypłatach są ograniczone stałą .$n \to \infty$

3. To samo pytanie co (2), ale odnoszące się do rzeczywistej równowagi obliczonej przez algorytmy. Myślę, że prawdopodobnie otrzymamy albo algorytmiczne / konstruktywne odpowiedzi, albo wcale, więc rozróżnienie nie ma większego znaczenia.

Poniższy artykuł przynajmniej formalizuje pojęcie przybliżonych równowag zbliżonych do równowag dokładnych i potwierdza pewne powiązane wyniki strukturalne.

Pranjal Awasthi, Maria-Florina Balcan, Avrim Blum, Or Sheffet i Santosh Vempala (2010). O równowagach Nasha gier stabilnych w przybliżeniu. W materiałach z trzeciej międzynarodowej konferencji na temat algorytmicznej teorii gier (SAGT'10), 78–89.

W szczególności w artykule podano przykład klasy gier dla pytania 3.