Dugaan luar biasa dan masalah terbuka dalam teori permainan (algoritmik)?

14

Apa jenis dugaan dan masalah terbuka utama yang paling penting dalam teori permainan algoritmik (atau teori permainan secara umum yang berkaitan dengan CS)? Sebagai contoh, resolusi NASH sebagai PPAD-lengkap akan, saya pikir, telah menjadi yang terbesar hingga diselesaikan.

(Ditambahkan: menyelesaikan hubungan PPAD dengan P dan NP adalah salah satu masalah terbuka yang baik, tetapi yang lain yang tidak terlalu mengakar dalam kompleksitas komputasi akan menyenangkan juga.)

big-list gt.game-theory daveagp
sumber
3
Pertanyaan ini akan bekerja lebih baik jika Anda menandainya sebagai CW (Komunitas Wiki). Lihat di sini: meta.cstheory.stackexchange.com/questions/225/…
Daniel Apon
2
Saya setuju. tandai saja CW.
Suresh Venkat

Jawaban:

5

Berikut ini beberapa masalah terbuka:

Masalah terbuka 1-Mayor adalah masalah perhitungan perkiraan Nash equilibria.

2- Adanya algoritma yang efisien untuk menghitung kesetimbangan Nash murni dalam game kemacetan?

Kesetimbangan 3-temuan dengan inefisiensi minimum?

4-Tim Roughgarden, dalam Communications of ACM, mengajukan masalah terbuka berikut:

Sejauh mana perhitungan efisien “kompatibel dengan insentif” pada dasarnya kurang kuat dari perhitungan efisien “klasik”?

Teori permainan algoritmik, Komunikasi ACM, Volume 53, Edisi 7, (Juli 2010)

Referensi ini juga mengandung beberapa masalah terbuka: Nisan, Roughgarden, Tardos, dan Vazirani, editor. Teori Permainan Algoritma. Cambridge University Press, 2007.

T. Roughgarden. Teori permainan algoritma: Beberapa hit terbesar dan arah masa depan. Dalam TCS '08, hal. 21–42.

Mohammad Al-Turkistany
sumber
Survei terbaru ini sangat membantu. Saya sebenarnya telah melihat buku Nisan +++ --- pencarian teks untuk "dugaan" hanya memberikan beberapa hit! --- tapi memang ada banyak masalah terbuka. Dugaan spesifik apa pun, atau masalah terbuka teknis yang kurang spesifik, akan tetap disambut dalam pencarian saya.
daveagp
Menghitung ekuilibrium Nash murni dari permainan kemacetan umum adalah lengkap-PLS, sehingga algoritma yang efisien tidak mungkin ada.
Rahul Savani
1

Dalam referensi ini, Papadimitriou dan Roughgarden menimbulkan 6 masalah terbuka terkait dengan komputasi berkorelasi kesetimbangan:

Papadimitriou dan Tim Roughgarden, Computing Equilibria yang Berhubungan dalam Game Multi-Pemain

Juga, dalam makalah ini Papadimitriou mengajukan beberapa masalah terbuka terkait dengan Teori Permainan dan Internet:

Papadimitriou, Algoritma, Game, dan Internet, Proc. STOC 2001

Mohammad Al-Turkistany
sumber
2
Survei Papadimitriou agak ketinggalan jaman, karena kemajuan signifikan telah dibuat pada sebagian besar masalah terbuka sejak 2001.
Ryan Williams