Kompleksitas permainan informasi parsial-negara terbatas

Diberikan permainan zero-sum informasi-informasi parsial deterministik dengan hanya banyak negara bagian,
yang kemungkinan hasilnya adalah [kalah, seri, menang] masing-masing dengan nilai [-1,0, + 1],
apa kompleksitas perkiraan nilai tersebut sebuah game secara aditif dalam ?$\epsilon$

Secara khusus, saya tidak dapat menemukan algoritma apa pun untuk melakukan itu.
Sisa dari pos ini dikhususkan sepenuhnya untuk memberikan uraian
masalah yang lebih menyeluruh , jadi jika Anda sudah dapat mencari tahu apa arti pertanyaan di bagian atas
pos ini, maka tidak ada alasan bagi Anda untuk membaca sisa pos ini.

Diberikan mesin wasit dengan status , dengan status awal yang ditentukan , status yang pasangan skornya , state yang skor pasangannya adalah , dan status formulirs 0 s a [ - 1 , + 1 ] s b [ + 1 , - 1 $\{1,2,3,...,S\}$$s_0$$s_a$$[-1,+1]$$s_b$$[+1,-1]$

$[\mbox{p1_info,p2_info,num_of_choices,player_to_move,next_state_table}]$ mana:

• $\mbox{player_to_move} \in \{1,2\}$
• $\mbox{next_state_table}$ adalah fungsi dari$\{1,2,3,...,\mbox{num_of_choices}\} \to \{1,2,3,...,S\}$
• $\mbox{p1_info},\mbox{p2_info}, \mbox{num_of_choices} \geq 1$

Ketika mesin dalam kondisi seperti itu:

• mengirim ke Player_1 dan mengirim ke Player_2,$\mbox{p1_info}$$\mbox{p2_info}$
• mengirimkan ke pemain yang ditunjukkan, menunggu elemen sebagai masukan dari pemain itu,$\mbox{num_of_choices}$$\{1,2,3,...,\mbox{num_of_choices}\}$
• kemudian pergi ke keadaan yang ditunjukkan oleh$\mbox{next_state_table}$

Ketika mesin memasuki salah satu dari dua negara lainnya atau ,$s_a$$s_b$

• berhenti dengan pasangan skor negara bagian itu sebagai hasilnya

Ada permainan dua pemain alami: mesin wasit dimulai dalam keadaan , pemain memberikan input yang oleh mesin wasit, jika mesin wasit berhenti maka Player 1 mencetak nilai pertama dari pasangan output mesin dan Pemain 2 mencetak nilai kedua dari pasangan keluaran mesin, jika tidak, kedua pemain mencetak skor 0. $s_0 = 1$

Apa kompleksitas dari masalah berikut ini?
Diberikan mesin wasit dan bilangan bulat positif N, menghasilkan bilangan rasional
yang (tambahnya) dalam 1 / N dari nilai permainan alami untuk Player 1.

Seperti yang disebutkan sebelumnya dalam pertanyaan ini, saya tidak dapat menemukan
algoritma apa pun untuk melakukan itu.

CATATAN: algoritme yang saya anggap salah; Saya menghapusnya.

Satu hal yang perlu disadari adalah bahwa tidak masalah apakah permainan itu deterministik atau tidak. Untuk mengacak, wasit dapat meminta setiap pemain untuk berkontribusi acak nomor mod , dan kemudian menambahkan mereka. Sangat mudah untuk menunjukkan bahwa jika para pemain menggunakan strategi optimal mereka, jumlahnya adalah angka acak mod , yang kemudian dapat digunakan wasit untuk mengacak strateginya. Ini tidak terlalu meningkatkan jumlah status dalam game.$p$$p$

Untuk batas bawah pada kompleksitas, pertanyaan mendekati nilai dari permainan stochastic sederhana yang tidak diketahui berada di P . Menggunakan trik pengacakan yang saya berikan di atas, mudah untuk menulis permainan stokastik sederhana sebagai permainan wasit dengan tabel pencarian ukuran polinomial.

Dengan Teorema 3.1 dan IPS bukti ini menjadi satu arah,
untuk semua bilangan real , jika maka masalah janji$\epsilon$$0<\epsilon$

Input: permainan seperti yang dijelaskan dalam pertanyaan saya
harus menampilkan YA jika: nilai permainan untuk Pemain 1 lebih besar dari 1- harus menghasilkan TIDAK jika: permainan nilai untuk Player 1 kurang dari$\hspace{.025 in}\epsilon$
$\epsilon$

tetap RE -hard bahkan ketika

player_to_move selalu 1 (yaitu, hanya 1 pemain yang dibutuhkan)
dan
s ₀ ≠ s _sebuah dan s _suatu tidak dalam Range (next_state_table)
(yaitu, secara harfiah tidak mungkin bagi pemain untuk kehilangan)
dan
p1_info dan p2_info dan number_of_choices independen dari negara
(yaitu, satu- satunya umpan balik pemain adalah apakah ia baru saja menang)

.