Pertanyaan teoritis terkait dengan Ilmu Komputer dan Teori Game
Ada justifikasi filosofis yang sering dikutip untuk meyakini bahwa P! = NP bahkan tanpa bukti. Kelas kompleksitas lainnya memiliki bukti bahwa mereka berbeda, karena jika tidak, akan ada konsekuensi "mengejutkan" (seperti runtuhnya hierarki polinomial). Pertanyaan saya adalah, apa dasar untuk...
Memutuskan apakah formula boolean yang dikuantifikasi seperti ∀x1∃x2∀x3⋯∃xnφ(x1,x2,…,xn),∀x1∃x2∀x3⋯∃xnφ(x1,x2,…,xn),\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n), selalu mengevaluasi benar adalah masalah PSPACE-lengkap klasik. Ini dapat dilihat sebagai...
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...
Beberapa bulan terakhir saya mulai memberi kuliah tentang pilihan sosial, teorema panah dan hasil terkait. Setelah membaca tentang hasil mani, saya bertanya pada diri sendiri tentang apa yang terjadi dengan preferensi urutan parsial, jawabannya ada di koran Pini et al. : Menggabungkan preferensi...
Ini adalah pernyataan kembali dari pertanyaan sebelumnya . Pertimbangkan permainan informasi sempurna yang tidak memihak antara dua pemain, Alice dan Bob. Para pemain diberi permutasi bilangan bulat 1 sampai n. Di setiap belokan, jika permutasi saat ini meningkat, pemain saat ini kalah dan pemain...
Pertanyaan teori permainan baru-baru ini membuat saya berpikir (ini bersinggungan, tentu saja): Apakah mungkin untuk secara efisien mengoptimalkan strategi pribadi untuk memilih pertanyaan penelitian untuk dikerjakan menggunakan teori permainan? Untuk menuju formalisasi pertanyaan, saya akan...
Mafia adalah permainan permainan peran yang populer di pesta-pesta, deskripsi terperinci tersedia di wikipedia http://en.wikipedia.org/wiki/Mafia_%28game%29 . Pada dasarnya, ini berfungsi sebagai berikut: Pada awalnya, masing-masing pemain NNN diam-diam diberi peran, baik selaras dengan Mafia...
Saya mencari contoh teknik untuk membuktikan harga batas anarki yang memiliki kekuatan untuk memisahkan harga anarki atas keseimbangan berkorelasi kasar (rangkaian pembatas dinamika tanpa penyesalan eksternal) dari harga anarki atas kesetimbangan berkorelasi (pembatas set dinamika...
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 populer di pesta liburan di Amerika Utara adalah pertukaran hadiah gajah putih . Secara singkat (mengabaikan variasi) berfungsi sebagai berikut: Ada orang dan n hadiah yang belum dibuka. Pemain dipesan secara sewenang-wenang. Di babak , pemain jugannnnnn
Apa jenis dugaan dan masalah terbuka utama yang paling penting dalam teori permainan algoritmik (atau teori permainan secara umum yang berkaitan dengan CS)? Sebagai contoh, resolusi NASH sebagai PPAD-lengkap akan, saya pikir, telah menjadi yang terbesar hingga diselesaikan. (Ditambahkan:...
Sebagai seorang mahasiswa ilmu komputer, saya telah diperkenalkan dengan teori permainan, tetapi tidak melihat banyak detail pada subjek. Saya telah mencari di Google dan melihat beberapa buku tentang teori permainan dan mereka memberikan konfirmasi penggunaannya dalam ilmu komputer. Saya telah...
Saya bertanya-tanya apakah ada versi yang dibatasi secara komputasional dari konsep keseimbangan Nash, sesuatu di sepanjang baris berikut. Bayangkan beberapa jenis dua pemain game informasi yang sempurna yang dimainkan pada papan, dan yang kompleks dalam arti bahwa bermain optimal adalah...
Saya mengalami permainan berikut. Saya akan memigrasi ini seperti yang diminta. Bug sedang mengunjungi lingkaran, dan musuh ingin memaksimalkan waktu perjalanannya. Musuh menempatkan lingkaran di setiap belokan. Bug berjalan dari posisi saat ini langsung menuju pusat lingkaran terbaru, lalu...
Pertimbangkan permainan berikut pada grafik tertimbang GGG diarahkan dengan chip di beberapa node. Semua node GGG ditandai dengan A atau B. Ada dua pemain, Alice dan Bob. Tujuan dari Alice (Bob) adalah untuk menggeser chip ke node yang ditandai oleh A (B). Awalnya Alice dan Bob memiliki...
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
Ada konstruksi yang sangat bagus oleh Conway angka surealis. Mereka adalah "angka" yang berisi bilangan real dan tata cara, benar-benar dipesan, dan memiliki semua properti bidang (kecuali mereka tidak membentuk himpunan tetapi kelas). Lihat misalnya pdf atau Wikipedia ini untuk pengantar. Mereka...
Untuk masalah pencarian lokal polinomial , kita tahu bahwa setidaknya ada satu solusi (lokal optimal) harus ada. Namun, banyak lagi solusi yang bisa ada, seberapa sulitkah menghitung jumlah solusi untuk masalah lengkap PLS? Saya terutama tertarik pada masalah keputusan: apakah contoh masalah...
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...
Seperti yang disebutkan @Marzio, game berikut ini dikenal sebagai Generalized Geography . Diberikan grafik dan simpul awal v ∈ V , permainan didefinisikan sebagai berikut:G = ( V, E)G=(V,E)G=(V,E)v ∈ Vv∈Vv \in V Di setiap belokan (dua pemain bergantian), seorang pemain memilih , dan kemudian...