Keseimbangan dalam Game yang Menghentikan

10

Pertimbangkan permainan 2-pemain berikut:

  • Alam secara acak memilih program
  • Setiap pemain memainkan angka dalam [0, tak terbatas] inklusif sebagai respons terhadap gerakan alam
  • Ambil jumlah minimum pemain, dan jalankan program untuk (hingga) banyak langkah (kecuali kedua pemain memilih angka tak terbatas)
  • Jika program terhenti, pemain yang memainkan angka minimum memperoleh 1 poin. Jika program tidak berhenti, pemain itu kehilangan 1 poin. Setiap pemain yang memainkan angka non-minimum menerima 0 poin, dan kedua pemain menerima 0 jika keduanya bermain tanpa batas.

(Kasus sudut dapat ditangani dengan cara apa pun yang terbaik menjaga semangat masalah - misalnya semikontinuitas atas dapat membantu.)

Pertanyaannya: apakah game ini memiliki keseimbangan Nash yang dapat dihitung?

Tanpa persyaratan komputabilitas, setiap pemain hanya memainkan jumlah langkah yang tepat di mana program berhenti (atau tak terbatas, jika tidak berhenti).

Jika Anda mencoba argumen diagonalisasi biasa untuk masalah penghentian, Anda akan menemukan bahwa keseimbangan ada dalam strategi campuran, sehingga pendekatan yang jelas tidak segera bekerja. Mungkin ada beberapa cara untuk mengubahnya?

Di sisi lain, kesetaraan bidang tertutup nyata berarti bahwa permainan terbatas dengan imbalan yang dapat dihitung memiliki keseimbangan yang dapat dihitung . Game ini tidak terbatas, tetapi ruang strategi ditutup dan imbalannya dapat dihitung, jadi mungkin trik yang sama dapat diterapkan dengan Teorema Glicksberg atau sesuatu dalam nada itu? Masalahnya adalah, tanpa persyaratan komputabilitas, keseimbangan berada dalam strategi murni, sehingga setiap upaya untuk membuktikan keberadaan keseimbangan yang dapat dihitung dengan menggunakan keberadaan keseimbangan yang mungkin dapat dihitung harus menjelaskan mengapa keseimbangan diturunkan dari murni menjadi campuran.

Ini sepertinya adalah jenis masalah di mana orang mungkin tidak pernah menjawab pertanyaan yang tepat ini sebelumnya, tetapi mungkin telah melihat sesuatu yang serupa. Saya belum bisa muncul banyak, tetapi jika ada yang tahu sesuatu dalam roh, tolong beri tahu saya!

Motivasi: ada intuisi umum bahwa referensi-diri adalah blok utama untuk kemampuan komputasi - yaitu, bahwa setiap masalah yang tidak dapat dihitung entah bagaimana menanamkan referensi-diri. Jika permainan yang kira-kira seperti ini memiliki keseimbangan Nash yang dapat dihitung, itu akan memberikan bukti untuk intuisi itu.

UPDATE: Untuk memperjelas, keseimbangan harus "dapat dihitung" dalam arti bilangan real yang dapat dihitung: probabilitas yang menggambarkan distribusi strategi campuran harus dapat dihitung dengan presisi yang sewenang-wenang. (Catat bahwa hanya banyak probabilitas secara pasti akan berada di atas batas presisi tertentu). Ini juga berarti bahwa kita dapat mengambil sampel dari pendekatan yang mendekati sewenang-wenang dari strategi ekuilibrium.

lo.logic computability gt.game-theory John Wentworth
sumber
Apakah pembaruan Anda juga menganggap permainan sebagai bilangan real yang dapat dihitung? (yaitu, dapat mereka memainkan nomor dengan probabilitas 1 tanpa mengetahui apakah-atau-tidak nomor adalah tak terhingga?)
Apakah kita diizinkan untuk mengetahui distribusi lawan?
Bjørn Kjos-Hanssen
Ricky: permainan dapat dianggap sebagai real yang dapat dihitung, tetapi memotong ke bilangan bulat harus mendominasi permainan terbatas yang bukan bilangan bulat, karena program hanya akan berjalan untuk sejumlah langkah bilangan bulat (atau tak terbatas). Saya tidak yakin saya mengerti contoh yang ditulis dalam tanda kurung, jadi saya mungkin salah mengerti pertanyaan Anda.
John Wentworth
Bjørn: Ya. Asumsikan distribusi sifat diketahui dan menempatkan bobot bukan nol pada semua program yang valid. Juga asumsikan bahwa setiap pemain mengetahui strategi pemain lain (yaitu distribusi).
John Wentworth
@johnwentworth, gunakan @ atau mereka tidak dapat melihat respons Anda.
rus9384

Jawaban:

11

1/2sayasayatjtjjt

Lance Fortnow
sumber
Saya suka konstruksi ini - ini menetapkan bahwa setiap keseimbangan Nash harus diputar dengan benar untuk semua program. Ada langkah tambahan yang diperlukan untuk menetapkan bahwa ini memecahkan masalah penghentian, karena distribusi hanya perlu menyatu ke kinerja sempurna dalam batas presisi tinggi (dan dengan demikian perhitungan tak terbatas). Karena kita tahu output harus meletakkan satuan berat pada satu bilangan bulat, saya pikir itu cukup untuk menghitung probabilitas strategi menjadi dalam 1/4 dan kemudian mengambil bilangan bulat mana pun yang memiliki bobot lebih besar dari 1/2.
John Wentworth