Эта статья — математический разбор задач, поставленных в предыдущей.
Кратко напомню задачу: команда велика и выстроена по рангу; старший (Сильвер) предлагает дележ, выплаты кратны одной монете. Заданный процент команды должен одобрить дележ, в противном случае капитан исключается и следующий по рангу предлагает свой дележ на тех же условиях.
Давайте же вместе разберемся, как Сильвер проделывал эти фокусы. Для порога в 50% задача хорошо известна и решается по индукции. Сильвер первый в очереди, и каждый пират имеет номер. Сильвер предлагает по одной монете всем пиратам с нечетным номером, а остальное берет себе.
В самом деле, если в команде всего двое, то Сильвер — это и есть половина, и он законно заберет все себе. Далее — по индукции, ведь если Сильвера изгонят, то все номера вырастут на единицу, а новый дележ будет, по индукции, таким же. В итоге те, кто сейчас нечетные, не получат ничего, и потому они одобрят дележ.
Если Сильвер сам не голосует, то это то же самое, как если бы он нуждался в строго большем, чем 50%, числе голосов. Схема выплат зависит теперь от делимости на три, а не на два, и она более сложная.
Если в команде двое, то все приходится отдавать младшему (но мы помним, что команда большая?). Для троих уже можно младшему ничего не давать, а среднему дать одну монету: С10. Здесь С означает “Сильвер”. Далее номер второй уже хочет получить все, поэтому ему нет смысла что-то предлагать, а голоса двух других Сильверу необходимы. Поэтому он даст одну монету младшему и две — второму с конца: С021. Затем ему нужно три голоса, то есть два помимо своего, и можно не предлагать ничего тому, который ожидает три монеты: С0102. Две следующие серии: С01210, С012021.
Но постойте! Схема для семи пиратов дает Сильверу пять голосов, если считать его собственный, или четыре, если голосуют шесть пиратов (все, кроме Сильвера)! А Сильверу необходимо только четыре в первом случае и три во втором. То есть он может выбрать одного из тех, кому по схеме предписано предложить две монеты, и не давать ему ничего. И каждый, кому что-то предложено, проголосует за — ведь новый дележ даст ему меньше!
Далее схемы имеют вид: С0120102, С01201210, и так далее: группа 012 повторяется несколько раз, а потом либо серия 10, либо 021, либо 0102, в зависимости от остатка от делимости численности команды на три. При этом из тех, кому предписано предлагать две монеты, можно выбрать нужное число пиратов — их больше, чем нужно Сильверу (если команда достаточно велика). В самом деле, за него точно голосуют те, кому он даст одну монету, а их около одной трети. Ему нужно еще около одной шестой, а “двоек” тоже около одной трети! Так что выбрать надо лишь около половины из них.
Такая схема работает до порога в 60% — проверьте! Далее схема немного меняется, но тоже зависит от делимости на три и с максимальной выплатой в два дублона — вплоть до 62.5%.
А для еще больших порогов (вплоть до 2/3) схема зависит от делимости на четыре, а в остальном она аналогична. Запишем несколько первых выплат для порога в две трети (сам Сильвер голосует) и начиная с трех человек (для меньшей команды все отдается младшему):
С10, С021, С0132, С01203, С012310, С0123021, С01230132, С012301203.
Далее схема повторяется: несколько групп 0123, затем “хвост”, зависящий от делимости на четыре: по кругу 10, 021, 0132, 01203. При этом те, кому предписана одна монета и две монеты вместе составляют около половины голосов. Сильверу нужно еще около одной шестой, а схема предписывает три монеты еще примерно четверти команды; так что у Сильвера опять есть некоторый выбор!
Схема позволяет получить аж три четверти голосов примерно (для большой команды), но проблема в том, что она опирается на индукцию, а при малой команде и пороге выше двух третей она не работает (проверьте!).
До порога 70% работает другая схема. Поначалу кажется, что Сильверу с ростом численности придется платить все больше и больше:
С110, С0221, С01332, С012443, С0123554, С01234665.
Однако при десяти пиратах Сильвер может осадить тех двоих с растущими аппетитами: С012345006, а затем “укоротить” и остальных: С0123450110, С01234001221, С012300112332. Теперь аппетиты выросли у троих, но у Сильвера появился лишний ноль: С(0123)011223003. Видите группу 0123 (в скобках), от которой уже отделилась новая группа? Далее: С(0123)0122330110, С(0123)(0123)3001221 — вот и вторая группа сформировалась! Итак, получается несколько групп 0123, одна растущая группа и некоторый “хвост”.
Проверьте, что такая же ситуация с любым порогом! Максимальная выплата, конечно, растет, но зависит только от порога (если численность команды достаточно велика). Выплаты для порога в 80% мы выписывать не будем; отметим только, что с ростом численности они растут аж до 19 монет, потом снижаются и для большой команды (от 30 человек) не превосходят пяти монет. Схема аналогичная: группы 012345, формирующаяся группа и некий “хвост”, зависящий от остатка от деления на шесть. При этом у Сильвера не всегда, но часто есть свобода в выборе: за него голосуют пять шестых примерно, а ему нужно лишь четыре пятых.
А как же Сильвер сумел вынудить пиратов отдать все ему, из-за чего чуть не погиб, высаженный с горой золота на островок?
Напомню, что пираты, фрустрированные дележами Сильвера, которые сами и одобряли, потребовали стопроцентного одобрения дележа всей командой. Сильвер согласился, причем отказался делить, отдав это право младшему в очереди (штурману).
Это очень просто! Пираты не сообразили вовремя, что 100% включают в себя и Сильвера, так что он должен одобрить дележ. А он не одобрит никакой дележ, если ему предложат не всё. Штурману дадут плетей и выгонят, но следующий пират окажется в том же положении. Либо кто-то предложит всё отдать Сильверу (а тогда за что страдали его предшественники?), либо все будут устранены и Сильвер отдаст себе всё. Если же штурман предложит отдать всё Сильверу, а его не поддержат, то опять следующий окажется в том же положении.
Что же до коварного трюка Сильвера (это когда он использовал свободу выбора для уменьшения выплат), то он относится к теории игр и заслуживает отдельного разбора. Так что к этой задачке мы еще вернемся, и не раз!
Путеводители по рубрике и каналу в целом
Литература
- Мулен Э. Теория игр с примерами из математической экономики. Там эта задача рассмотрена для порога в 50% и команды любого размера. Оцените адрес сайта, на котором лежит серьезная монография о математике!
- Chernov I., Ivashko E. Quorum Analysis for the "Pirate Game" problem // Proceedings of the Second International Workshop on Stochastic Modeling and Applied Research of Technology (SMARTY 2020). CEUR Vol-2792, 2020. Pp. 24-37. В этой статье рассмотрена задача для любого порога. Моя заметка основана на ней.
- А вот в этой статье задача используется для проведения параллелей с Российской действительностью. Небесспорно, на мой взгляд, но интересно. И тоже для пяти пиратов и порога в половину голосов!
