Процедура «Движущийся нож» Барбанеля — Брамса

Процедура «Движущийся нож» Барбанеля — Брамса[1] — это процедура завистливого разрезания торта торта между тремя участниками[2]. Процедура делает только два разреза, так что каждый участник получает один цельный кусок.

Главное преимущество процедуры перед более ранней процедурой «Движущийся нож» Стромквиста заключается в том, что требуется только два движущихся ножа вместо четырёх. Также более ранняя процедура «Движущийся нож» Робертсона — Уэбба требует всего одного ножа, но она работает только для двумерных тортов, в то время как процедура Барбанеля — Брамса работает и на одномерном торте. Предложена американскими учёными Джулиусом Барбанелем (род. 1951) и Стивеном Брамсом (род. 1940) в 2004 году.

Процедура

Первоначально каждый участник делает пометки, показывающие часть торта слева, которая (по мнению участника) оценивается ровно в 1/3. Выбирается самая левая метка. Предположим, что эту метку сделала Алиса. Алису просят сделать тогда вторую метку, так что (по её мнению) значение торта слева от пометки равно в точности 2/3. Таким образом, теперь есть две метки, которые делят торт ровно на три части (по мнению Алисы).

Боба и Карла просят оценить два куска торта справа. Есть несколько возможных случаев[3]:

1. Боб и Карл предпочитают разные куски. В этом случае отдаём им по куску, которые они предпочитают, а Алисе отдаём крайний левый кусок, тем самым завершая делёж.

2. Боб и Карл предпочитают средний кусок. Алиса помещает два ножа по краям среднего куска и передвигает их внутрь данного куска так, чтобы два крайних куска после разрезания оставались в её глазах равными. Значение среднего куска уменьшается до тех пор, пока в некоторый момент Боб или Карл не посчитают его равным внешнему куску. Первый, кто так считает, должен воскликнуть «стоп» и получает внешний (равный по его мнению) кусок. Алиса получает второй внешний кусок, а промолчавший участник получает средний кусок.

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

Делёж «плохого» торта

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

См. также

Примечания
  1. Авторы называют эту процедуру «Squeezing procedure», то есть «Процедура сжимания»
  2. Barbanel, Brams, 2004, с. 251, Секция 2.
  3. Brams, 2006, с. 428.

Литература
  • Julius B. Barbanel, Steven J. Brams. Cake division with minimal cuts: Envy-free procedures for three persons, four persons, and beyond // Mathematical Social Sciences. — 2004. — Т. 48, вып. 3. — doi:10.1016/j.mathsocsci.2004.03.006.
  • Steven J. Brams. Fair Division // the oxford handbook of POLITICAL ECONOMY / (ред.) BARRY R. WEINGAST, DONALD A. WITTMAN. — OXFORD university press, 2006. — ISBN 0–19–927222-0.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.