Seberapa keraskah Mafia?

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 $N$ diam-diam diberi peran, baik selaras dengan Mafia atau dengan Kota. Setiap peran mungkin memiliki kemampuan khusus; lebih lanjut tentang itu nanti.
Ada dua fase permainan: Siang dan Malam. Di Malam Hari, Mafia dapat berkomunikasi secara diam-diam satu sama lain; dan mereka mungkin menyetujui satu pemain target yang mereka bunuh malam itu. Pada Hari, semua pemain (hidup) berkomunikasi dalam forum terbuka. Para pemain dapat menyetujui untuk memilih satu pemain, mayoritas mutlak dari semua pemain diperlukan.
Permainan berakhir jika hanya ada Mafia yang tersisa, atau hanya ada Town yang tersisa. Partai yang selamat menang.
Mari kita asumsikan ada tiga peran: Warga Negara, Penyelidik, dan Mafioso. Warga tidak memiliki kekuatan. Mafiosi juga tidak memiliki kemampuan selain dapat berkomunikasi satu sama lain di malam hari dan memberikan suara untuk satu korban pembunuhan setiap malam. Investigator dapat menyelidiki satu pemain lain di setiap malam, mencari tahu peran mereka yang sebenarnya.
Asumsikan permainan dimulai pada hari itu, dan bahwa peran seorang pemain diungkapkan pada saat kematian

Strategi kemenangan

Mengingat setup $(i,c,m)$ dari $i$ Penyidik, $c$ Citizen, dan $m$ Mafiosi, kita mengatakan bahwa setup yang menang untuk Town , jika ada strategi untuk pemain Town, sehingga mereka menang, tidak peduli bagaimana Drama mafia.

Perhatikan bahwa kami dapat mengasumsikan bahwa Mafia bermain dengan informasi lengkap, karena kami ingin memperhitungkan setiap keputusan yang dapat mereka ambil.

Contoh: Pengaturan $(4,1,1)$ menang untuk Town.

Hari 1: Semua pemain Kota dengan jujur melaporkan peran mereka dalam obrolan terbuka. Pemain Mafia harus mengklaim sebagai Penyidik atau Warga Negara.

Jika dia mengklaim warga negara, maka Mafioso adalah salah satu dari dua warga negara yang dituduhkan. Setiap Penyelidik dapat menginvestigasi salah satu dari mereka, dan akan menemukan yang benar. Paling-paling satu Penyidik bisa mati di malam hari, dan dua lainnya hanya menggantung Mafioso.

Karena itu, Mafioso harus mengklaim Penyidik. Ada 5 dugaan Penyelidik. Dalam obrolan terbuka, Penyelidik menyetujui permutasi untuk saling memeriksa.

Malam 1: Penyelidik memeriksa target mereka, dan Mafioso membunuh satu.

Hari 2: Ada 3 simpatisan yang tersisa. Semua tersangka Penyidik melaporkan temuan mereka. Tidak peduli siapa yang terbunuh, setidaknya satu dari mereka juga dikonfirmasi oleh Penyelidik lain yang masih hidup. Karena Mafioso mengklaim Penyidik, dia juga perlu mengatakan apakah target yang ditugaskan adalah Mafia atau tidak. Jika dia membingkai seseorang, maka Town tahu bahwa dia, atau yang dibingkai adalah Mafia, terhadap 3 Town lainnya yang dikonfirmasi. Jika dia tidak menjebak siapa pun, juga akan ada 3 Kota yang dikonfirmasi. Either way, tidak menggantung siapa pun, dan menyelidiki hanya 2 tersangka yang menang untuk Town.

Pertanyaan

Seberapa sulit untuk memutuskan apakah pengaturan yang diberikan mengakui strategi kemenangan untuk Town? Secara intuitif, suara ini seperti -Lengkap masalah. Adakah yang bisa membuat pengurangan? $PSPACE$
Bisakah kita menemukan pengaturan kemenangan minimal? Seperti dalam bisakah kita meminimalkan rasio atau ? $i:m$ $(i+c):m$

cc.complexity-theory gt.game-theory combinatorial-game-theory Syzygy
sumber

Apakah identitas terungkap saat kematian?

Piotr Migdal

Oh, ya mereka, saya lupa menyebutkan.

Syzygy

Menarik. Saya memainkan versi game ini di mana identitas tidak terungkap pada saat kematian. Jadikan lebih banyak tentang menyusun cerita yang bisa dipercaya dan deteksi kebohongan.

Lucas Cook

m

$m$

@LucasCook Ya, lihat arxiv.org/abs/1009.1031 (makalah saya tentang game Mafia). Dalam sebuah permainan ketika dua pemain dapat terbunuh dalam satu giliran, paritas dari jumlah total pemain itu penting. Namun, efeknya tergantung pada aturan yang tepat (misalnya jika hukuman mati tanpa pengadilan adalah opsional atau tidak); dan mungkin tidak muncul dalam skenario non-probabilistik (mis. pertanyaan tentang strategi menang, bukan - pada probabilitas menang).

Piotr Migdal

Jawaban:

Berikut adalah referensi yang ingin Anda lihat: http://www.jstor.org/stable/10.2307/25442651

Mafia: Studi teoritis pemain dan koalisi di lingkungan informasi parsial Braverman, M. dan Etesami, O. dan Mossel, E. The Annals of Applied Probability 2008

Aaron Roth
sumber

Saya tidak menyadari bahwa masalahnya sudah dipelajari. Seandainya saya tahu ini ketika saya bermain Mafia :)

Suresh Venkat

Terima kasih, saya akan melihat ini ... Namun, tampaknya mereka fokus pada strategi acak, daripada mencari strategi kemenangan deterministik di mana Mafia bermain dengan informasi lengkap

Syzygy

Makalah ini membahas probabilitas dan juga masalah yang sangat berbeda.

domotorp

@domotorp: Karena cara Mafia diatur, dengan pengetahuan yang tidak lengkap, adalah mungkin untuk strategi probabilistik adalah yang terbaik. Jika seorang Mafioso selalu mengklaim sebagai Warga Negara (atau selalu mengaku sebagai Investigator), jumlah tersangka yang harus dikhawatirkan oleh Kota berkurang banyak.

Peter Shor

@ Peter: Saya setuju dengan Anda tetapi pertanyaan ini adalah tentang strategi menang kasus terburuk deterministik, seperti yang dicatat oleh Syzygy dalam komentarnya.

domotorp

Pertama-tama, perhatikan bahwa selalu ahli waris untuk memulai permainan dengan meminta setiap warga negara peran mereka jika kita mencari strategi kemenangan yang menentukan untuk Town. Ini karena jika tidak peduli apa yang dinyatakan Mafiosi sebagai Kota menang, maka jelas tidak ada salahnya untuk bertanya. Dan jika Mafiosi dapat menyatakan diri mereka sesuatu dan menang dalam kasus itu, maka mereka berpura-pura bahwa mereka melakukan deklarasi dan bertindak sesuai.

Juga, permainan seperti ini mungkin tidak akan menyelesaikan PSPACE karena tidak ada struktur yang mendasarinya. Saya sangat percaya bahwa tidak sulit untuk menganalisis game untuk semua nilai i, c, m. Di bawah ini saya melakukan ini untuk m = 1. Jadi mulai sekarang mari kita anggap bahwa hanya ada satu mafioso, M, dan permainan dimulai dengan menanyakan peran. Sekarang M bisa mengklaim penyelidik atau warga negara. Mari kita periksa kedua kasus.

Kasus 1: M mengklaim penyelidik

Jika i = 0, maka Town menang jika c setidaknya 2.

Jika i = 1, maka Town menang jika c setidaknya 4. Untuk jumlah yang lebih kecil mereka kalah karena M dapat membunuh seorang warga negara setiap malam.

Jika i = 2, maka Town menang jika c adalah setidaknya 3. Tiga tersangka simpatisan dapat saling bertanya dalam urutan lingkaran. M terungkap kecuali salah satu dari mereka mati, jadi dia harus membunuh seorang penyelidik. Ini mengurangi game ke case i = 1.

Jika i = 3, maka Town menang jika c setidaknya 1. Ke-4 orang yang diduga penyelidik dapat saling bertanya dalam urutan melingkar. M terungkap kecuali salah satu dari mereka mati, jadi dia harus membunuh seorang penyelidik. Sekarang ada (paling banyak) dua kemungkinan untuk M dan setidaknya 5 orang tersisa, sehingga mereka dapat membunuh keduanya. Jika c = 0, maka tidak peduli bagaimana mereka saling bertanya, M selalu dapat membunuh seseorang dan tetap tersembunyi (berdasarkan analisis kasus), sehingga Town tidak memiliki kemenangan deterministik.

Jika i> = 4, maka Town menang oleh simpatisan yang ditanyakan satu sama lain dalam urutan melingkar, seperti dalam kasus i = 3.

Kasus 2: M mengklaim warga negara

Di sini permainannya jauh lebih sederhana, para penyelidik meminta orang yang berbeda di setiap babak dan M membunuh satu dari mereka setiap malam (selalu lebih baik untuk membunuh penyelidik daripada warga negara). Juga, kadang-kadang mereka mungkin memilih untuk membunuh warga negara (pada kenyataannya, itu selalu ok untuk melakukannya, kecuali saya = 2 dan c = 1). Karena menggunakan rekursi, lebih baik membiarkan warga negara terbukti tidak bersalah, dan menyatakan jumlah mereka dengan n.

Kota menang jika

i = 0, n> = c + 2, i = 1, n> = c + 1, i = 2, n> = c-2, dan dari sini kita dapat melihat (dan juga dengan mudah membuktikan) bahwa secara umum i Town menang jika dan hanya jika n> = c + 2-i ^ 2. Karena dalam permainan sebenarnya tidak ada warga yang tidak bersalah di awal, ini berarti bahwa Kota menang jika i ^ 2> = c + 2.

Menyatukannya: Town tidak memiliki kemenangan deterministik jika saya <= 2. Untuk i = 3, Town menang untuk 1 <= c <= 7 (karena 0 M dapat mengklaim penyelidik dan untuk c> = 8, ia dapat mengklaim warga). Untuk i> = 4, Town menang untuk c <= i ^ 2-2.

domotorp
sumber