Дели и выбирай
Из Википедии, свободной энциклопедии
Из Википедии, свободной энциклопедии
Дели и выбирай (или Режем и выбираем, а также Я режу, ты выбираешь) — это процедура разрезания торта между двумя участниками, в результате которой отсутствует зависть. В задаче предполагаются неоднородные блага или ресурсы («торт») и два участника с различными предпочтениями на отдельные части торта. Протокол работает следующим образом: один из участников («разрезающий») режет торт на два куска, второй участник («выбирающий») выбирает один из кусков, а разрезающему достаётся оставшийся кусок.
Метод дели-и-выбирай упоминается в Библии в Книге Бытия. Когда Авраам и Лот прибыли в страну Ханаан, Авраам предложил разделить её между ними. Затем Авраам, пришедший с юга, разделил землю на «левую» (западную) и «правую» (восточную) части и предложил Лоту выбирать. Лот выбрал восточную часть, которая включала Содом и Гоморру, а Аврааму досталась западная часть, в которой находились Беэр-Шева, Хеврон, Бейт-Эль и Сихем.
Метод дели-и-выбирай даёт разбиение, в котором отсутствует зависть в следующем смысле: каждый из двух участников может поступать так, что в результате дележа его часть (по его мнению) будет не менее ценна, чем часть второго участника, независимо от поведения второго участника. Вот как участники могут себя вести:
Для стороннего наблюдателя делёж может показаться несправедливым, но для участников дележа нет причин завидовать друг другу.
Если функции оценок участников аддитивны, то делёж дели-и-выбирай получается также и пропорциональным в следующем смысле: каждый участник может действовать так, что он гарантированно получит кусок со значением по меньшей мере 1/2 от полной оценки торта. Это следствие того, что в случае аддитивных оценок любое разрезание без зависти также и пропорционально.
Протокол работает одинаково как для дележа желаемого ресурса (как при разрезании торта), так и для дележа нежелательного ресурса (как при дележе обязанностей).
Протокол дели-и-выбирай предполагает одинаковые причитающиеся доли[англ.] и решение делить между собой или использовать медиацию, но не третейского судью. Предполагается, что добро делимо любым образом, но части могут оцениваться игроками по-разному.
Для разрезающего имеет смысл делить ресурс как можно справедливее, в противном случае он вполне может получить нежелательную часть. Это правило является конкретным приложением концепции занавеса неведения.
Метод дели-и-выбирай не гарантирует, что каждый участник получит в точности половину торта по его собственной оценке, так что делёж не является точным. Не существует конечной процедуры для точного дележа, но это можно сделать с помощью двух движущихся ножей[англ.]. См. статью Процедуры «Движущийся нож» Остина.
Дели-и-выбирай может дать неэффективное разрезание.
В качестве примера обычно используется торт, который наполовину ванильный и наполовину шоколадный. Предположим, что Боб любит только шоколад, а Кэрол только ваниль. Если Боб будет разрезающим и он не в курсе предпочтений Кэрол, его надёжной стратегией будет разрезать торт так, что каждая часть будет содержать равное количество шоколада. Но тогда, независимо от выбора Кэрол Боб получает только половину шоколада и ясно, что разрезание не эффективно по Парето. Вполне возможно, что Боб по неведению выделит всю ваниль (и некоторое количество шоколада) в одну большую порцию, так что Кэрол получит всё, что она хотела, в то время как Боб получит меньше, чем он мог бы получить после совместного обсуждения.
Если Боб знает предпочтения Кэрол и она ему нравится, он может разрезать торт на всю шоколадную и всю ванильную части, так что Кэрол может выбрать ванильную часть, а Боб получит всю шоколадную часть. С другой стороны, если ему Кэрол не нравится, он может разрезать торт на чуть больше половины ванильной части в одном куске, а остаток ванильной части и шоколадную часть в другом куске. Кэрол может также взять кусок с частью шоколада назло[англ.] Бобу. Существует процедура для решения даже таких проблем, но она очень нестабильна при небольших ошибках в оценках[1]. Есть более практичные решения, которые гарантируют оптимальность, но много лучше, чем метод дели-и-выбирай, разработанный Стивеном Брамсом и Аланом Тейлором, в частности процедура «подстраивающийся победитель»[2][3].
В 2006 году Стивен Дж. Брамс, Майкл А. Джонс и Христиан Кламер объяснили детально новый путь разрезания торта, названный дележом излишек[англ.] (англ. surplus procedure, SP), который удовлетворяет условию беспристрастности и тем самым решает вышеупомянутую задачу[4]. Субъективные оценки игроков выделенных им кусков по отношению ко всему торту одинаковы.
Мартин Гарднер популяризовал задачу разработки аналогичной процедуры справедливого дележа для больших групп в его майской колонке 1959 года «Mathematical Games» (Математические игры) в журнале Scientific American[5]. Одна из процедур начинается с того, что один из участников режет торт по своему пониманию справедливого дележа. Любой другой может отрезать от некоторого куска часть, чтобы сделать его меньше. Последний, кто уменьшит кусок, обязан его взять.
В журнале «Scientific American» был предложен новый метод[6], который разработали Азиз и Маккензи[7]. Будучи быстрее в принципе, чем более ранние методы, он потенциально остаётся очень медленным: , где n — это число желаемых кусков.