Из Википедии, бесплатной энциклопедии
  (Перенаправлен из Вырезать и выбрать )
Перейти к навигации Перейти к поиску

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

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

История [ править ]

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

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

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

Анализ [ править ]

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

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

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

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

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

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

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

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

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

Обобщения и улучшения [ править ]

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

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

Эффективное размещение [ править ]

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

Если бы Боб знал, что предпочитает Кэрол, и она ему нравилась, он мог бы разрезать торт на полностью шоколадный и ванильный кусочки, Кэрол выбрала бы ванильный кусок, а Боб получил бы весь шоколад. С другой стороны, если ему не нравится Кэрол, он может разрезать торт на чуть больше половины ванили в одной порции и остальную часть ванили и весь шоколад в другой. Кэрол может также захотеть съесть порцию с шоколадом назло Бобу. Есть процедура для решения даже этой проблемы, но она очень нестабильна перед лицом небольшой ошибки в суждении. [10] Были разработаны более практичные решения, которые не могут гарантировать оптимальность, но которые намного лучше, чем «разделяй и выбирай», в частности, скорректированная процедура победителя (AW) [11]и процедура излишков (SP). [12] См. Также Эффективная резка торта .

См. Также [ править ]

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

Примечания и ссылки [ править ]

  1. Перейти ↑ Steinhaus, Hugo (1948). «Проблема справедливого разделения». Econometrica . 16 (1): 101–4. JSTOR  1914289 .
  2. ^ a b Брамс, Стивен Дж .; Тейлор, Алан Д. (1996). Честное разделение: от разрезания торта до разрешения споров . Издательство Кембриджского университета. ISBN 0-521-55644-9.
  3. ^ a b Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы резки торта: будьте честны, если можете . Натик, Массачусетс: А. К. Питерс. ISBN 978-1-56881-076-8. LCCN  97041258 . OL  2730675W .
  4. ^ Янг, Х. Пейтон (1995-01-01). Справедливость . Издательство Принстонского университета. ISBN 978-0-691-21405-4.
  5. ^ Уолш, Тоби (2011). Брафман, Ронен I .; Робертс, Фред С .; Цукиас, Алексис (ред.). «Онлайн резка торта» . Теория алгоритмических решений . Конспект лекций по информатике. Берлин, Гейдельберг: Springer: 292–305. DOI : 10.1007 / 978-3-642-24873-3_22 . ISBN 978-3-642-24873-3.
  6. ^ Организация Объединенных Наций (1982-12-10). «Приложение III: Основные условия поиска, разведки и разработки. Статья 8» . un.org .
  7. ^ Гарднер, Мартин (1994). Мои лучшие математические и логические головоломки . Dover Publications. ISBN 978-0486281520.
  8. ^ Klarreich, Erica (13 октября 2016). «Математика нарезки торта» . Журнал Quanta (журнал Scientific American) .
  9. ^ АЗИЗ, ХАРИС; МАККЕНЗИ, САЙМОН (2017). «Дискретный и ограниченный протокол резки торта без зависти для любого количества агентов». arXiv : 1604.03655 . Bibcode : 2016arXiv160403655A . Цитировать журнал требует |journal=( помощь )
  10. ^ Резание торта с полным знанием дела Дэвид МакКиллан, 1999 (не проверено)
  11. ^ Стивен Дж. Брамс и Алан Д. Тейлор (1999). Беспроигрышное решение: гарантия справедливой доли акций для всех Norton в мягкой обложке. ISBN 0-393-04729-6 
  12. ^ Лучшие способы разрезать торт Стивеном Дж. Брамсом, Майклом А. Джонсом и Кристианом Кламлером в Уведомлениях Американского математического общества, декабрь 2006 г.