Game wasit dengan koin semi-pribadi yang tidak berkorelasi

Saya (dan masih) sangat tertarik pada jawaban untuk pertanyaan ini, karena ini adalah variasi yang menarik pada kompleksitas permainan yang belum terselesaikan, jadi saya menawarkan hadiah. Saya pikir pertanyaan aslinya kemungkinan besar terlalu sulit, jadi saya memposting tiga pertanyaan terkait yang juga layak untuk hadiah itu. Tidak ada yang memposting jawaban apa pun sebelum hadiah berakhir. Saya kemudian dapat menjawab dua pertanyaan terkait (pertanyaan 3 dan 4, dibahas di bawah posting asli saya), menunjukkan bahwa perkiraan nilai permainan wasit dengan koin semi-pribadi berkorelasi (didefinisikan di bawah) adalah EXPTIME-complete. Pertanyaan asli masih belum terjawab. Saya juga tertarik pada hasil apa pun yang menempatkan game terkait antara PSPACE dan EXPTIME di kelas kompleksitas yang menarik.

POST ASLI:

Pertanyaan ini terinspirasi oleh diskusi tentang pertanyaan hex Itai . Sebuah permainan wasit adalah permainan di mana dua pemain komputasi terbatas bermain dengan berkomunikasi melalui polinomial-waktu verifier yang dapat flip koin pribadi (sehingga jumlah lilitan dan jumlah komunikasi juga polinomial-waktu dibatasi). Di akhir pertandingan, wasit menjalankan algoritme dalam P untuk menentukan siapa yang menang. Menentukan siapa yang memenangkan permainan seperti itu (bahkan kira-kira) adalah EXPTIME lengkap. Jika Anda memiliki koin publik, dan komunikasi publik, game seperti itu ada di PSPACE. ( Lihat Feige dan Killian, "Membuat Game Singkat." ) Pertanyaan saya menyangkut batas antara dua hasil ini.

Pertanyaan: Misalkan Anda memiliki dua pemain yang tidak terikat secara komputasi yang memainkan permainan panjang polinomial. Peran wasit terbatas pada, sebelum setiap gerakan, memberikan masing-masing pemain sejumlah koin privat (tidak berkorelasi dengan pemain lain). Semua gerakan pemain bersifat publik, sehingga terlihat oleh lawannya - satu-satunya informasi pribadi adalah lemparan koin. Di akhir permainan, semua flips koin pribadi terungkap, dan wasit poli-waktu menggunakan flip koin ini dan gerakan pemain untuk memutuskan siapa yang menang.

Dengan hasil pertandingan wasit, kira-kira probabilitas bahwa pemain pertama yang menang ada di EXPTIME, dan itu juga jelas PSPACE-hard. Yang mana (jika ada) itu? Adakah yang diketahui tentang masalah ini?

Perhatikan bahwa para pemain mungkin harus menggunakan strategi campuran, karena Anda dapat memainkan permainan matriks zero-sum (a la von Neumann) dengan cara ini.

BAHAN YANG DITAMBAH:

Sebut saja kelas kompleksitas ini RGUSP (semua bahasa yang dapat direduksi menjadi Permainan Wasit dengan Koin Semiprivat Tidak Berkorelasi seperti dijelaskan di atas, sehingga jika , pemain 1 menang dengan probabilitas , dan jika , pemain 1 menang dengan probabilitas ). Tiga pertanyaan terkait saya adalah: $L$ $x \in L$ $\geq 2/3$ $x \notin L$ $\leq 1/3$

Pertanyaan 2: RGUSP tampaknya cukup kuat. Sebagai contoh, jika kita mengubah permainan sehingga wasit tidak mengirim pesan, tetapi hanya mengamati pesan publik pemain 1 dan 2, dan menerima pesan pribadi darinya, maka perkiraan nilai permainan ini masih setara dengan RGUSP. Saya ingin menunjukkan bahwa RGUSP kuat, jadi saya bersedia memberikan hadiah kepada siapa pun yang menemukan kelas kompleksitas alami C sehingga PSPACE C RGUSP, di mana tak satu pun dari kontennya tampak tepat. $\subseteq$ $\subseteq$
Pertanyaan 3: Saya juga sangat curiga bahwa kelas RGCSP (Refereed Games with Correlated Semiprivate Coins) adalah EXPTIME lengkap, dan saya juga bersedia memberikan hadiah kepada seseorang yang membuktikan fakta ini. Dalam RGCSP, pada langkah pertama, wasit memberi dua pemain variabel acak berkorelasi (misalnya, ia mungkin memberi pemain pertama poin di bidang proyektif besar, dan pemain kedua garis berisi poin ini). Setelah ini, untuk sejumlah putaran polinomial, kedua pemain saling bergantian mengirim pesan publik ukuran-poli. Setelah pertandingan dimainkan, wasit waktu menentukan siapa yang menang. Apa kompleksitas perkiraan probabilitas menang untuk pemain 1?
Pertanyaan 4: Akhirnya, saya memiliki pertanyaan yang mungkin benar-benar mengenai kriptografi dan distribusi probabilitas: Apakah memberikan kemampuan untuk melakukan transfer tanpa sadar kepada dua pemain dalam permainan wasit dengan koin semi-swasta tidak berkorelasi membiarkan mereka memainkan permainan wasit yang sewenang-wenang dengan koin berkorelasi (Atau sebagai alternatif, apakah itu memungkinkan mereka memainkan permainan menentukan pemenang yang lengkap-EXPTIME)?

cc.complexity-theory gt.game-theory interactive-proofs Peter Shor
sumber

Satu pengamatan adalah bahwa wasit hanya perlu memberikan koin acak kepada pemain di awal permainan. Anda dapat menghasilkan koin acak untuk pemain 1 tepat sebelum langkahnya dengan mengambil beberapa koin acak pribadi dari awal permainan dan XOR'ing dengan string disediakan oleh pemain 2. Mudah untuk menunjukkan bahwa pemain 2 tidak dapat melakukan lebih baik daripada memilih secara acak (dalam hal ini XOR juga acak).

r

$r$

s

$s$

s

$s$

s

$s$

r

$r$

Peter Shor

Saya benci ungkapan "setengah pribadi setengah publik". Bagaimana dengan semi privat?

Peter Shor

sebut saja 'facebook private';). Anda pikir itu pribadi, tetapi tidak

Suresh Venkat

Tampak bagi saya bahwa bukti Feige-Kilian tidak dapat dengan mudah diadaptasi untuk menjawab pertanyaan ini.

Peter Shor

Saya pikir Magic: The Gathering (dan mungkin permainan kartu lainnya yang dapat dikoleksi) adalah contoh sempurna dari jenis permainan wasit yang lebih lemah ini. Saya tidak bermain Magic, tetapi masing-masing pemain memiliki setumpuk, dan para pemain mulai dengan mengocok dek mereka sendiri, sehingga semua keacakan tidak berkorelasi.

Peter Shor

Jawaban:

Saya tidak dapat menjawab pertanyaan asli saya, tetapi saya dapat menjawab pertanyaan 3 (dan 4), yang saya tambahkan ketika saya menawarkan hadiah karena saya pikir pertanyaan aslinya kemungkinan terlalu sulit. Sebenarnya, saya punya dua bukti pertanyaan 3.

Berikut pengaturan untuk pertanyaan 3: Kami memiliki wasit waktu-polinomial yang, pada awal permainan, memberikan pemain 1 dan 2 variabel acak berkorelasi. Pemain 1 dan 2 kemudian memainkan permainan, tanpa ada gangguan dari wasit. Di akhir pertandingan, wasit memeriksa transkrip dan memutuskan siapa yang menang. Saya dapat menunjukkan bahwa memutuskan siapa yang memenangkan permainan seperti itu EXPTIME lengkap, bahkan jika Anda diberi janji bahwa pemenang menang dengan probabilitas setidaknya . $2/3$

======== Bukti 1 ============

Bukti pertama menggunakan fakta bahwa transfer yang tidak disadari bersifat universal untuk perhitungan dua pihak yang aman. Dengan demikian, jika pemain 1 dan 2 dapat melakukan transfer secara tidak sadar, mereka dapat mensimulasikan wasit polinomial waktu sewenang-wenang, sehingga hasil sebelumnya bahwa permainan wasit yang lengkap EXPTIME dapat diterapkan.

Sekarang, untuk mencapai 1-2 transfer tanpa disadari, pada awal pertandingan, wasit memberi kedua pemain sejumlah besar "kotak transfer yang tidak disadari." Kami menggambarkan salah satu kotak transfer yang tidak disadari ini. P1 mendapat dua angka acak, dan . P2 mendapatkan salah satu dari angka acak ini, dan variabel ( atau ) yang mengatakan dari nomor acak P1 mana yang ia dapatkan. Untuk melakukan transfer yang tidak sadar, P1 mengambil dua bagian data yang ingin ditransfer, dan XOR dengan dan $r_1$ $r_2$ $r_i$ $i$ $=1$ $2$ $r_1$ $r_2$ . P2 kemudian dapat mendekode salah satu dari ini, tetapi P1 tidak dapat menentukan mana yang P2 dapat memecahkan kode. Ini 1-2 transfer yang tidak disadari. (Jelas, wasit juga harus memberi para pemain kotak transfer yang tidak disadari diarahkan ke arah lain, dari P2 ke P1.)

Ketika saya pertama kali mengajukan pertanyaan 4, saya khawatir bahwa hasil perhitungan dua pihak yang aman tidak berlaku untuk perhitungan interaktif semacam ini dengan wasit, tetapi sebenarnya cukup mudah untuk menunjukkan bahwa mereka melakukannya.

=========== Bukti 2 ===========

Sekarang untuk bukti kedua untuk pertanyaan 3. Di sini, kita perlu kembali dan memodifikasi bukti Feige-Kilian. Dalam bukti ini, mereka menganggap mesin Turing T yang menjalankan perhitungan waktu eksponensial. Feige dan Kilian menyandikan bit pada pita pada waktu dalam polinomial x_1 x_n atas bidang terbatas GF ( ). Sekarang, wasit memberikan poin ke P1 dan garis yang berisi poin ini ke P2, dan kedua pemain memberikan evaluasi poin dan garis di kembali ke wasit. Wasit menggunakan pencarian biner untuk menemukan waktu mana evaluasi P1 dan P2 untuk $2^n$ $t$ $Q_t($ $, \ldots,$ $)$ $p$ $Q_t$ $t$ $Q_t$ setuju, tetapi evaluasi mereka terhadap tidak setuju, setelah itu ia mengajukan pertanyaan pintar kepada P1 yang akan mengungkapkan apakah dia orang yang berbohong. $Q_{t+1}$

Hal pertama yang akan kita gunakan adalah bahwa, bahkan dengan koin acak yang tidak berkorelasi, wasit dapat membuat pemain 1 dan 2 melakukan komitmen bit, dengan meminta mereka XOR data yang ingin mereka komit dengan koin acak. Dengan demikian, kita dapat berbicara tentang P1 dan P2 memasukkan benda ke dalam amplop tertutup.

Satu hal yang Anda coba untuk mensimulasikan bukti Feige-Kilian adalah: wasit memberi P1 banyak poin berbeda , dan P2 banyak garis , sehingga ada di . Sekarang, pada setiap langkah pencarian biner, para pemain meletakkan nilai dan ke dalam amplop tertutup, dan kemudian wasit memilih satu secara acak agar pemain dapat membuka. Kedua pemain memutuskan apakah nilainya konsisten, dan melanjutkan dengan pencarian biner yang sesuai. Sekarang, kami telah merusak pasangan , karena kedua pemain mengetahui nilai titik dan garis, tetapi kami masih memiliki banyak pasangan (titik, garis) yang dapat kami gunakan. $p_i$ $\ell_i$ $p_i$ $\ell_i$ $Q_{t}(p_i)$ $Q_t(\ell_i)$ $(p_i, \ell_i)$

(Bagaimana wasit dapat memilih satu secara acak jika dia memberikan instruksi kepada pemain hanya di awal permainan? Dia dapat menyandikan instruksinya dalam nilai-nilai XOR yang dia berikan kepada dua pemain di awal, dan dua pemain tidak dapat membaca instruksi sampai mereka berdua mengungkapkan nilainya pada waktu yang relevan.) $(p_i, \ell_i)$

Strategi ini tidak begitu berhasil, karena P1 dan P2 tidak harus konsisten tentang waktu di mana mereka mulai berbohong dengan dua poin (atau garis) Yaitu, P1 dapat membiarkan memberikan nilai yang tepat untuk dan nilai yang salah untuk . Ini benar-benar akan mengacaukan pencarian biner, dan membuat protokol tidak meyakinkan. Namun, ada trik rapi yang bisa kita gunakan untuk memaksa P1 agar konsisten. Tambahkan sekelompok titik dummy ke set poin P1, dan tambahkan garis dummy $Q_t(p_i)$ $Q_t(p_j)$ ${p}'_k$ ${\ell}'_k$ ke set garis P2. Biarkan setiap baris boneka memiliki dua poin di atasnya. Jika P1 memberikan nilai yang tepat untuk satu titik dummy pada suatu garis dan nilai yang salah untuk titik dummy lainnya, maka ia telah mengungkapkan dirinya sebagai pembohong, karena tidak ada cara bagi P2 untuk memberikan nilai untuk garis yang mengoreksi salah satu dari dua poin P1 di atasnya dan bukan yang lain. Kita dapat melakukan trik serupa untuk membuat jawaban P2 konsisten. Maka satu-satunya yang tersisa adalah menunjukkan bahwa langkah terakhir dari bukti Feige-Kilian masih berfungsi. Ini ternyata mudah, meskipun melalui perincian akan membuat jawaban ini lebih lama.

Peter Shor
sumber