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

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

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

История

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

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

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

Анализ

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

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

^ Штайнхаус, Хьюго (1948). «Проблема справедливого дележа». Эконометрика . 16 (1): 101–4. JSTOR 1914289 .
^ Jump up to: ^а ^б Брамс, Стивен Дж.; Тейлор, Алан Д. (1996). Справедливое разделение: от разрезания торта до разрешения споров . Издательство Кембриджского университета. ISBN 0-521-55644-9 .
^ Jump up to: ^а ^б Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы разрезания торта: будьте честны, если можете . Натик, Массачусетс: АК Питерс. ISBN 978-1-56881-076-8 . LCCN 97041258 . ОЛ 2730675В .
^ Янг, Х. Пейтон (1 января 1995 г.). Капитал . Издательство Принстонского университета. дои : 10.1515/9780691214054 . ISBN 978-0-691-21405-4 .
^ Уолш, Тоби (2011). «Онлайн разрезание торта» . В Брафмане, Ронен И.; Робертс, Фред С.; Цукиас, Алексис (ред.). Конспекты лекций по информатике. Том. 6992. Берлин, Гейдельберг: Springer. стр. 292–305. дои : 10.1007/978-3-642-24873-3_22 . ISBN 978-3-642-24873-3 . S2CID 501890 . {{cite book}}: |journal= игнорируется ( помощь ) ; Отсутствует или пусто |title= ( помощь )
^ Организация Объединенных Наций (10 декабря 1982 г.). «Приложение III: Основные условия поиска, разведки и разработки. Статья 8» . un.org . Архивировано из оригинала 14 сентября 2001 г.
^ Гарднер, Мартин (1994). Мои лучшие математические и логические задачи . Дуврские публикации. ISBN 978-0486281520 .
^ Кларрайх, Эрика (13 октября 2016 г.). «Математика разрезания торта» . Журнал Quanta (Scientific American) .
^ АЗИЗ, ХАРИС; МАККЕНЗИ, САЙМОН (2017). «Дискретный и ограниченный протокол разрезания торта без зависти для любого количества агентов». arXiv : 1604.03655 . Бибкод : 2016arXiv160403655A . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Разрезание торта с полным знанием Дэвид Маккуиллан, 1999 г. (без рецензии)
^ Стивен Дж. Брамс и Алан Д. Тейлор (1999). Беспроигрышное решение: гарантия справедливого распределения акций для всех Norton в мягкой обложке. ISBN 0-393-04729-6
↑ « Лучшие способы разрезать торт» Стивена Дж. Брамса, Майкла А. Джонса и Кристиана Кламлера в «Уведомлениях Американского математического общества», декабрь 2006 г.

[steinhaus48-1] Штайнхаус, Хьюго (1948). «Проблема справедливого дележа». Эконометрика . 16 (1): 101–4. JSTOR 1914289 .

[:0-2] Jump up to: ^а ^б Брамс, Стивен Дж.; Тейлор, Алан Д. (1996). Справедливое разделение: от разрезания торта до разрешения споров . Издательство Кембриджского университета. ISBN 0-521-55644-9 .

[book-3] Jump up to: ^а ^б Робертсон, Джек; Уэбб, Уильям (1998). Алгоритмы разрезания торта: будьте честны, если можете . Натик, Массачусетс: АК Питерс. ISBN 978-1-56881-076-8 . LCCN 97041258 . ОЛ 2730675В .

[4] Янг, Х. Пейтон (1 января 1995 г.). Капитал . Издательство Принстонского университета. дои : 10.1515/9780691214054 . ISBN 978-0-691-21405-4 .

[5] Уолш, Тоби (2011). «Онлайн разрезание торта» . В Брафмане, Ронен И.; Робертс, Фред С.; Цукиас, Алексис (ред.). Конспекты лекций по информатике. Том. 6992. Берлин, Гейдельберг: Springer. стр. 292–305. дои : 10.1007/978-3-642-24873-3_22 . ISBN 978-3-642-24873-3 . S2CID 501890 . {{cite book}}: |journal= игнорируется ( помощь ) ; Отсутствует или пусто |title= ( помощь )

[6] Организация Объединенных Наций (10 декабря 1982 г.). «Приложение III: Основные условия поиска, разведки и разработки. Статья 8» . un.org . Архивировано из оригинала 14 сентября 2001 г.

[7] Гарднер, Мартин (1994). Мои лучшие математические и логические задачи . Дуврские публикации. ISBN 978-0486281520 .

[8] Кларрайх, Эрика (13 октября 2016 г.). «Математика разрезания торта» . Журнал Quanta (Scientific American) .

[9] АЗИЗ, ХАРИС; МАККЕНЗИ, САЙМОН (2017). «Дискретный и ограниченный протокол разрезания торта без зависти для любого количества агентов». arXiv : 1604.03655 . Бибкод : 2016arXiv160403655A . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[10] Разрезание торта с полным знанием Дэвид Маккуиллан, 1999 г. (без рецензии)

[11] Стивен Дж. Брамс и Алан Д. Тейлор (1999). Беспроигрышное решение: гарантия справедливого распределения акций для всех Norton в мягкой обложке. ISBN 0-393-04729-6

[12] ↑ « Лучшие способы разрезать торт» Стивена Дж. Брамса, Майкла А. Джонса и Кристиана Кламлера в «Уведомлениях Американского математического общества», декабрь 2006 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]