Перед вами головоломка по эпистемической логике. Для ее решения не требуется знакомства с предыдущими публикациями. Материал продолжает перевод статьи Джоэла Дэвида Хэмкинса «Epistemic Logic and the Problem of Common Knowledge». Ранее вышли:
Задача о разделе пиратского сокровища
Пиратский корабль, на борту которого находится команда грозных и безупречно логичных пиратов, а также сокровище из ста золотых монет, которое им предстоит разделить между собой. Как они это сделают?
Пираты уже давно договорились о процедуре раздела сокровища. Все они линейно упорядочены по старшинству: капитан, первый помощник, второй помощник и так далее по иерархии. Но для простоты будем называть их пиратом номер один, пиратом номер два, пиратом номер три и так далее. Пират номер девять тем временем драит палубу, готовясь к предстоящему.
Для проведения раздела все пираты собираются на палубе, а пират самого низкого ранга встает на доску. Стоя перед остальными пиратами, он предлагает конкретный способ разделить золото: столько‑то золотых монет капитану, столько‑то пирату номер два и так далее. После этого пираты голосуют за предложенный план, причем пират, стоящий на доске, также участвует в голосовании.
Если план одобряет строгое большинство пиратов, то он принимается, и золото распределяется именно таким образом. Но если план не получает поддержки большинства, то, к сожалению, предложивший его пират должен пройти по доске и упасть в море, где его ждет смерть. После этого процедура продолжается со следующим пиратом снизу по старшинству, который теперь, разумеется, становится пиратом самого низкого ранга.
Предположим, что вы - пират номер десять. Какой план вы предложите?
Сочли бы вы хорошей идеей предложить оставить себе девяносто четыре золотые монеты, а оставшиеся шесть раздать нескольким другим пиратам?
На самом деле вы действительно можете предложить именно такой вариант, и если все сделать правильно, ваш план будет принят!
Прежде чем объяснить почему, расскажу еще немного о пиратах. Я уже упоминал, что пираты безупречно логичны. Более того, это является общим знанием: каждый из них знает, что все пираты безупречно логичны, каждый знает, что остальные это знают, каждый знает, что остальные знают, что все это знают, и так далее. В частности, в своих рассуждениях они могут опираться на то, что другие пираты логичны, что другие пираты знают о логичности всех остальных, что они знают, что остальные это знают, и так далее.
Кроме того, общим знанием среди пиратов является и то, что все они придерживаются одной и той же системы ценностей, в которой приоритеты строго упорядочены следующим образом.
Система ценностей пиратов:
Самое главное - остаться в живых.
На втором месте - получить золото, и чем больше, тем лучше.
После этого - по возможности добиться смерти других пиратов.
Наконец, при прочих равных, по возможности сделать так, чтобы золото досталось пиратам более высокого ранга.
Иными словами, каждый пират любой ценой предпочтет избежать смерти. Если он остается в живых, то постарается получить как можно больше золота. Добившись этого, он предпочтет, чтобы погибло как можно больше других пиратов, однако не настолько, чтобы ради дополнительной смерти отказаться хотя бы от одной золотой монеты. А если и во всем остальном варианты равны, то пират предпочтет, чтобы золото, которое не досталось ему самому, по возможности досталось пиратам более высокого ранга. Ведь в глубине души пираты - люди консервативные.
Какой план вы предложите, будучи пиратом номер десять?
Естественно, пираты будут оценивать план пирата номер десять в сравнении с альтернативой - планом, который предложит пират номер девять. Тот, в свою очередь, будет сопоставляться с планом пирата номер восемь, и так далее.
Поэтому, по‑видимому, анализ следует вести снизу вверх, рассуждая в обратном порядке и начиная с того, что происходит при совсем небольшом числе пиратов.
Один пират. Если пират всего один - капитан, то он встает на доску и, очевидно, должен предложить: «Пират номер один получает все золото». Сам он проголосует за этот план, и в результате пират номер один получит все золото, как и следовало ожидать.
Два пирата. Если пиратов ровно двое, то на доску встанет пират номер два. Что же он предложит? Ему необходимо заручиться поддержкой большинства из двух пиратов, а значит, он должен добиться, чтобы капитан проголосовал за его план. Но какой бы план он ни предложил, даже если предложит отдать все золото капитану, капитан все равно проголосует против. Ведь если пирата номер два убьют, капитан и так получит все золото, а в силу третьего пункта пиратской системы ценностей он предпочтет, чтобы пират номер два погиб. Поэтому капитан не поддержит план пирата номер два, и тому, к сожалению, придется пройти по доске.
Три пирата. Если пиратов трое, что предложит пират номер три? Ему достаточно всего двух голосов, причем один из них - его собственный. Значит, ему нужно убедить либо пирата номер один, либо пирата номер два проголосовать за его план.
Но на самом деле у пирата номер два будет очень веская причина поддержать этот план, поскольку в противном случае он окажется в ситуации с двумя пиратами, которая, как мы уже выяснили, заканчивается его смертью. Поэтому пират номер три может рассчитывать на голос пирата номер два независимо от деталей своего предложения и предложит следующее: пират номер три получает все золото!
За этот план проголосуют и пират номер два, и пират номер три. Это большинство, поэтому при трех пиратах все золото достается пирату номер три.
Четыре пирата. Пирату номер четыре необходимо получить три голоса, поэтому ему нужно убедить еще двух пиратов проголосовать за его план. Он замечает, что в случае его гибели пираты номер один и два вообще не получат золота. Поэтому он понимает, что если предложить каждому из них по одной золотой монете, то в силу пиратской системы ценностей они предпочтут именно этот вариант. Таким образом, пират номер четыре предложит отдать по одной золотой монете пиратам номер один и два, а девяносто восемь монет оставить себе. Этот план будет принят голосами пиратов номер один, два и четыре.
Пять пиратов. Пирату номер пять нужны три голоса, включая его собственный. Он может фактически купить голос пирата номер три за одну золотую монету, поскольку в случае с четырьмя пиратами тот вообще ничего не получит. Кроме того, ему нужен еще один голос - пирата номер один или два, и его можно получить, предложив две золотые монеты. В силу четвертого пункта пиратской системы ценностей при прочих равных он предпочтет отдать эти монеты пирату более высокого ранга. Поэтому он предлагает следующий план: две монеты пирату номер один, ничего пирату номер два, одну монету пирату номер три, ничего пирату номер четыре, а девяносто семь монет - себе. Этот план будет принят голосами пиратов номер один, три и пять.
Шесть пиратов. Пирату номер шесть нужны четыре голоса. Он может купить голоса пиратов номер два и четыре, предложив каждому по одной золотой монете, а затем получить голос пирата номер три, предложив ему две монеты, что обойдется дешевле остальных вариантов. Поэтому он предлагает следующий план: по одной монете пиратам номер два и четыре, две монеты пирату номер три, а девяносто шесть монет - себе. План будет принят голосами пиратов номер два, три, четыре и шесть.
Семь пиратов. Пирату номер семь нужны четыре голоса. Он может купить голоса пиратов номер один и пять всего за одну монету каждому, поскольку в случае с шестью пиратами они не получают ничего. Предложив две монеты пирату номер два, он сможет заручиться еще одним голосом. При этом, в соответствии с пиратской системой ценностей, дополнительное золото он предпочтет отдать именно пирату номер два, а не пиратам более низкого ранга.
Восемь пиратов. Пирату номер восемь нужны пять голосов. Он может купить голоса пиратов номер три, четыре и шесть, предложив каждому по одной монете, а еще один голос обеспечить, отдав две монеты пирату номер один. Остальные девяносто пять монет он оставит себе. Вместе с его собственным голосом этого будет достаточно, чтобы план был принят.
Девять пиратов. Пирату номер девять нужны пять голосов. Он может купить голоса пиратов номер два, пять и семь, предложив каждому по одной монете, а пирату номер три дать две монеты. Вместе с собственным голосом пирата номер девять этого будет достаточно, чтобы план был принят.
Десять пиратов. Теперь, зная, какой раздел предложит пират номер девять, мы видим, что пират номер десять может обеспечить себе шесть голосов, предложив по одной монете пиратам номер один, четыре, шесть и восемь, две монеты пирату номер два, а оставшиеся девяносто четыре монеты забрать себе. Этот план будет принят: все перечисленные пираты проголосуют за него вместе с самим пиратом номер десять, поскольку каждый из них получит при таком разделе больше золота, чем получил бы по плану пирата номер девять.
Подведем итог и представим все предложения в следующей таблице, где строка с номером n соответствует предложению пирата номер n.
Здесь стоит обратить внимание на несколько моментов, которые позволят понять, как будет продолжаться эта закономерность. Начиная с четвертой строки, в каждой строке число пиратов, не получающих ни одной монеты, составляет почти половину от общего числа пиратов - точнее, это наибольшее целое число, строго меньшее половины. Ровно один пират получает две монеты, остальные получают по одной, за исключением самого предлагающего, который забирает все оставшееся золото.
Эта схема может сохраняться до тех пор, пока золота хватает для ее реализации. Дело в том, что каждый пират может фактически купить по одной монете голоса тех пиратов, которые при альтернативном плане, то есть в случае с одним пиратом меньше, получили бы ноль монет. Таких пиратов будет не больше, чем на единицу меньше половины предыдущего числа пиратов. Затем он может купить еще один голос, предложив две монеты одному из тех пиратов, кто в альтернативном плане получил только одну монету. Вместе с его собственным голосом это даст половину голосов плюс один, то есть большинство.
Кроме того, из пиратской системы ценностей следует, что две монеты всегда будут доставаться либо пирату номер один, либо пирату номер два, либо пирату номер три. Причина в том, что на предыдущем шаге один из них всегда будет самым высокопоставленным пиратом среди тех, кто получает одну монету. В разных предложениях их доли циклически меняются по схеме: ноль монет, одна монета, две монеты.
По крайней мере до тех пор, пока количество золота не станет ограничивающим фактором, все остальные пираты, начиная с пирата номер четыре, при каждом следующем предложении будут поочередно получать то ноль, то одну монету. При этом пират номер n —1 всегда будет получать ноль монет в предложении пирата номер n.
Поэтому мы видим, что эта закономерность сохраняется по меньшей мере до пирата номер 199, предложение которого будет иметь следующий вид:
Пират 199: 1 2 0 0 1 0 1 0 1 0 1 0 1 … 1 0 1 0 0
Именно на пирате номер 199 впервые возникает ситуация, когда для покупки голосов остальных приходится потратить все сто монет. Ему необходимо отдать девяноста восьми пиратам по одной монете и еще две монеты пирату номер два, чтобы вместе с собственным голосом набрать в общей сложности сто голосов. В результате самому ему не остается ни одной монеты.
По этой причине пират номер 200 сможет предложить план, который будет принят: теперь ему уже не требуется тратить две монеты на покупку одного голоса, поскольку по плану пирата номер 199 сто пиратов получают ноль монет. Поэтому пират номер 200 может получить сто чужих голосов, предложив по одной монете каждому, кто по плану пирата номер 199 не получил бы ничего. Вместе с его собственным голосом это даст большинство в 101 голос.
200 пиратов: 0 0 1 1 0 1 0 1 0 1 0 … 0 1 0 1 1 0
Пирату номер 201 также нужен 101 голос. Он может их получить, отдав по одной монете всем тем, кто в случае с 200 пиратами получил бы ноль, и добавив к ним свой собственный голос.
А вот несчастному пирату номер 202 необходимо уже 102 голоса, и получить их он не сможет, поскольку у него всего 100 монет. Поэтому пират номер 202 погибнет.
Далее возникает любопытный эффект. Пират номер 203 сможет рассчитывать на голос пирата номер 202, не отдавая ему за это ни одной монеты. Ведь альтернатива для пирата номер 202 - собственная смерть. Поэтому, помимо своего голоса и бесплатного голоса пирата номер 202, пирату номер 203 потребуется набрать лишь еще 100 голосов. Он сможет купить их, предложив ста пиратам по одной монете.
Пирату номер 204 снова не хватит одной монеты, поэтому он погибнет. Хотя пират номер 205 сможет рассчитывать на один дополнительный бесплатный голос, этого все равно будет недостаточно для принятия его предложения. За сто монет он сможет купить сто голосов, а вместе с собственным голосом и бесплатным голосом пирата номер 204 получит в общей сложности 102 голоса, что не составляет большинства.
По той же причине пират номер 206 также не сможет набрать достаточно голосов. Даже с учетом собственного голоса и бесплатных голосов пиратов номер 204 и 205 он сможет получить не более 103 голосов, а этого для большинства недостаточно.
Таким образом, пират номер 207 сможет рассчитывать на голоса пиратов номер 204, 205 и 206. Добавив к ним собственный голос и еще сто голосов, купленных по цене одной монеты за голос у пиратов, которые в противном случае не получили бы ничего, он сможет набрать 104 голоса, то есть большинство.
Дальнейшее развитие этой закономерности читателю предлагается исследовать самостоятельно в последующих вопросах. Разбираться в этой задаче весьма увлекательно. Постепенно возникает интересное явление: появляются все более длинные последовательности идущих подряд пиратов, каждый из которых оказывается неспособен предложить план, набирающий большинство голосов, пока внезапно не появляется пират, который выживает именно благодаря тому, что может заранее рассчитывать на голоса всех этих обреченных пиратов.
Раздел пиратского сокровища при очень малом количестве монет
Не менее интересно разобраться, что происходит, когда монет совсем мало. Например, если имеется всего одна золотая монета, то уже пират номер четыре не сможет предложить план, который будет принят. Он способен купить лишь один дополнительный голос, а вместе с его собственным это даст только два голоса, чего недостаточно для большинства.
При одной монете пират номер пять уже сможет выжить: он купит голос пирата номер один и вдобавок сможет рассчитывать на голос пирата номер четыре, а также на свой собственный голос. В сумме этого хватит для большинства. Дальнейшее развитие ситуации читателю предлагается исследовать самостоятельно в последующих вопросах.
Интересен даже случай, когда монет вообще нет. Тогда делить нечего, и голосование фактически сводится к вопросу о том, должен ли пират пройти по доске или остаться в живых.
Если пират всего один, он выживает. Пират номер два погибнет, поскольку пират номер один проголосует против него. Но именно поэтому пират номер два проголосует за предложение пирата номер три, и тот выживет.
Возникает следующая последовательность:
выживает, погибает, выживает, погибает, погибает, погибает, выживает, погибает, погибает, погибает, погибает, погибает, погибает, погибает, выживает, …
После каждого успешного предложения, при котором предлагающий пират выживает, должна последовать достаточно длинная череда смертей, чтобы очередной пират смог заранее рассчитывать на достаточное число голосов обреченных пиратов.
Иными словами, после каждого выживает текущую последовательность нужно удвоить, добавив подряд столько же элементов погибает. Только после этого следующий пират получит достаточную поддержку и выживет.
Эту версию процесса можно также переформулировать как «Игру в популярность», в которую играют старшеклассники, пытающиеся попасть в круг избранных. Ученик с самым низким положением в иерархии встает перед остальными, и те голосуют, следует ли изгнать его или оставить в составе своей компании.
