Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Поток Научпоп доступен 24/7 благодаря поддержке друзей Хабра
Комментарии 59
5 рациональных пиратов
Они же рациональные, причём все. И совершенно глупо считать, что Д в предложенном раскладе удовлетворится одной монетой. Во всяком случае, он должен рассуждать так: "Пока что мне светит либо 0 монет, либо 1 монета. Надо получить хотя бы 2. Если А даст мне 1 монету, а проголосую против него. Тогда Б, если не идиот, а он не идиот, должен понимать, что я и его прокачу точно так же и по тем же соображениям (тогда В мне просто обязан будет дать 1 монету, я ничего не теряю), и, чтобы этого избежать, даст мне минимум 2 монеты."
И это только самое начало рассуждений.
Совершенно верно, подобные задачи можно возгонять в бесконечную рефлексию по логике всё возрастающих порядков.
На самом деле непонятно, почему В должен соглашаться с А на 1 монету, если, прокатив А и Б, он может получить гораздо большую сумму.
Пусть осталось всего 3 чувака: В, Г, Д, и прямо сейчас будет делить В.
Д конечно может заранее сказать, что поддержит вариант, только если ему дают не менее двух монет. Заявив, что для него это прямо красная линия)) Но что, если В все равно предложит "99, 0, 1", поставив Д перед фактом и отрезав себе возможность поменять расклад? Теперь если Д пойдет на принцип и откажется, он остается ни с чем. Поэтому Д примет и такой вариант - получить хоть какие-то деньги для него важнее, чем "по-пацански ответить за базар" и отомстить за несправедливую дележку. Игрок В, понимая это, предлагает "99, 0, 1" и предложение прокатывает. Аналогично можно размотать и для 5 игроков.
Чтобы осталось всего 3 чувака, А и Б должны вести себя нерационально, что противоречит условиям задачи.
На самом деле А должен предложить сразу такие условия, которые заведомо устроят ещё минимум двоих, а это непростое дело. Притом, что ситуация ВГД в ваших стратегиях заведомо лучше для всех живых, чем АБВГД.
Давайте по порядку. Предположим, что чуваков исходно всего 3. Вы согласны с моими доводами о том, почему "99, 0, 1" в таком кейсе гарантированно принимается?
Согласен.
И сразу скажу, что не готов рассматривать задачу с 4 чуваками, потому что она сложнее задачи с 5.
Я всё-таки хочу попробовать рассмотреть 4 )
Итак, Б, В, Г, Д. Если игрок Б предлагает "99, 0, 1, 0", то игрок Г, ранее тоже размахивавший красными линиями, либо примет вариант, либо остается ни с чем (потому что "99, 0, 1", как установлено выше, гарантированно прокатывает). Поэтому он принимает такой вариант. Правильно?
Неправильно. Гораздо лучше будет на месте Г, например, подбросить монетку. Допуская, что Г будет подбрасывать монетку в случае 99-0-1-0, Б скорее всего предложит ему больше, например пусть 20 монет. Тогда матожидание выигрыша Г будет больше 1. Тут есть какой-то оптимум, но он явно отличается от 99-0-1-0.
А толку с этой монетки? Г не имеет механизма, который бы ограничил ему свободный выбор - принимать или не принимать. Потому, как бы он ни понтовался заранее, он всё равно согласится на 1. Даже если подброшенная им монетка выпадет так, чтобы не брать.
Вот если бы такой неотменяемый самоограничивающий механизм для Г существовал, и Г успел его запустить до внесения предложения от Б - тогда да, уже Б был бы поставлен перед фактом.
Так суть любой игры можно выхолостить до распасов. Если он будет соглашаться на 1 монету, то он больше и не получит. Тут действует антипричинность.
Но в варианте с 5 игроками обычная причинность.
Я, видимо, не понимаю идею. Опишите вариант, где кто-нибудь из игроков, кроме самого первого, может взять 2 монеты.
Допустим, А предлагает вариант 98-0-1-0-1. Тогда Б, Г и Д, руководствуясь моей логикой, голосуют против (Б и Г – потому что ничего не получают, а Д – потому что ему некуда торопиться), и А убивают. Тогда Б понимает, что, если он предложит 99-0-1-0, то возможно Г будет против, Б убьют, а выигрыш распределится либо 0-0-99-1-0, либо 0-0-99-0-1. Тогда Б вынужден был бы предлагать Г или Д такую сумму, которая заведомо сделает одного из них его союзником, то есть минимум 2. А это уже безусловно лучше для Б и в матожидании не хуже для Г и Д, чем предложение А (у каждого из Г и Д получается 50% вероятность получить 2 вместо 100% вероятности получить 1).
Возвращаемся назад. Понимая всё это, А видит, что его скорее всего убьют, если он предложит 98-0-1-0-1, и получат лучшее предложение от Б. Тогда А должен предложить такое распределение, которое не только не даст оснований отвергнуть его, просто чтобы запугать Б, но и будет лучше распределения В, что (схватка А с В), вообще говоря, непросто для А.
Короче говоря, убивая А с предложением 98-0-1-0-1, тройственное большинство БГД ничего не теряет, а поэтому такое предложение неприемлемо для А.
Тогда Б понимает, что, если он предложит 99-0-1-0, то возможно Г будет против
Так если Г выскажется против, то дальше он остается с нулем, это я уже писал ранее. Значит именно этот вариант Б и предложит.
Зная об этом, Д и В поддержат 98-0-1-0-1.
Г никогда не остаётся с нулём, в худшем случае у него 50% шанс получить минимальную ставку (так как в эндшпиле ВГД - Г и Д равны). Даже если он прокатит Б, то всё ещё мог бы получить от В. Более того, со стороны В логично предпочесть именно Г, которому он обязан выигрышем. А минимальная ставка в этом варианте развития событий должна быть не меньше 2, чтобы Б был уверен в принятии своего предложения.
Это как в преферансе выгоднее валить играющего, чем вистующего.
Тут я ошибся, конечно, Г и Д не равны в эндпиле, так как в ВГД для Г нет смысла в выживании В.
Тем не менее, всё же видя смерть А, рационально мыслящий Б не станет повторять его опыт. Б будет рассуждать таким образом: "Мой расчёт показывает, что коллектив должен был согласиться с предложением А, однако, как видим, это не так. Расчёт моих товарищей имеет какую-то другую природу. Что мне надо сделать, чтобы не повторить судьбу А?"
Как я уже сказал, вычисление правильного хода за Б в таком случае выше моих способностей. Однако это и не нужно, потому что рационально мыслящий А не должен довести дело до своей смерти.
Думаю, что тут надо расписывать всё дерево игры и считать, сколько какие ходы кому принесли. Может быть, можно сократить при этом общее количество монет, однако тоже не факт – возможна какая-то экспоненциальная зависимость ставок.
Можно сказать короче: предложение Б:99-0-1-0, рассмотренное в авторском решении, противоречит условиям задачи, так как подразумевает нерациональность А.
Тогда Б, если не идиот, а он не идиот, должен понимать, что я и его прокачу точно так же и по тем же соображениям
Б не будет предлагать 1 монету пирату Д. Ему (кроме своего) нужен всего 1 голос. Он предложит монету пирату Г. Пират Г согласится, потому что пират В предложит ему 0 монет.
Зачем пирату Г соглашаться на 1 монету от пирата Б, если, допуская для себя возможность более агрессивной стратегии, он мог бы рассчитывать на большую щедрость Б?
Решение выше базируется на предположении, что пираты будут пассивно соглашаться на варианты во вред себе только потому, что они самые хорошие из оставшихся. Это не рационально в логике более высокого порядка.
Зачем пирату Г соглашаться на 1 монету от пирата Б
Затем что если он не согласится, право раздела перейдёт к В, который не даст ему ничего.
Это кажется нерациональным только с позиции житейской логики, потому что в реальной жизни делёжка по таким строго формальным правилам никогда не происходит.
Вы тут рассматриваете пиратов как конечные автоматы, которые ничего не знают о предыстории и не прогнозируют будущее. А для этого в условиях задачи нет никаких предпосылок.
Допуская, что пират Г может не согласиться на 1 монету, пират Б вынужден будет предложить пирату Г больше. Поэтому выигрышная стратегия для Б, В и Г должна быть направлена на шантаж предыдущих пиратов, а не на подбирание объедков.
Тем более формально неверно как базу для индукции рассматривать заведомо недостижимую в дереве игры ситуацию дележа между Г и Д.
Рациональная стратегия для пиратов была бы изначально сговориться и потребовать больше у А, но это уже будет не по условию задачи.
Представьте что пиратов только трое, В, Г, Д. Вы - Д и В вам предлагает одну монету. Согласитесь? )
В ситуации ВГД на месте Д я соглашусь на 1 монету. Но ситуация ВГД недостижима из АБВГД при рациональной стратегии А.
Тут же можно разматывать не только справа, но и слева, что гораздо осмысленнее.
изначально сговориться и потребовать больше у А
Им не надо сговариваться для того, чтобы действовать против А.
Здесь суть как раз в том что пиратов нужно воспринимать не как живых людей с чувством справедливости, а как логических автоматов, предпочитающих получить одну монету чем ничего и знающих что все остальные из них принимают решения строго по тому же принципу.
Ловушка, кмк в том что монет по условию 100. Если бы их было всего 3 или 4, решение было бы куда очевиднее.
и знающих что все остальные из них принимают решения строго по тому же принципу
Этого нет в условиях задачи.
В условиях задачи "рациональное" решение. Рационально тут склонить Б к более-менее справедливому дележу показательной казнью А. И А в таких условиях надо очень немало поразмыслить, чтобы остаться в живых и оставить себе хотя бы 1 монету.
Мы же вроде как матожидание выигрыша максимизируем, а не находим гарантированный локальный максимум?
Мы же вроде как матожидание выигрыша максимизируем
Нет, задачка не на распределение вероятностей. Она полностью логическая с единственным верным решением.
Единственно верное решение у такой задачи может быть только в том случае, если заранее обязать пиратов пользоваться одним алгоритмом, известным друг другу.
Большинство игровых задач вероятностны.
Хорошо, не буду спорить )
Соглашусь с тем что условие в статье могло быть сформулировано точнее.
В целом, задача достаточно известная и многократно разобранная. Для неё даже отдельная статья в русской и английской вики есть.
Так как пираты рациональные, то они могут поставить себя на место других и провести те же рассуждения с другой точки зрения. Так что они логически придут к одному алгоритму
Только если алгоритм единственный.
Короче - надо честно строить многомерную матрицу зависимости ожидаемого выигрыша пиратов от стратегий (минимального количества монет, которое согласен получить пират на каждой итерации) каждого из них и смотреть оптимальную стратегию для каждого. Там всего 6 пиратов - нампай легко справится!
Простая логика, много раз повторенная тут, диктует, что для всех остальных стратегий ожидаемый выигрыш будет хуже получаемой 1 монеты.
Распишите, пожалуйста, подробно рассуждения Б в том случае, если Б видит, что А фактически убит. Предложенный анализ совершенно обходит этот вопрос, что, на мой взгляд, выглядит подобно делению правой и левой частей уравнения на ноль в ходе рассуждений. Нет аккуратной логической связи.
По логике автора, Б должен сделать вид, что произошла какая-то ошибка и никакого А по сути вообще не было. Но это противоречит условию о рациональности пиратов.
Я пират В, и я хочу рассмотреть рассуждения Б в том случае, если я не соглашусь с А на одну монету, на что потенциально имею полное право.
Если пират В рационален (по условию) и, тем не менее, проголосовал против предложения А (предположим, что так произошло), то Б обязан сделать вывод, что его первоначальный анализ неверен и предпринять, видимо, какие-то другие действия. Другими словами, в предложенной формулировке задачи пираты своими голосами передают информацию друг другу, а не только перераспределяют добычу.
Особенно явно эта проблема становится видна, если удлинить цепочку ещё на несколько шагов. Например, пусть на корабле тысяча пиратов, а на кону миллион монет. Следуя логике автора, первый пират должен всё так же предлагать по одной монете нечётным пиратам. В то время как в другой логике каждый из пиратов, находящихся в середине цепочки, на каждом втором шаге играет в игру "забрать минимальную ставку или рискнуть в надежде на повышение?", а для пирата с минимальным номером это, в свою очередь, гораздо более интересная игра "достаточное предложение или смерть?". Обе носят вероятностный характер.
По логике автора, Б должен сделать вид, что произошла какая-то ошибка и никакого
На самом деле, эта ситуация противоречит условию. Потому что по условию все они действуют рационально, и рационально действующий А убит бы не был. Если бы оно случилось, то Б должен бы был подумать "ну и дебил, блин".
Не так.
А не имеет никакой информации о стратегии других пиратов, поэтому умереть ему простительно, если рациональная стратегия не единственна или не детерминирована (например, если В кидает монетку).
Может быть, что рациональная стратегия других пиратов такова, что А надо убить вне зависимости от сделанного им предложения, просто чтобы напугать Б.
Но ваше возражение ценно в том плане, что раскручивает логику дальше в третий порядок.
Рассуждения А: мою логику изложил автор. Сделаю предложение 98-0-1-0-1.
Рассуждения Б и Г: нам ничего не предложили, мы против.
Д голосует за, так как это его единственный шанс вообще что-то заработать. Но может и против, неважно.
Рассуждения В: допустим, я соглашусь. Тогда я получу одну монету. Теперь, допустим, я буду против. Тогда Б увидит, что А убили, и должен будет сделать своё предложение. Что предложит Б в этой ситуации? Он может действовать по логике автора и предложить 99-0-1-0, но тогда он обязан задаться вопросом, чем он лучше А, которого убили. Б ничего не знает о стратегии Г, которому пока ничего не предлагали. Зато Б знает, что В рассчитывает получить больше 1 монеты, так как был против предложения А. Деньги к В могут придти либо в результате согласия на предложение Б, либо в результате гибели Б и согласия Г и Д на собственное предложение В. Второй случай (ВГД) полностью детерминирован, как описано у автора, при этом В получает 99 монет (иначе все деньги достанутся Г без голосования). Таким образом, Б должен сделать В лучшее предложение, то есть отдать ему 100 монет и остаться без денег, но живым.
Поэтому В, представляя себе такой анализ Б, голосует против предложения А и получает от Б 100 монет, что несомненно наиболее рационально для В.
Хорошо, но мог ли Б наплевать на произошедшее убийство А и всё равно сделать предложение 99-0-1-0? Или мог ли Б вообще искать поддержку у других пиратов, кроме В? Нет, потому что такое развитие событий противоречило бы условию о рациональности В (которое в данном случае можно рассматривать как самосбывающееся пророчество).
Итог: А умер, потому что ему не повезло стоять первым. Б не получил денег, но остался жив, что наилучший вариант для него при такой стратегии В. В остался жив и получил все деньги благодаря своему контринтуитивному голосованию. Г и Д остались живы и ничего не получили, так как Г никто ничего и не предлагал, а голос Д ни на что не повлиял.
Где я неправ в этом рассуждении?
Ваша ошибка вот:
Зато Б знает, что В рассчитывает получить больше 1 монеты,
Неважно что В думает, почему он решил голосовать против, тут он получает 0, ведь Г согласится с предложением. Потому что если Г не согласится он скорее всего получит 0, а тут он получает 1. Ему выгоднее взять 1 монету, чем надеятся что Д потом не согласится с 1 монетой пойдя на принцип, или В вдруг не включит жадность и не заберет себе 99 монет, которые может без проблем забрать.
Нет смысла показательно наказывать А, потому что на следующем этапе эта показушность ни на что не влияет, ведь там показательно наказывать уже должны другие, а им это невыгодно. А вы, которые вместо четкой логики пытаетесь давить на психику, отказались от 1 монеты в пользу 0. Зато поимели А.
Предположение Б о том, что Г обязательно согласится на предложение Б, противоречит условию о рациональности В. Тогда с тем же успехом можно предполагать и другие нерациональные действия пиратов.
Иными словами, вы в дереве вариантов выбираете противоречащий условиям задачи.
Если В выберет голосование против и никто не станет совершать запрещённых условиями ходов, то ход В тоже тем самым окажется разрешенным.
Сам принцип раскрутки справа налево подразумевает отсутствие учёта предыстории.
Короче - надо честно строить многомерную матрицу зависимости ожидаемого выигрыша пиратов от стратегий (минимального количества монет, которое согласен получить пират на каждой итерации) каждого из них и смотреть оптимальную стратегию для каждого. Там всего 6 пиратов - нампай легко справится!
Пиратов пять и стратегия для каждого в том как распределить монеты оптимальным образом. Нампай тут незачем, для решения максимум бумага и ручка нужны.
Это не так
Пират Б вообще ничего предлагать Д не будет, ему хватит голоса пирата Г, что бы разделить.
Там верное решение, просто большая часть итераций пропущена.
Ну и идея в четности: если один из пиратов с 1 монеткой не согласится, то очередь перейдёт к пирату, который им вообще ничего предлагать не будет.
Чтобы узнать точное время, достаточно посмотреть на муравья, который находится дальше всего от ближайшего к нему конца палки и ползет от этого конца. Максимальное время падения — это время, которое потребуется самому далекому муравью, чтобы доползти до ближайшего края.
Почему дальше всего от ближайшего к нему конца палки? Ближе всего. Например, если муравей сидит на самом конце, то "он" (с учётом нашей трактовки столкновений) проползёт по всей палке (он ползёт от от ближайшего конца к дальнему).
дел (не туда ответил)
А теперь сделайте следующий логический шаг. И учитывайте, что А не хочет оказаться за бортом.
И учитывайте, что А не хочет оказаться за бортом.
Если пирата А выкинут за борт, то предлагать будет пират Б. Тогда пираты В и Д получат 0 монет. Им выгоднее согласиться на предложение пирата А.
Г может не согласиться с Б и выкинуть того за борт за неравноценный делёж. Понимая это, А и Б с самого начала должны быть щедрее.
Проще говоря, с фига ли пираты в своей стратегии учитывают только последний ход?
Допустим, я пират Г, и я с самого начала говорю: "я выкину за борт каждого, кто мне предложит меньше 20 монет". Пират В тогда будет рассуждать так же. Вот и пусть думают А и Б.
В этом случае пиратам В и Д будет выгоднее в последний момент нарушить договоренность и все-таки забрать свою монету, потому что иначе они могут остаться вообще ни с чем. Например, если пират В верит договоренности, голосует против предложения А и того выбрасывают за борт, то затем пират Б не предложит ему вообще ничего и легко купит еще один недостающий голос за 1 монету.
я с самого начала говорю: "я выкину за борт каждого, кто мне предложит меньше 20 монет"
В Вашей интерпретации это больше походит на "Golden Balls", где каждый из двух финалистов выбирает между "украсть" и "поделить". Причём, с точки зрения рациональной игры нет никакого смысла выбирать "поделить".
oops, был неправ.
Интересные вариации задачи про пиратов получаются если монет всего две или одна )
так как при отказе и переходе хода к Б они могут не получить ничего или меньше
Так у них одна монета. Что значит ничего или меньше?
Обозначим д(Х) = доля пирата Х. Рассмотрим ситуации по возрастанию количества участников дележки. Каждый пират будет иметь одну или несколько выгодных для него ситуаций и не будет соглашаться на меньшее количество монет, чем в самой выгодной для него ситуации. Ситуацию, когда остался только Д, не рассматриваем, поскольку это невозможно - если дележка дойдет до момента, когда останутся только Г и Д, Г в любом случае заберет себе все золото, и дележка закончится.
Остались Г, Д:
д(Г) = 100 - выгодно Г
д(Д) = 0
Остались В, Г, Д:
д(Д) = 1 - выгодно Д (его голос проще всего подкупить, поэтому все, кроме Г, предложат ему 1 монету)
д(Г) = 0
д(В) = 99 - выгодно В
Остались Б, В, Г, Д:
д(Д) = 1 - выгодно Д
д(Г) = 0
д(В) = 0
д(Б) = 99 - выгодно Б
Остались А, Б, В, Г, Д:
д(Д) = 1 - выгодно Д
д(Г) = 0
Чтобы не оказаться за бортом, пирату А нужно купить еще один голос, помимо Д и своего. Б и В оба согласятся не меньше, чем на 99 монет, поэтому пират А должен одному из них предложить 99 монет. Пирату А не достанется монет, но по крайней мере он не окажется за бортом. Таким образом:
д(В) = 0 или 99
д(Б) = 99 или 0 - выгодно Б или В
д(А) = 0
Если введем более старшего, чем А, пирата К (капитан), ситуация будет похожа на БВГД:
д(Д) = 1 - выгодно Д
д(А) = 1 - выгодно А
д(К) = 98 - выгодно К
д(Г) = д(В) = д(Б) = 0
Еще более старшему пирату К1 понадобится купить 4 из 7 голосов, то есть он предложит аналогичную предыдущей дележку, не оставив себе монет.
Еще более старшему пирату К2 понадобится купить 4 из 8 голосов, то есть он предложит 1 монету Д, А, К1, оставшиеся 97 заберет себе, и так можем продолжать до количества пиратов равного 201.
У вас ошибка в случае для 5 пиратов уже. Да, теоретически и В и Б могли бы попасть в ситуацию, где они получат 99 монет. Но они до нее точно не доживут, по крайней мере В. Потому что если убить А, то Б предложит 1 монету Д/Г и выиграет. И В свои 99 монет никак никогда не получит. Он их получает только при условии, что А/Б вышли, но мы с вами видим, что Б, если не дурак, никогда не выйдет из игры.
Поэтому А достаточно предложить лишь 1 монету В. Б ясно не согласится ни на что меньше 99, но В больше этой 1 монеты никогда не увидит.
Вы же эту логику применили к Д как-то? Хотя при условии смерти всех остальных Д получит все 100 монет, вы как-то пришли к тому, что этого не случится. Это же для него лучший исход. Точно такая же логика распространяется на Г,В и Б. Почему вы ее там не применяете?
В случае логики в статье Д всё равно ничего не светит, но в тоже время он ничем и не рискует - это его сильно отличает от остальных. Но это никак не учитывается.
Если считать моральное удовлетворение от смерти товарища как слабоположительный исход (скажем в 0,001 монеты), то логика всё же меняется - пиратам, которые получают мало монет - выгодно убивать.
Б предложит 1 монету Д/Г и выиграет.
Да, только предлагать он должен именно Г.
Остались Б, В, Г, Д:
д(Д) = 1 - выгодно Д
д(Г) = 0
д(В) = 0
д(Б) = 99 - выгодно Б
В этой ситуации Д одинаково выгодно голосовать как за Б, так и против. Одну монету он получит в обоих случаях. Поэтому Б лучше подкупить Г одной монетой.
Про ситуацию с 5-ю пиратами ниже объяснили.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Шесть интересных логических задач