Kapan -Nash strategi keseimbangan menyatu dengan strategi Nash Equilibrium?

Nash Equilibria tidak dapat dihitung secara umum. Suatu keseimbangan -Nash adalah seperangkat strategi di mana, mengingat strategi lawan, masing-masing pemain memperoleh dalam dari hasil maksimum yang diharapkan. Menemukan keseimbangan -Nash, diberikan dan permainan, adalah .ϵ ϵ ϵ P P A $\epsilon$$\epsilon$$\epsilon$$\epsilon$$\mathsf{PPAD}$

Sesuai dengan definisi-definisi itu, tampaknya tidak ada alasan khusus untuk meyakini bahwa strategi-strategi dari keseimbangan -Nash yang diberikan dekat dengan strategi-strategi kesetimbangan Nash mana pun. Namun, kita sering melihat literatur agak sembarangan menggunakan frasa seperti "kira-kira menghitung keseimbangan Nash" ketika itu berarti mengatakan "menghitung perkiraan Nash-ekuilibrium".$\epsilon$

Jadi, saya bertanya-tanya kapan yang kedua menyiratkan yang pertama; yaitu, untuk game apa kita berharap -Nash equilibria menjadi "dekat" dengan Nash equilibria?$\epsilon$

Secara lebih formal, misalkan saya memiliki permainan pada pemain dan serangkaian profil strategi .( s ( 1 ) 1 , … , s ( 1 ) n ) , ( s ( 2 ) 1 , … , s ( 2 ) n ) , ( s ( 3 ) 1 , … , s ( 3 ) n ) , $n$$(s_1^{(1)},\dots,s_n^{(1)}), (s_1^{(2)},\dots,s_n^{(2)}), (s_1^{(3)},\dots,s_n^{(3)}), \dots$

Setiap adalah \ epsilon_i -Keimbang ekuivalen, dan urutan \ epsilon_1, \ epsilon_2, \ epsilon_3, \ titik-titik bertemu menjadi nol.ϵ i ϵ $(s_1^{(i)},\dots,s_n^{(i)})$$\epsilon_i$$\epsilon_1,\epsilon_2,\epsilon_3,\dots$

Pertanyaan saya:

1. Kapan (dalam kondisi / asumsi apa) semua strategi bertemu? Yaitu, untuk setiap pemain $j$ , $s_j^{(1)},s_j^{(2)},s_j^{(3)},\dots$ tentu konvergen.

2. Dalam kondisi lebih lanjut apa batas urutan ini sebenarnya merupakan keseimbangan permainan Nash? (Tampak bagi saya bahwa tidak ada asumsi lebih lanjut yang diperlukan; yaitu , jika semua strategi bertemu, batasnya harus NE).

3. Kapan suatu algoritma untuk penghitungan -Nash equilibria perlu menyiratkan suatu algoritma untuk kira-kira strategi penghitungan kesetimbangan Nash? Apakah kondisi di atas cukup?$\epsilon$

Terima kasih banyak!

Edit 2014-03-19

Setelah membaca referensi dalam jawaban Rahul, tampaknya lebih masuk akal untuk berpikir dalam hal jarak antara distribusi daripada urutan konvergen. Jadi saya akan mencoba untuk mengubah kata-kata pertanyaan dan juga menaruh beberapa pemikiran baru.$\ell_1$

1. (Yah, ini terlalu tergantung pada algoritma untuk benar-benar memiliki jawaban. Tanpa batasan pada algoritme, Anda dapat memiliki dua kesetimbangan Nash yang berbeda dan kemudian, saat Anda memasukkan lebih kecil dan lebih kecil ke dalam algoritma, jarak antara berturut-turut output masih bisa besar karena output berosilasi antara kesetimbangan.)ℓ $\epsilon$$\ell_1$

2. Misalkan adalah profil strategi, yaitu distribusi produk di atas strategi pemain. Untuk permainan apa kita dapat mengatakan bahwa adalah keseimbangan -Nash menyiratkan untuk beberapa ekuilibrium Nash , di mana sebagai ? (Perhatikan bahwa yang sebaliknya berlaku jika pembayaran dibatasi oleh )p ϵ ‖ p - q ‖ 1 ≤ δ q δ → 0 ϵ → 0 $p$$p$$\epsilon$$\|p - q\|_1 \leq \delta$$q$$\delta \to 0$$\epsilon \to 0$$1$

   Ini sebenarnya rumit karena kita dalam pengaturan kompleksitas yang kita sebut "permainan" sebenarnya adalah urutan permainan yang diparameterisasi oleh , jumlah strategi murni ("aksi"). Jadi sebagai , dan nilai relatifnya penting. Berikut adalah contoh tandingan sederhana untuk menunjukkan jawabannya bukan "semua game". Misalkan kita memperbaiki urutan penurunan . Kemudian untuk setiap , buat gim dua pemain di atas aksi di mana, jika seorang pemain memainkan aksi pertama, mereka mendapat hadiah terlepas dari apa yang dimainkan pemain lain; jika seorang pemain memainkan aksi kedua, mereka mendapatkan hadiahn → ∞ ϵ → 0 ϵ 1 , ϵ 2 , … ϵ n n 1 1 - ϵ n$n$$n \to \infty$$\epsilon \to 0$$\epsilon_1,\epsilon_2,\dots$$\epsilon_n$$n$$1$$1-\epsilon_n$terlepas dari apa yang dimainkan pemain lain; dan jika seorang pemain memainkan tindakan lain, mereka mendapat imbalan terlepas dari apa yang dimainkan pemain lain.$0$

   Dengan demikian setiap game memiliki -equilibrium (keduanya memainkan aksi kedua) yang secara maksimal jauh dalam jarak dari satu-satunya keseimbangan Nash (keduanya memainkan aksi pertama).ϵ n ℓ $n$$\epsilon_n$$\ell_1$

   Jadi, dua pertanyaan menarik:

   1. Untuk permainan tetap dan tetap , apakah untuk "cukup kecil" kondisi di atas berlaku (semua equilibria dekat dengan Nash equilibria).ϵ $n$$\epsilon$$\epsilon$
   2. Mungkin pertanyaan yang sama pada dasarnya, tetapi apakah kondisi tersebut berlaku jika perbedaan dalam hadiah dibatasi oleh konstanta seperti .$n \to \infty$

3. Pertanyaan yang sama seperti (2), tetapi berkaitan dengan keseimbangan aktual yang dihitung oleh algoritma. Saya kira mungkin kita akan mendapatkan jawaban algoritmik / konstruktif atau tidak sama sekali, jadi perbedaannya tidak terlalu menjadi masalah.

Makalah berikut setidaknya memformalkan gagasan tentang ekuilibria perkiraan yang mendekati kesetimbangan yang tepat, dan membuktikan beberapa hasil struktural terkait.

Pranjal Awasthi, Maria-Florina Balcan, Avrim Blum, Or Sheffet, dan Santosh Vempala (2010). Pada Nash, ekuilibria dari game-game aproksimasi-stabil. Dalam Prosiding konferensi internasional ketiga tentang teori permainan Algoritma (SAGT'10), 78-89.

Secara khusus, makalah ini memberikan contoh kelas permainan untuk pertanyaan 3.