Дели и выбирай (:yln n fdQnjgw)

Дели и выбирай (или Режем и выбираем, а также Я режу, ты выбираешь) — это процедура разрезания торта между двумя участниками, в результате которой отсутствует зависть. В задаче предполагаются неоднородные блага или ресурсы («торт») и два участника с различными предпочтениями на отдельные части торта. Протокол работает следующим образом: один из участников («разрезающий») режет торт на два куска, второй участник («выбирающий») выбирает один из кусков, а разрезающему достаётся оставшийся кусок.

История

Метод дели-и-выбирай упоминается в Библии в Книге Бытия. Когда Авраам и Лот прибыли в страну Ханаан, Авраам предложил разделить её между ними. Затем Авраам, пришедший с юга, разделил землю на «левую» (западную) и «правую» (восточную) части и предложил Лоту выбирать. Лот выбрал восточную часть, которая включала Содом и Гоморру, а Аврааму досталась западная часть, в которой находились Беэр-Шева, Хеврон, Бейт-Эль и Сихем.

Анализ

Разрез торта на два куска

Метод дели-и-выбирай даёт разбиение, в котором отсутствует зависть в следующем смысле: каждый из двух участников может поступать так, что в результате дележа его часть (по его мнению) будет не менее ценна, чем часть второго участника, независимо от поведения второго участника. Вот как участники могут себя вести:

• Разрезающий может разрезать торт на две части, которые он считает равными. Тогда независимо от того, какую часть выберет второй участник (выбирающий), они оба получат по куску, который не менее ценен, чем другой кусок.
• Выбирающий может выбрать кусок, который ему понравился больше, так что даже если разрезающий поделит торт на явно неравные части (в глазах выбирающего), у выбирающего нет причин жаловаться, поскольку он выбирает более ценный в его глазах кусок.

Для стороннего наблюдателя делёж может показаться несправедливым, но для участников дележа нет причин завидовать друг другу.

Если функции оценок участников аддитивны, то делёж дели-и-выбирай получается также и пропорциональным в следующем смысле: каждый участник может действовать так, что он гарантированно получит кусок со значением по меньшей мере 1/2 от полной оценки торта. Это следствие того, что в случае аддитивных оценок любое разрезание без зависти также и пропорционально.

Протокол работает одинаково как для дележа желаемого ресурса (как при разрезании торта), так и для дележа нежелательного ресурса (как при дележе обязанностей).

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

Для разрезающего имеет смысл делить ресурс как можно справедливее, в противном случае он вполне может получить нежелательную часть. Это правило является конкретным приложением концепции занавеса неведения.

Метод дели-и-выбирай не гарантирует, что каждый участник получит в точности половину торта по его собственной оценке, так что делёж не является точным. Не существует конечной процедуры для точного дележа, но это можно сделать с помощью двух движущихся ножей. См. статью Процедуры «Движущийся нож» Остина.

Проблемы эффективности

Дели-и-выбирай может дать неэффективное разрезание.

В качестве примера обычно используется торт, который наполовину ванильный и наполовину шоколадный. Предположим, что Боб любит только шоколад, а Кэрол только ваниль. Если Боб будет разрезающим и он не в курсе предпочтений Кэрол, его надёжной стратегией будет разрезать торт так, что каждая часть будет содержать равное количество шоколада. Но тогда, независимо от выбора Кэрол Боб получает только половину шоколада и ясно, что разрезание не эффективно по Парето. Вполне возможно, что Боб по неведению выделит всю ваниль (и некоторое количество шоколада) в одну большую порцию, так что Кэрол получит всё, что она хотела, в то время как Боб получит меньше, чем он мог бы получить после совместного обсуждения.

Альтернативы

Если Боб знает предпочтения Кэрол и она ему нравится, он может разрезать торт на всю шоколадную и всю ванильную части, так что Кэрол может выбрать ванильную часть, а Боб получит всю шоколадную часть. С другой стороны, если ему Кэрол не нравится, он может разрезать торт на чуть больше половины ванильной части в одном куске, а остаток ванильной части и шоколадную часть в другом куске. Кэрол может также взять кусок с частью шоколада назло Бобу. Существует процедура для решения даже таких проблем, но она очень нестабильна при небольших ошибках в оценках. Есть более практичные решения, которые гарантируют оптимальность, но много лучше, чем метод дели-и-выбирай, разработанный Стивеном Брамсом и Аланом Тейлором, в частности процедура «подстраивающийся победитель».

В 2006 году Стивен Дж. Брамс, Майкл А. Джонс и Христиан Кламер объяснили детально новый путь разрезания торта, названный дележом излишек (англ. surplus procedure, SP), который удовлетворяет условию беспристрастности и тем самым решает вышеупомянутую задачу. Субъективные оценки игроков выделенных им кусков по отношению ко всему торту одинаковы.

Делёж среди более чем двух участников

Мартин Гарднер популяризовал задачу разработки аналогичной процедуры справедливого дележа для больших групп в его майской колонке 1959 года «Mathematical Games» (Математические игры) в журнале Scientific American. Одна из процедур начинается с того, что один из участников режет торт по своему пониманию справедливого дележа. Любой другой может отрезать от некоторого куска часть, чтобы сделать его меньше. Последний, кто уменьшит кусок, обязан его взять.

В журнале «Scientific American» был предложен новый метод, который разработали Азиз и Маккензи. Будучи быстрее в принципе, чем более ранние методы, он потенциально остаётся очень медленным: $O(n^{2n+3})$, где n — это число желаемых кусков.

См. также

• Справедливый делёж
• Оптимальное распределение ресурсов
• Маркетмейкеры, игроки финансовых рынков