Задачка про разделение торта поровну между двумя детьми

На день рождения мне подарили книгу "Ученые шутят" (составители Б. С. Горобец, Ю. А. Золотов, С. Н. Федин), которую я уже почти прочел. В ней много интересных историй, но одна мне понравилась особо - это история про Берию, что назначал министров угольной промышленности. Ниже я напишу ее полностью, но сейчас хотел поговорить про упрощенную постановку проблемы честного разделения ресурсов, как я узнал ее почти 10 лет назад из курса "Making Better Group Decisions: Voting, Judgement Aggregation and Fair Division" от Eric Pacuit из University of Maryland: Предположим, что есть торт и два голодных ребенка. Они хотят поделить торт поровну без участия третьей стороны. Если торт однородный (например, шоколадный торт с равномерно распределенной ванильной глазурью), то найти справедливое разделение несложно - торт можно относительно ровно порезать. Но как нам найти «справедливое» разделение торта, если он неоднороден (например, глазурь, состоящая на 1/3 из шоколада, на 1/3 из ванили и на 1/3 из клубники), и каждый ребенок хочет разные части > торта?>

Примерно такую задачу помог решить Берия двум министрам, между которыми делили угольную промышленность СССР (цитата из вышеупомянутой книги "Ученые шутят")

Назначение министров угольной промышленности> (рокировка по Берии)

Он <Берия> был мастером неожиданных и нестандартных решений. <...> Политбюро приняло решение разделить наркомат угольной промышленности, которым руководил В. В. Вахрушев, на два - для западных районов страны и восточных. Предполагалось, что возглавят их соответственно В. В. Вахрушев и Д. Г. Оника. Поручили разделение провести Берии. Можно представить, сколько мороки вызвала бы подобная процедура при обычном бюрократическом подходе. Берия вызвал Вахрушева и Онику и предложил им разделиться полюбовно. А по истечению срока вызвал обоих и сначала спросил у Вахрушева - претендента на руководство западными районами отрасли, - нет ли претензий. Тот ответил, что претензий нет, и всё поделили правильно. Тогда Берия обратился к Онике: "Как вы?" Оника заупрямился: "У меня есть претензии. Все лучшие кадры Вахрушев себе забрал. И все лучшие санатории и дома отдыха тоже". Видя такое дело, Берия рассудил: "Раз Вахрушев считает, что все разделено правильно, а Оника возражает, то сделаем так: Вахрушев будет наркомом восточных районов, а Оника - западных". И совещание на том закончил

В общем, если обратиться к "Задаче справедливого разрезания пирога", то видно, что Берия применил алгоритм, который называется дележ без зависти (envy-free). В этом алгоритме каждый партнер думает, что его кусок как миниму так же ценен как и все остальные. Такой дележ может быть произведен при помощи процедуры дели-и-выбирай: один партнёр режет пирог на два сектора, которые он считает равными, а другой партнёр выбирает сектор, который он считает лучшим. Для пирога может существовать процедура и лучше, а вот для угольной промышленности ее придумать сложнее. Думается, что именно поэтому Берия остановился на этом простом алгоритме, но забавно, что он заранее не предупредил кандидатов о том, как будет принимать решение об их поллюбовном разделении.

P.S. Рекомендую как курс, так и книгу - они определенно расширяют кругозор и интересны для изучения и помогают быть лучшим руководителем:)

P.P.S. ИЗ курса мне особенно запомнилась теорема Эрроу, которая еще называется теоремой "о невозможности демократии" как "коллективного выбора" или "теоремой о неизбежности диктатора". Смысл этой теоремы состоит в том, что

В рамках ординалистского подхода не существует метода объединения индивидуальных предпочтений для трёх и более альтернатив, который удовлетворял бы некоторым вполне справедливым условиям и всегда давал бы логически непротиворечивый результат. Ординалистский подход основывается на том, что предпочтения индивидуума относительно предлагаемых к выбору альтернатив не могут измеряться количественно, а только качественно, то есть одна альтернатива хуже или лучше другой.

#PopularScience #Math #Management #Leadership