Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Поток Научпоп доступен 24/7 благодаря поддержке друзей Хабра
Комментарии 32
Идея модификации задачи и её решение принадлежит автору.
Да-да, а мы, комментаторы Хабра, ну просто вообще не при чём )))
Круто, только эти “предлагает то решение которое считает нужным” слегка вводят в заблуждение. Исходя из своих целей Е будет требовать (и получит) все 100 монет себе.
Для него сохранение жизни пиратов более высокий приоритет, чем получить все деньги. А если он при 5 пиратах потребует 0 монет всем остальным, то 3м как минимум будет выгодно “убить” А, прежде чем принять это предложение (их приоритет №3) на следующем круге. Что категорически не устроит Е (его приоритет №1 - выживание А). Так что решение как-то … неокончено.
Это действительно нетривиальный момент.
В живых 5 пиратов. Согласно требованию пирата E, пират A предлагает, чтобы E получил 100 монет остальные 0. За пираты A,E. Нужен ещё один голос.
Но E заявил, что B должен проголосовать ЗА иначе E будет против любого его предложения.
Фишка тут в том, что пират E готов "убить" B, понимая что именно эта готовность позволит манипулировать остальными пиратами так, чтобы никто не погиб и монеты были распределены правильно (с точки зрения E)
Если E так сделает - он нарушит условия индукции. А значит С и/или D тоже “имеют право нарушить индукцию” и заверить B в своей поддержке - за соответсвующую плату в 100 монет ) (ну или в 1 монету - сговариваться же нельзя!)
Изначально в задаче было правило
4. Пираты не доверяют друг другу и не способны придерживаться каких-либо договорённостей, за исключением предлагаемого плана распределения.
За исключением E, который находится под действием эликсира. Именно поэтому он может так делать.
Но ещё раз - при таком поведении Е нарушаются условия индукции. Т.е. все предыдущие рассуждения выбрасываются за борт. И задачу для 5 пиратов надо решать “с нуля” не опираясь на решения задачи с меньшим числом пиратов. Это просто логически некорректно.
Ну или Е должен давать тоже обещание В, какое бы он давал при 4х пиратах. Т.е. на каждом шаге индукции мы “зафиксировали обещание”. И при увеличении числа пиратов - он должен дать всем “старым” пиратам точь в точь те же самые обещания что были на предыдущем шаге. Иначе просто принцип индукции ломается и рассыпается на независимые задачи.
Индукция тут и не работает, задачу в посте для 5 пиратов пришлось решить с нуля (добавить еще одно обещание т.к. иначе голосов для принятия не хватало). Что будет для большего числа пиратов мне не совсем понятно - вроде бы пираты смогут проигнорировать Е и спокойно поделить добычу по старинке.
При большем количестве пиратов я не смог найти решение, при котором E может забрать все монеты, и вероятно его не существует. Задумка в том, что на каждом этапе хотя бы половина пиратов должна получать хотя бы одну монету, чтобы было что терять. А если старший пообещает что-то не то, то ему эти монеты не переобещаются (чтобы было чем подкупить остальных.
В общем, решение, вероятно, возможно, но более громоздкое.
При большем количестве пиратов я не смог найти решение, при котором E может забрать все монеты, и вероятно его не существует
Кажется, при 6 пиратах работает та же схема, как при 5: эликсирщик может аналогично навязать старшему свой план под угрозой смерти, а второму пообещать "неподдержку", если старший помрет. И вроде бы это обобщается и дальше, только при 7 и 8 игроках надо обещать неподдержку второму и третьему, и т.д.
На всякий случай, он может заранее рассказать остальным свою стратегию, и дать клятву, что будет её придерживаться.
«Я проголосую за план C тогда и только тогда, когда C предложит то распределение, которое я назову».
А почему Е называет распределение не в свой ход? По изначальным правилам он должен только голосовать за или против предложенного старшими. Если у него есть такое право, то он и без эликсиров уже в привилегированном положении по сравнению с другими.
Нужен ли вообще элексир правды?
Главное отличие этой версии задачи - в том, что у 4 пиратов целевая функция одинакова (жизнь, бабло, кровожадность), а у пятого - другая (жизнь, бабло, милосердие). Причём его жизни ничего не угрожает, а порядок (бабло, милосердие) или (милосердие, бабло), похоже, не играет роли.
Если все пираты насквозь прозорливые, то они безо всяких клятв вычислят оптимальную линию поведения пятого, так же, как они вычисляют линии поведения подельников.
Попробую промоделировать индукцию в этих условиях.
0) E остался один, распеределение - всё бабло к нему.
1) D, E. Голос D решающий, скатиться к 0 в принципе невозможно, убивать некого. D максимизирует цф, получая (1,100,3), а E достаётся (1,0,2).
2) C, D, E.
Что бы ни предложил C, - D при отказе получит больше (на +1 жертву, как минимум).
E выбирает между (1, 100-Mc-Md, 3) и (1, 0, 2).
Клятва в этот момент означает, что пираты уже знают, как устроены решения E.
И вот тут внезапно! Если C предложит ему (1,0,3) - то есть, "я тебе ничего не дам, но ты же заинтересован, чтобы выжило как можно больше? это лучше, чем если вы меня убьёте!"
Может ли E поклясться "если C предложит мне 0, то я его убью!"? Нет, это противоречит его целевой функции.
Тут как бы возникает коллизия. C видит, к чему идёт дело, и, прежде чем E поклянётся "если C не отдаст мне все 100, то я его убью", - сам может сказать "если E меня убьёт, то хрен ему чего достанется". Безо всякой клятвы. Типа, E, ублюдок, мать твою, ты думал меня трахнуть, иди, я сам тебя трахну, дерьмо собачье!
Поэтому поведение с клятвами все-таки отличается от поведения без клятв. С клятвами Е нельзя подкупить какими-то предложениями, т.к. независимо от сказанных слов Е все равно проголосует против если его доля будет меньше 100. А С не настолько хочет обставить Е чтобы заплатить за это жизнью.
Но кстати, давайте посмотрим, если E не клянётся всякой фигнёй, а действует рационально.
Итак, случай 2) C,D,E. Как мы выяснили, для E (1,0,3) лучше, чем (1,0,2), поэтому C предлагает распределение 100-0-0 (всё себе, D будет протестовать, а этот сопляк E добренький).
3) B,C,D,E.
Если B убьют, то E получит (1,0,3). Если оставят в живых, то (1,e,4). Ровно та же фигня получается! То есть, E голосует "за". B+E дают кворум. Поэтому B предлагает распределение 100-0-0-0.
4) A,B,C,D,E.
Если A убьют, то B получит (1,100,1), C - (1,0,1), D - (1,0,1), E - (1,0,4).
Если A оставят, то B получит (1,b,0), C - (1,c,0), D - (1,d,0), E - (1,e,5).
Видно, что B заинтересован голосовать против, E опять заинтересован голосовать за, так что нужно просто ублажить C или D хотя бы одной монеткой.
99-0-1-0-0 или 99-0-0-1-0.
А всё потому, что сопляк добренький!
Допустим, E не кровожадный, а пофигистичный.
И да, я зря стал писать тройки, - понятно, что там 1 в начале всегда. Итак, двойки (бабло, жертвы). Для E - (бабло, 0).
D,E.
Если D выжил, то (d,3) и (e,0), где d+e=100.
D, разумеется, выжил, поэтому 100 и 0.
C,D,E.
Если C выжил, то (c,2), (d,2), (e,0).
Если C убили, то (0,0), (100,3), (0,0).
D заинтересован убить. E готов принять хотя бы монетку, поэтому 99, 0, 1.
B,C,D,E.
Если выжил, то (b,1), (c,1), (d,1), (e,0).
Если убили, то (0,0), (99,2), (0,2), (1,0).
C можно перекупить только 100 монетами, d - одной, e - одной (или, для надёжности, двумя).
Ясное дело, что выгоднее 99-0-1-0.
A,B,C,D,E.
Если выжил, то (a,0), (b,0), (c,0), (d,0), (e,0).
Если убили, то (0,0), (99,1), (0,1), (1,1), (0,0).
B можно перекупить только 100, C - 1, D - 2, E - 1.
Нужно купить два голоса, это будут C и E. 98-0-1-0-1.
Наконец, пусть E радикальный. Его позиция: "если я не получаю максимум, то лучше я убью всех, пусть поплачут".
D,E - как мы знаем, (100,3), (0,3).
C,D,E
Если выжил - (c,2), (d,2), (e,2). Если нет - (0,0), (100,3), (0,3).
И вот тут E может сказать: либо я получу 100, либо C умрёт.
Тогда (0,2), (0,2), (100,2).
B,C,D,E.
Если выжил - (b,1), (c,1), (d,1), (e,1). Если нет - и если индукция работает! - то (0,0), (0,2), (0,2), (100,2).
B нужно купить один голос. И казалось бы, достаточно дать монету c или d.
Но. Индукция здесь так не работает. E действительно может анонсировать, что на следующем шаге он примет такое решение, которое будет максимизировать его выгоду на этом шаге.
Но, раз пираты все продуманные, - что мешает пиратам C и D устроить тот же цирк? У них нет элексира, но у них есть свобода слова и воли.
Ну ок, свободу слова у них отняли процедурой, - голосуют молча. Но они же могут мысленный пинг-понг устроить... Может быть, тут надо посмотреть в сторону равновесий Нэша?
D устраивает ровно тот же цирк (всегда голосует против, ведь если все прошлые провалятся то деньги его). Е может конкурировать с ним только за счет клятв. А старшие пираты не могут действовать также т.к. они рискуют умереть.
D это не устраивает, потому что во всех случаях, кроме провала троих, - денег ему не достанется вовсе.
Но он может наслаждаться казнями! Это ему тоже в плюс. А вот для Е - любая казнь неприммлема (он лучше все деньги потеряет). Потому , если было бы возможно обсуждение - “оригинальнм” Е бы этим задавили и оставили бы ни с чем.
Т.е. подкуп одной монеткой с “кровожадными” пиратами не сработает - т.к. для них одна монетка + казнь лучше одной монетки. И потому у А очень мало вариантов выжить, если вообще есть при пофигистичном Е (для того же С 100 монет+ казнь - лучше 100 монет!)
Я имею в виду что если убрать механизм клятв, то D находится в положении не хуже Е (и даже лучше), т.к. тоже не рискует умереть. А вот начиная с C угрозы E начинают работать.
Идея модификации задачи ... принадлежит автору
Исходная задача недавно обсуждалась, в комментах я озвучил ту же идею. Но на первенство не претендую, наверняка эта мысль возникала у многих в разное время. Собственно, решение исходной задачи опирается как раз на отсутствие такого эликсира.
Но здесь всё наоборот: систему, построенную на страхе и жадности, ломает единственный участник, который не может лгать.
Тут дело не во лжи/правде, а в том, что обладатель эликсира реально умеет в пресловутые "красные линии" и за счет этого имбует.
Без эликсира правды при числе пиратов N>2 команда итеративно сократится до двух человек а потом ночью до одного. Рациональные пираты подчиняются нерациональному закону, поэтому всё так.
E может диктовать любое распределение при четырёх пиратах.
Вот только не любое, он будет обязан отдать B, C, D то количество монет которое пообещал им А на предыдущем этапе.
То же самое для случая с тремя пиратами.
Даже более того, если А принесли в жертву, B будет знать что ни один его план не будет принят Е. У него нет смысла соглашаться с планом Е, он может предложить любое другое распределение только ради того чтобы поломать схему.
эти клятвы рассчитаны так что исполнять их не придется) А сам отдаст Е 100 монет своим планом, т.к. не умереть ему важнее чем монеты, а B поддержит его т.к. тоже хочет жить.
Ну так рассуждая - все единогласно (ну кроме D) проголосуют за Е при любом числе пиратов. Т.к. обещание “я тебя убью, если не отдашь мне все деньги” можно повторять для всех! Но только D - может его безопасно проигнорировать.
Не факт. Тут проблема в том что вся схема ломается. К примеру, Е требует себе все монеты. А предлагает С 80 монет, а себе оставляет 20. А и B голосуют за, D и E против. Как будет рассуждать C?
Если я проголосую против, А будет принесён в жертву и на следующем ходе E будет голосовать против B, т.к. связан клятвой отвергать любой его план. Соответственно, B сможет предложить любое распределение которое взбредёт ему в голову, и Е будет обязан поддержать его на следующем этапе.
С большой вероятностью B предложит С в этом случае меньше 80 монет, поэтому смысла отвергать план А нет.
Смысл есть. Не забывайте - пираты кровожадны. Т.е. и С - в любом случае не получая ничего вполне удовлетворится смертью А и В. Для него это положительный балланс. Кровожадность это тот ещё геймченжер. Е - это единственная надежда А не выживание!
Кровожадность по приоритету меньше жадности. Если А изначально предложит С 80 монет, С будет выбирать между гарантированными 80 монетами, или неизвестным количеством который предложит B на следующем шаге.
Ключевой момент - в случае 4-х пиратов, B не обязан соглашаться с планом Е! Для него не будет разницы соглашаться или нет, Е в любом случае отвергнет его план.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Пять пиратов: эликсир правды