Как поделить торт так, чтобы никто не завидовал? Алгоритмы справедливого дележа

Что математики называют отсутствием зависти

Равный делёж и делёж без зависти — разные вещи. Равный делёж означает, что каждый участник получил ровно свою долю по какой-то общей мерке, например по весу или площади куска. Делёж без зависти требует большего: каждый участник, оценивая ВСЕ куски по собственному вкусу, считает свой кусок не менее ценным, чем любой другой. Разница важна, потому что вкусы у людей разные. Один участник любит шоколадную половину торта и равнодушен к фруктовой, другой наоборот — и кусок, равный по массе, может при этом сильно проигрывать по личной ценности.

Делёж на двоих — один режет, другой выбирает

Самый старый и самый простой способ работает так. Первый участник режет торт на два куска, которые сам считает равноценными — при любом собственном вкусе он вправе резать так, как ему кажется справедливым. Второй участник смотрит на оба куска и забирает тот, что нравится ему больше. Первому участнику после этого завидовать нечему: по его собственной оценке оба куска стоили одинаково, значит, какой бы кусок ни достался, для него это ровно та же ценность. Второй участник тоже доволен — он выбрал сам, из двух вариантов, тот, что ценит выше.

Почему для троих та же идея не работает напрямую

Кажется естественным продолжить схему: один режет торт сразу на три части, а трое выбирают по очереди. Проблема в том, что резчик режет части равными по собственному вкусу, но после его нарезки участники со стороны, оценивая эти же куски по своему вкусу, почти всегда находят среди них один явный фаворит. Если этот фаворит достаётся не резчику, а кому-то из выбирающих, резчик может почувствовать себя обделённым — ведь по его собственным меркам куски были равны, а забрали лучший на вид не он. Прямое расширение схемы «режет-выбирает» до трёх участников зависть не убирает, и рабочую процедуру для этого случая математики нашли только через полтора десятилетия после того, как задачу о справедливом дележе поставили в математической форме в середине сороковых годов XX века.

Процедура для троих без зависти

Решение предложили математики Джон Селфридж и Джон Конвей, и работает оно в четыре шага. Первый участник режет торт на три куска, которые сам считает равноценными. Второй участник изучает эти куски по собственному вкусу: если два из них уже кажутся ему самыми большими и равными между собой, он ничего не трогает, а если явно выделяется один самый ценный кусок, он подрезает его так, чтобы сравнять с занимающим второе место, а срезанный остаток откладывает в сторону — этот остаток пока не участвует в разборе.

Куски разбирают в порядке третий участник, второй, первый. Если второй участник что-то подрезал, есть дополнительное условие: подрезанный кусок обязан взять именно второй участник — но только если третий не забрал его раньше. Такой порядок гарантирует отсутствие зависти на первых трёх кусках. Остаётся отложенный остаток от подрезки. Его делит на три равные по собственной оценке части тот из второго и третьего участников, кто получил неподрезанный кусок на предыдущем шаге. Порядок разбора остатка такой — сначала выбирает тот, кто держит подрезанный кусок, затем первый участник, и только затем сам резчик остатка.

• Первый участник режет торт на три равные по своей оценке части
• Второй участник подрезает самый ценный на его взгляд кусок до уровня второго по ценности
• Куски выбирают по очереди — третий, второй, первый, с обязательным условием для подрезанного куска
• Остаток от подрезки делит на три части тот, кто получил неподрезанный кусок, а выбирают в порядке подрезанный участник, первый участник, резчик остатка

Пример на понятных числах

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

Где такие процедуры применяют за пределами тортов

Одинаковый принцип годится для любого делимого ресурса, который люди ценят по-разному. Наследство делят между родственниками, у которых разные привязанности к конкретным вещам покойного, — кому-то важна дача, кому-то коллекция книг. При разводе супруги распределяют совместно нажитое имущество, а совладельцы общего бизнеса — доли и обязанности. Исследователи фейр-дивижн даже построили работающие онлайн-сервисы, где алгоритмы этого типа помогают делить аренду квартиры между соседями по комнатам или распределять домашние обязанности в семье так, чтобы никто не чувствовал себя обделённым по сравнению с остальными.