Разделяй и выбирай

Метод разрезания торта двумя людьми без зависти

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

Эта процедура использовалась с древних времен для разделения земли, пирога и других ресурсов между двумя сторонами. В настоящее время существует целая область исследований, называемая справедливым разрезанием пирога , посвященная различным расширениям и обобщениям метода «разрезать и выбрать». ^{[2] [3]}

История

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

Конвенция ООН по морскому праву применяет процедуру, похожую на разделение и выбор, для распределения участков в океане между странами. Развитое государство, подающее заявку на разрешение на добычу полезных ископаемых из океана, должно подготовить два участка примерно одинаковой ценности, позволить органу ООН выбрать один из них для резервирования развивающимся государствам и получить другой участок для добычи: ^{[4] [5]}

Каждая заявка... должна охватывать общую площадь... достаточно большую и имеющую достаточную предполагаемую коммерческую ценность, чтобы позволить проведение двух горнодобывающих операций... равной предполагаемой коммерческой ценности... В течение 45 дней с момента получения таких данных Орган определяет, какая часть должна быть зарезервирована исключительно для проведения Органом деятельности через Предприятие или совместно с развивающимися государствами... Обозначенная территория становится зарезервированной зоной, как только будет одобрен план работы для незарезервированной территории и подписан контракт. ^[6]

Анализ

Торт, разрезанный на две части

Разделяй и выбирай независим в следующем смысле: каждый из двух партнеров может действовать таким образом, который гарантирует, что, согласно их собственному субъективному вкусу, их распределенная доля будет по крайней мере столь же ценной, как и другая доля, независимо от того, что делает другой партнер. Вот как может действовать каждый партнер: ^{[2] [3]}

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

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

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

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

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

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

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

Обобщения и улучшения

Разделение между более чем двумя сторонами

Разделяй и выбирай работает только для двух участников. Когда участников больше, можно использовать другие процедуры, такие как последний уменьшающий или протокол Even–Paz . Мартин Гарднер популяризировал проблему разработки аналогичной справедливой процедуры для больших групп в своей колонке «Математические игры » в журнале Scientific American за май 1959 года . ^[7] См. также пропорциональное разрезание торта . Более новый метод был описан в журнале Scientific American . ^[8] Он был разработан Азизом и Маккензи. ^[9] Хотя в принципе он быстрее, чем предыдущий метод, он все еще потенциально очень медленный. См. разрезание торта без зависти .

Эффективное распределение

Разделяй и выбирай может привести к неэффективному распределению. Одним из часто используемых примеров является торт , который наполовину ванильный , наполовину шоколадный . Предположим, что Боб любит только шоколад, а Кэрол — только ванильный. Если Боб режет торт и не знает о предпочтениях Кэрол, его безопасная стратегия — разделить торт так, чтобы каждая половина содержала равное количество шоколада. Но тогда, независимо от выбора Кэрол, Боб получает только половину шоколада, и распределение явно не является эффективным по Парето . Вполне возможно, что Боб по своему невежеству положил бы всю ваниль (и некоторое количество шоколада) в одну большую порцию, поэтому Кэрол получает все, что хочет, в то время как он получил бы меньше, чем мог бы получить, ведя переговоры. Если бы Боб знал предпочтения Кэрол и она ему нравилась, он мог бы разрезать торт на полностью шоколадный кусок и полностью ванильный кусок, Кэрол выбрала бы последний, а Боб получил бы весь шоколад. С другой стороны, если ему не нравится Кэрол, он может разрезать торт, положив в одну часть чуть меньше половины ванили, а в другую — остальную часть ванили и весь шоколад. Кэрол также может быть мотивирована взять часть с шоколадом, чтобы досадить Бобу. Существует процедура, позволяющая решить даже эту проблему, но она очень нестабильна перед лицом небольшой ошибки в суждении. ^[10] Были разработаны более практичные решения, которые не могут гарантировать оптимальности, но намного лучше, чем разделение и выбор, в частности, скорректированная процедура победителя (AW) ^[11] и процедура излишков (SP). ^[12] См. также Эффективное разрезание торта .

Деление с одной точкой

Вагенер ^[13] изучает вариант «Разделить и выбрать» на двумерном торте, в котором делитель находится в невыгодном положении: вместо того, чтобы сделать разрез, он может только отметить точку на торте. Выбирающий может затем сделать прямой разрез через эту точку и выбрать кусок, который он предпочитает. Он доказывает, что если торт ограничен, делитель всегда может захватить по крайней мере 1/3 торта. Если торт одновременно ограничен и выпукл, делитель может захватить 4/9 торта.

Смотрите также

• Маркет-мейкер  — субъект торговли на фондовом рынке, игроки на финансовых рынках, которые предлагают либо купить, либо продать по определенной цене (плюс спред).
• Распределение ресурсов  – распределение ресурсов среди возможных вариантов использования.

Примечания и ссылки

1. Штейнхаус, Хьюго (1948). «Проблема справедливого дележа». Econometrica . 16 (1): 101–4. JSTOR  1914289.
2. Brams, Steven J.; Taylor, Alan D. (1996). Справедливое разделение: от разрезания торта до разрешения споров . Cambridge University Press. ISBN 0-521-55644-9.
3. Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы разрезания торта: будьте честны, если можете . Натик, Массачусетс: AK Peters. ISBN 978-1-56881-076-8. LCCN  97041258. OL  2730675W.
4. Янг, Х. Пейтон (1995-01-01). Акции. Princeton University Press. doi :10.1515/9780691214054. ISBN 978-0-691-21405-4.
5. Уолш, Тоби (2011). «Онлайн-разрезание торта». В Brafman, Ronen I.; Roberts, Fred S.; Tsoukiàs, Alexis (ред.). Lecture Notes in Computer Science. Vol. 6992. Berlin, Heidelberg: Springer. pp. 292–305. doi :10.1007/978-3-642-24873-3_22. ISBN 978-3-642-24873-3. S2CID  501890. {{cite book}}: |journal=игнорируется ( помощь ) ; Отсутствует или пусто |title=( помощь )
6. Объединенных Наций (1982-12-10). "Приложение III: Основные условия поиска, разведки и эксплуатации. Статья 8". un.org . Архивировано из оригинала 2001-09-14.
7. Гарднер, Мартин (1994). Мои лучшие математические и логические головоломки . Dover Publications. ISBN 978-0486281520.
8. Кларрайх, Эрика (13 октября 2016 г.). «Математика разрезания торта». Журнал Quanta (Scientific American) .
9. АЗИЗ, ХАРИС; МАКЕНЗИ, САЙМОН (2017). «Дискретный и ограниченный протокол разрезания торта без зависти для любого числа агентов». arXiv : 1604.03655 . Bibcode :2016arXiv160403655A. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
10. Разрезание торта с полным знанием дела Дэвид МакКуиллан 1999 (не рецензировано)
11. Стивен Дж. Брамс и Алан Д. Тейлор (1999). Беспроигрышное решение: гарантия справедливой доли для всех. Norton Paperback. ISBN 0-393-04729-6 
12. Лучшие способы нарезать торт» Стивена Дж. Брамса, Майкла А. Джонса и Кристиана Кламлера в «Уведомлениях Американского математического общества», декабрь 2006 г.
13. Вагенер, Андреас (01.01.2006). «Геометрическое деление с фиксированной точкой: не половина торта, но по крайней мере 4/9». Групповое решение и переговоры . 15 (1): 43–53. doi :10.1007/s10726-005-9000-z. ISSN  1572-9907.