Algoritma untuk perhitungan ekuilibrium Nash.

10

Saya mencari di forum untuk melihat apakah ini telah ditanyakan sebelumnya, dan sementara teori permainan algoritmik dibahas, saya tidak dapat menemukan masalah ini ditangani. Saya mencoba mencari tahu apa algoritma yang paling dikenal adalah untuk menghitung perkiraan (strategi campuran) Nash equilibria dalam permainan n-orang yang terbatas. Tentu saja, algoritma ini adalah PPAD. Saya lebih tertarik pada kecepatan / efisiensi daripada akurasi algoritma.

Terima kasih, Philip

ds.algorithms gt.game-theory Philip White
sumber
Kami dapat membantu Anda dengan lebih baik jika Anda memberikan lebih banyak detail. Misalnya berapa nilai yang ada dalam pikiran Anda? Apakah Anda memiliki struktur khusus fungsi pembayaran dalam pikiran? Apakah Anda benar-benar membutuhkan keseimbangan Nash atau apakah keseimbangan berkorelasi sudah mencukupi? Apakah Anda mencari sesuatu dengan batas yang dapat dibuktikan baik atau sesuatu dengan kinerja praktis yang baik? n
Warren Schudy

Jawaban:

7

Jawaban singkatnya adalah bahwa walaupun ada beberapa algoritma waktu polinomial untuk menemukan perkiraan Nash equilibria, mereka semua menemukan perkiraan yang relatif buruk - mungkin tidak cukup baik jika Anda benar-benar mencoba mencari algoritma untuk bermain game. Lebih dikenal untuk 2 game pemain daripada untuk game n pemain.

Jika apa yang Anda coba lakukan sebenarnya menemukan keseimbangan (perkiraan) Nash, satu hal yang mudah untuk dikodekan yang mungkin Anda coba adalah mensimulasikan permainan, dengan masing-masing pemain menggunakan algoritma mayoritas tertimbang acak (http://en.wikipedia.org/ wiki / Randomized_weighted_majority_algorithm). Ini tidak dijamin berfungsi, tetapi dalam banyak kasus akan (Dan dijamin untuk kelas permainan tertentu, seperti game zero-sum). Khususnya, jika proses ini konvergen sama sekali, dijamin akan menyatu dengan kesetimbangan Nash. Bahayanya adalah bahwa ia tidak akan bertemu, dan berputar selamanya - tetapi bahkan dalam kasus ini, sejarah permainan empiris akan menyatu ke set keseimbangan berkorelasi kasar.

Aaron Roth
sumber
Saya mulai melihat kertas yang disebutkan dalam jawaban di atas. Saya tidak mengerti semua itu (atau sebagian besar pada pandangan pertama) ... dapatkah Anda menjelaskan mengapa perkiraannya "relatif buruk?" Juga, dapatkah Anda menjelaskan secara singkat apa itu "keseimbangan berkorelasi kasar"? Saya tahu apa itu keseimbangan berkorelasi, tapi apa artinya persamaan itu. menjadi kasar. Akhirnya, apa yang Anda maksud dengan "sejarah empiris permainan akan bertemu ... [dll]"? Bagaimana mungkin sesuatu yang tidak pernah konvergen bertemu menjadi satu set CCE? Terima kasih atas jawaban Anda, saya mencari artikel Wikipedia sekarang.
Philip White
Untuk beberapa latar belakang tentang algoritma yang menghasilkan distribusi yang menyatu dengan kesetimbangan berkorelasi kasar atau kesetimbangan berkorelasi, saya akan mulai di sini: cs.cmu.edu/~avrim/Papers/regret-chapter.pdf
Aaron Roth
Jika Anda menginginkan keseimbangan berkorelasi daripada kesetimbangan berkorelasi kasar, Anda dapat menggunakan pembelajar tanpa-penyesalan internal. Misalnya (plug tak tahu malu) cs.brown.edu/~ws/papers/regret.pdf . Ada juga algoritma untuk menghitung kesetimbangan berkorelasi langsung dalam waktu polinomial.
Warren Schudy
10

n

Joseph O'Rourke
sumber
4

Jika Anda tertarik pada algoritma yang sebenarnya diimplementasikan dalam perangkat lunak, ada beberapa yang saya ketahui:

  1. paket GAMBIT (http://www.gambit-project.org/doc/index.html) mengimplementasikan beberapa algoritma kesetimbangan Nash untuk bentuk normal 2-pemain & n-pemain, dan dalam beberapa kasus permainan formulir yang luas.

  2. GameTracer (http://dags.stanford.edu/Games/gametracer.html) mengimplementasikan algoritma GNM dan IPA Govindan & Wilson untuk game bentuk normal n-pemain.

  3. Untuk permainan besar, representasi bentuk normal bermasalah karena ukuran tumbuh secara eksponensial dalam jumlah pemain. Alih-alih, jika fungsi utilitas gim Anda memiliki jenis struktur tertentu, Anda dapat menggunakan "representasi ringkas" (misalnya gim grafis, gim simetris, gim aksi-grafik) untuk mengekspresikannya menggunakan lebih sedikit ruang; dan selanjutnya struktur sering dapat dieksploitasi untuk mempercepat komputasi. Dalam hal perangkat lunak, AGG Solver (http://agg.cs.ubc.ca) mengadaptasi algoritma GNM GameTracer dan algoritma simpdiv GAMBIT ke representasi game aksi-grafik (AGG). (Penafian: Saya terlibat dalam pengembangan pacakge perangkat lunak ini.)

albert
sumber