Teori permainan algoritma - konsep kesetimbangan yang tidak standar?

Saya memulai studi saya tentang teori permainan algoritmik, dan tampaknya konsep keseimbangan yang biasanya diambil adalah titik tetap dalam grafik. Namun, sudahkah orang melihat konsep keseimbangan alternatif, seperti siklus batas? Saya dapat membayangkan bahwa siklus batas "ketat" - yaitu, siklus dalam grafik yang sangat kecil - dapat dianggap sesuatu yang "dekat" dengan definisi standar keseimbangan.

Saya sudah mencoba menggali di sekitar Google Cendekia, tetapi tidak berhasil.

Salah satu yang saya sukai kadang-kadang disebut "Coarse Correlated Equilibrium". Ini sebenarnya adalah rangkaian terbatas dari dinamika "Tanpa Penyesalan" yang efisien.

Ini memiliki beberapa sifat yang bagus, tak terkecuali bahwa ia dapat dicapai dengan dinamika yang efisien dan tidak berpasangan, dan memasukkan Nash equilibria sebagai kasus khusus (sehingga "sangat ketat lebih masuk akal" sebagai prediksi perilaku). Apa yang mungkin membuat mereka agak mirip dengan apa yang Anda tanyakan, adalah bahwa dinamika pembelajaran ini tidak perlu menyatu ke titik yang sudah pasti - memang, mereka mungkin berputar selamanya. Namun demikian, sering kali mungkin untuk mengikat konvergensi cepat kesejahteraan sosial di bawah dinamika ini (yaitu harga anarki atas kesetimbangan berkorelasi kasar), dan terlebih lagi, seringkali kesejahteraan sosial tidak lebih buruk daripada kesetimbangan berkorelasi kasar daripada terhadap kesetimbangan Nash.

Beberapa makalah yang relevan:

http://portal.acm.org/citation.cfm?id=1374430

http://portal.acm.org/citation.cfm?id=1536414.1536485

http://portal.acm.org/citation.cfm?id=1536487

Anda mungkin mencari sesuatu seperti Sink Equilibria (mulai dari mis. Http://arxiv.org/abs/0902.0382 ) - tetapi panjang siklus tidak dipertimbangkan.

Ini mungkin bukan yang Anda cari, tetapi dimungkinkan untuk menentukan ekuilibrium Nash perkiraan di mana tujuannya adalah untuk menemukan status sehingga utilitas pemain mendekati yang ditentukan oleh equlibrium Nash. Noam Nisan memiliki posting yang bagus tentang ini (dan karena dia kadang-kadang datang ke sini, dia mungkin akan memiliki jawaban yang lebih baik untukmu).

Joseph Y. Halpern dari Cornell baru-baru ini memberikan ceramah di Pusat Pascasarjana CUNY dengan judul: Melampaui Nash Equilibrium: Konsep Solusi untuk Abad ke-21. Mungkin karyanya akan menarik bagi Anda.

http://web.cs.gc.cuny.edu/~kgb/seminar.html

Mudah-mudahan ini tidak terlalu di luar topik jawaban, karena melihat pertanyaan ini dari sudut teori permainan evolusioner (EGT), bukan AGT.

Teori permainan seperti yang awalnya dirumuskan oleh von Neumann dan Morgenstern adalah teori statis. Karenanya, banyak konsep keseimbangan populer (Nash, Correlated, dll) pada dasarnya statis. Untuk berbicara tentang keseimbangan non-statis, kita harus memperkenalkan semacam dinamika. AGT sering melakukan ini dengan mempertimbangkan agen penalaran (algoritma) tertentu yang mungkin digunakan untuk sampai pada keputusan mereka.

Pendekatan alternatif, dan yang dianut oleh EGT, adalah mempertimbangkan dinamika populasi sejumlah besar agen dengan pengambilan keputusan yang sangat sederhana. Ini biasanya menciptakan dinamika non-linear dalam populasi dan menempatkan EGT sebagai bagian dari sistem dinamis. Oleh karena itu, Anda mulai melihat semua konsep keseimbangan gila sistem dinamis seperti siklus batas atau penarik kacau yang muncul sebagai konsep keseimbangan. Kesetimbangan non-stasioner ini dipelajari dengan baik dalam EGT, meskipun seringkali analisisnya murni dari sistem yang dinamis dan tidak algoritmik.

Jika Anda tertarik dengan EGT, maka titik awal standar (dan dapat diakses) adalah survei Hofbauer dan Sigmund 2003 " Evolutionary game dynamics "