Sumber untuk Teori Permainan Evolusi Algoritma

Saya menggunakan istilah judul dalam arti yang sangat longgar.

Ada sejumlah besar pekerjaan pada teori permainan evolusioner, termasuk dasar matematisnya. Saya direkomendasikan "Game Evolusi dan Dinamika Populasi" tetapi belum menggali ke dalamnya.

Ada juga sejumlah besar pekerjaan pada teori permainan algoritmik, yang merupakan topik populer di situs ini.

Yang ingin saya lihat adalah karya yang membuat kompleksitas komputasi atau pernyataan konvergensi tentang dinamika evolusi tertentu.

Contoh (diungkapkan dengan sangat longgar):

1. Mengingat populasi dan skema evolusi, dapatkah kita memberikan batasan penyesalan probabilistik untuk optimalitas populasi jangka panjang (dibandingkan dengan individu yang diproduksi terbaik?). Ini tampaknya sangat terkait dengan ansambel pakar dan masalah bandit. Bagaimana dengan pengaturan non-stasioner?
2. Mengingat seperangkat populasi spesies berbeda yang berinteraksi di lingkungan mereka, memainkan hampir semua jenis permainan multi-pemain, pernyataan apa yang dapat kita buat tentang stabilitas akhirnya dari strategi atau distribusi strategi mereka, mengingat strategi evolusi mereka.
3. Dalam lingkungan apa pun dengan banyak "ceruk" (cara ungkapan yang terlalu luas, saya mengerti), baik dalam hal hubungan langsung dengan lingkungan atau dalam hal hubungan dengan spesies lain, pernyataan apa yang dapat kita buat tentang bagaimana populasi akan mendistribusikan melintasi ceruk ini.
4. Masalah apa pun yang belum saya tanyakan tetapi harus - saya hadapi ini dengan sedikit AGT, TCS, Algoritma Genetika, teori permainan evolusi atau latar belakang biologi populasi; Saya mengajukan pertanyaan saya dari sudut pandang optimasi / pembelajaran mesin / statistik, yang mungkin salah atau tidak lengkap.

Ini adalah salah satu topik di mana saya telah mencari koneksi untuk sementara waktu. Namun, mereka tampaknya tidak lazim. Orang-orang yang bekerja pada teori biologi dan ekonomi yang menggunakan EGT, biasanya tetap berpegang pada teori sistem dinamis dan tidak mengenakan lensa algoritmik. Dengan demikian, sebagian besar hasil adalah gaya AMath / Fisika, dan bukan dari algoritma dan gaya matematika diskrit. Jika Anda ingin mengejar pendekatan sistem dinamis, maka ada survei oleh Hofbauer dan Sigmund yang lebih pendek dan lebih baru dari buku mereka (saya sebutkan dan beberapa komentar yang lewat di jawaban sebelumnya ).

Salah satu dinamika replikator tempat telah digunakan dalam hasil terkait kompleksitas, adalah oleh Marcello Pelillo dan rekan penulis sebagai heuristik untuk memecahkan max-klik (mengurangi max-klik untuk pemrograman kuadratik, memecahkan pemrograman kuadratik dengan menggunakan dinamika replicator sebagai heuristik Anda) :

[1] Immanuel M. Bomze, dan Marcello Pelillo [2000]. "Mendekati Klik Berat Maksimum Menggunakan Dynamics Replicator." Transaksi IEEE di Jaringan Saraf 11 (6)

[2] Marcello Pelillo, dan Andrea Torsello [2006]. "Dynamics Game Hasil-Monotonik dan Masalah Kelompok Maksimum." Perhitungan Saraf 18: 1215-1258.

$\Sigma^P_2$$\Sigma^P_2$

[3] Kousha Etessami, dan Andreas Lochbihler [2008] "Kompleksitas komputasi dari strategi yang stabil secara evolusioner". International Journal of Game Theory , 37 (1): 93-113. (Pertama kali tersedia pada tahun 2004 sebagai laporan teknologi ECCC TR04-055).

[4] Vincent Conitzer [2013] "Kompleksitas komputasi yang tepat dari strategi yang stabil secara evolusioner". Konferensi ke-9 tentang Ekonomi Web dan Internet (WINE) . ( pdf ).

Banyak pertanyaan EGT yang menarik saat ini adalah tentang game pada grafik, dan meskipun ada beberapa hasil sistem dinamis yang keren, seperti (lihat juga pertanyaan ini untuk ekstensi dari pendekatan ini):

[5] Hisashi Ohtsuki, dan Martin Nowak [2006] "Persamaan replikator pada grafik." _ Journal of Theoretical Biology_, 243 (1), 86-97 ( tautan , posting blog )

Sebagian besar pekerjaan melewati pemodelan berbasis agen (lihat jawaban ini untuk konteks pemodelan penyebaran penyakit). Model-model ini biasanya jauh lebih ramah terhadap pernyataan kompleksitas dan konvergensi. Lihatlah buku berikut untuk lebih lanjut:

[6] Yoav Shoham dan Kevin Leyton-Brown [2009], "Sistem multi-agen: algoritmik, teori permainan, dan dasar logis", tekan Universitas Cambridge.

Saya pikir pembelajaran mesin adalah cara yang cukup mudah untuk mendekati EGT, karena itu adalah titik setengah alami antara fisika yang relevan (mekanika statistik) dan ilmu komputer. Ini sudah pasti dilakukan, saya perlu sedikit untuk menemukan referensi yang baik, tetapi referensi acak (yang juga menunjukkan bahwa orang-orang EGT telah mempertimbangkan konsep keseimbangan populer lainnya, seperti kesetimbangan berkorelasi):

[7] Sergiu Hart dan Andreu Mas-Colell [2000], "Prosedur adaptif sederhana yang mengarah ke keseimbangan berkorelasi", Econometrica 68 (5): 1127-1150

[8] Antonella Ianni [2001], "Belajar berkorelasi keseimbangan dalam permainan populasi", Matematika Ilmu Sosial 42 (3): 271-294.

[9] Ludek Cigler dan Boi Faltings [2011], "Mencapai Kesetimbangan yang Berhubungan Melalui Pembelajaran Multi-Agen", AAMAS 2011: 509-516

Saya sungguh berharap orang lain memberikan jawaban yang lebih spesifik, karena ini adalah pertanyaan yang selalu ingin saya ketahui lebih lanjut.

Seperti yang orang lain katakan, ada kurang dari yang Anda harapkan. Beberapa makalah terkait terkait:

"Berat Multiplikatif dalam Permainan Koordinasi dan Teori Evolusi" oleh Chastain, Livnat, Papadimitriou, dan Vazirani. Makalah ini berpendapat bahwa dinamika evolusi (dalam model sederhana) setara dengan permainan koordinasi antara gen yang dimainkan dengan algoritma pembelajaran bobot multiplikatif. Mereka menganalisis varian 2 gen, dalam model yang disederhanakan.

Perhatikan bahwa algoritma bobot multiplikatif adalah dinamika alami yang diketahui konvergen ke kesetimbangan Nash dalam game zero sum, game potensial non-atomik, dan beberapa lainnya (lihat misalnya Freund dan Schapire )

"The Price of Stochastic Anarchy" oleh Chung, Ligett, Pruhs, dan saya sendiri (dari beberapa waktu yang lalu). Di sini kita mempelajari keadaan permainan yang stabil secara stokastik, yang terkait dengan ESS. Kami tidak khawatir tentang kerumitan menemukan mereka, tetapi kami menunjukkan bahwa dalam beberapa permainan, harga anarki lebih rendah daripada set kesetimbangan stabil stokastik dibandingkan dengan kesetimbangan Nash sewenang-wenang.

Saya belajar dari sekolah Ashlock . Keuntungan besar yang saya dapatkan adalah betapa bermanfaatnya untuk mengambil$n^2$ tabel hasil antara agen dan menggunakan K-Means untuk mengelompokkan baris ke dalam kelompok strategi untuk analisis.