Насколько тяжела мафия?

Мафия - популярная ролевая игра на вечеринках, подробное описание доступно на википедии http://en.wikipedia.org/wiki/Mafia_%28game%29 .

В основном это работает следующим образом:

В начале каждому из игроков тайно отводится роль, связанная либо с мафией, либо с городом. Каждая роль может иметь особые способности; подробнее об этом позже. $N$
Есть две фазы игры: день и ночь. Ночью мафия может тайно общаться друг с другом; и они могут договориться об одном целевом игроке, которого они убивают той ночью. В День все (живые) игроки общаются на открытом форуме. Игроки могут согласиться линчевать одного игрока, необходимо абсолютное большинство всех игроков.
Игра заканчивается, если осталась только мафия или остался только город. Выжившая партия побеждает.
Давайте предположим, что есть три роли: гражданин, следователь и мафиози. Граждане не имеют полномочий. Мафиози также не имеют никаких способностей, кроме возможности общаться друг с другом ночью и голосовать за одну жертву убийства каждую ночь. Следователи могут исследовать еще одного игрока каждую ночь, выясняя их точную роль.
Предположим, что игра начинается днем, и что роль игрока раскрывается после смерти.

Выигрышные стратегии

Учитывая установку от следователей, Citizen и мафиози, мы говорим , что установка выигрыш для города , если есть стратегия для Городских игроков, таким образом, что они победят, независимо от того , как Мафия играет. $(i,c,m)$ $i$ $c$ $m$

Обратите внимание, что мы можем предположить, что мафия играет с полной информацией, поскольку мы хотим учитывать любое решение, которое они могут принять.

Пример: установка выигрывает для города. $(4,1,1)$

День 1: Все игроки города правдиво сообщают о своей роли в открытом чате. Игрок мафии должен заявить, что он либо следователь, либо гражданин.

Если он претендует на Гражданина, то Мафиози является одним из двух предполагаемых Граждан. Каждый Следователь может расследовать любой из них и узнает истинного. Не более одного следователя может умереть ночью, а два других просто повесят мафиози.

Следовательно, мафиози должны требовать следователя. Есть 5 предполагаемых следователей. В открытом чате следователи договариваются о перестановке, чтобы проверять друг друга.

Ночь 1: Следователи проверяют свои цели, а мафиози убивают одну.

День 2: Осталось 3 следователя. Все предполагаемые следователи сообщают о своих выводах. Независимо от того, кто был убит, по крайней мере один из них также подтвержден другим живым следователем. Поскольку мафиози требовал следователя, он также должен сказать, была ли его назначенная цель мафией или нет. Если он подставляет кого-то, то Город знает, что либо он, либо подставленный - мафия, против другого подтвержденного 3 города. Если он никого не подставит, также будет 3 подтвержденных города. В любом случае, никого не вешать, а расследование только двух оставшихся подозреваемых побеждает в Тауне.

Вопросов

Насколько сложно решить, допускает ли данная установка выигрышную стратегию для Тауна? Наглядно это звучит как -полные проблемы. Кто-нибудь может придумать сокращение? $PSPACE$
Можем ли мы найти минимальные выигрышные настройки? Как и в случае, мы можем минимизировать отношения или ? $i:m$ $(i+c):m$

cc.complexity-theory gt.game-theory combinatorial-game-theory сизигия
источник

Раскрываются ли личности после смерти?

Петр Мигдаль

О да, я забыл упомянуть.

Сизигий

Интересный. Я играл в версию этой игры, где личности не раскрываются после смерти. Делает это больше о создании правдоподобных историй и обнаружении лжи.

Лукас Кук

m

$m$

@LucasCook Да, см. Arxiv.org/abs/1009.1031 (моя статья об игре Мафия). В игре, когда два игрока могут быть убиты за один ход, соотношение общего количества игроков имеет значение. Однако эффект зависит от точных правил (например, является ли линчевание необязательным или нет); и может не появиться в не вероятностных сценариях (например, вопросы о стратегии выигрыша, а не - о вероятности выигрыша).

Петр Мигдаль

Ответы:

Вот ссылка, которую вы хотите посмотреть: http://www.jstor.org/stable/10.2307/25442651

Мафия: теоретическое исследование игроков и коалиций в частичной информационной среде Браверман, М. и Этесами, О. и Моссель, Э. Анналы прикладной вероятности 2008

Аарон Рот
источник

Я не осознавал, что проблема уже изучена. Жаль, что я не знал об этом, когда играл в мафию :)

Суреш Венкат

Спасибо, я посмотрю на это ... Однако, похоже, что они сосредоточены на рандомизированных стратегиях, а не на поиске детерминированных выигрышных стратегий, где мафия играет с полной информацией

Syzygy

Эта статья имеет дело с вероятностями и, таким образом, имеет дело с совершенно другой проблемой.

Domotorp

@domotorp: Из-за того, как настроена мафия, с неполным знанием, возможно, что вероятностная стратегия - лучшая. Если мафиози всегда утверждают, что являются гражданами (или всегда утверждают, что являются следователями), число подозреваемых, о которых должен беспокоиться Таун, значительно сокращается.

Питер Шор

@Peter: Я согласен с вами, но этот вопрос о детерминистских стратегиях выигрыша в худшем случае, как отметил Сизигий в своем комментарии.

domotorp

Прежде всего, обратите внимание, что всегда полезно начинать игру, спрашивая каждого гражданина об их роли, если мы ищем детерминированную стратегию выигрыша для города. Это потому, что, независимо от того, что объявят себя мафиози, победит Город, тогда, очевидно, спрашивать не вредно. И если мафиози могут заявить о себе и победить в этом случае, то они делают вид, что сделали декларацию и действуют соответственно.

Кроме того, подобная игра, вероятно, не будет завершена PSPACE, поскольку в ней нет базовой структуры. Я твердо верю, что не сложно проанализировать игру для всех значений i, c, m. Ниже я делаю это для m = 1. Итак, теперь давайте предположим, что существует только один мафиози М, и игра начинается с выяснения ролей. Сейчас М либо претендует на следователя, либо на гражданина. Давайте проверим оба случая.

Дело 1: М утверждает следователь

Если я = 0, то город выигрывает, если с не менее 2.

Если i = 1, то город выигрывает, если c не меньше 4. Для меньшего числа они проигрывают, потому что M может убивать гражданина каждую ночь.

Если i = 2, то город выигрывает, если c равно по крайней мере 3. 3 предполагаемых следователя могут спрашивать друг друга в круговом порядке. М раскрывается, если один из них не умрет, поэтому он должен убить следователя. Это сводит игру к случаю i = 1.

Если i = 3, то город выигрывает, если c не меньше 1. 4 предполагаемых следователя могут спрашивать друг друга в круговом порядке. М раскрывается, если один из них не умрет, поэтому он должен убить следователя. Теперь у М есть (максимум) две возможности и осталось не менее 5 человек, поэтому они могут убить обоих. Если c = 0, то независимо от того, как они спрашивают друг друга, M всегда может убить кого-то и остаться скрытым (путем анализа случая), поэтому у Тауна нет детерминированной победы.

Если i> = 4, то Таун побеждает предполагаемые следователи, спрашивая друг друга в круговом порядке, как в случае i = 3.

Дело 2: М требует гражданина

Здесь игра намного проще, следователи спрашивают разных людей в каждом раунде, и М убивает одного из них каждую ночь (всегда лучше убить следователя, чем гражданина). Кроме того, иногда они могут голосовать, чтобы убить гражданина (на самом деле, это всегда нормально, если только i = 2 и c = 1). Из-за использования рекурсии лучше также разрешить гражданам доказывать свою невиновность и обозначить их число через n.

Город побеждает, если

i = 0, n> = c + 2, i = 1, n> = c + 1, i = 2, n> = c-2, и отсюда мы можем видеть (и также легко доказать), что для общего i Town выигрывает тогда и только тогда, когда n> = c + 2-i ^ 2. Поскольку в реальной игре в начале нет ни в чем не повинных граждан, это означает, что город выигрывает, если i ^ 2> = c + 2.

Собираем это вместе: у города нет детерминированного выигрыша, если я <= 2. Для i = 3 город выигрывает для 1 <= c <= 7 (для 0 M может требовать следователь, а для c> = 8 он может требовать гражданина). Для i> = 4 город выигрывает для c <= i ^ 2-2.

domotorp
источник