Задача дележа земли Хилла — Бека

Задача дележа земли Хилла — Бека — это вариант задачи справедливого разрезания торта, предложенный Тэдом Хиллом в 1983 году^[1].

Имеется территория D, смежная n странам. Каждая страна оценивает (по-своему) подмножества территории D. Страны хотят поделить территорию D справедливо между собой, где «справедливость» означает пропорциональный делёж. Кроме того, выделяемые каждой стране части должны быть связны и прилегать к выделяемой стране. Эти географические ограничения отличают задачу от классической задачи справедливого разрезания торта.

Формально, любая страна C_i должна получить непересекающиеся куски территории D, которые обозначим D_i, такие, что порции границы между C_i и D содержатся внутри ${\displaystyle C_{i}\cup D_{i}}$.

Имеются случаи, когда задача не может быть решена:

1. Если имеется одна точка, в которой сосредотачивается вся ценность земли (например, «святое место»), то очевидно, что территорию невозможно разделить пропорционально. Для предотвращения таких ситуаций мы предполагаем, что все страны назначают значение 0 всем отдельным точкам.
2. Если D является квадратом, имеются 4 страны, которые соприкасаются с 4 сторонами этого квадрата, а каждая страна видит всю ценность земли в границе противоположной стороны квадрата, тогда любое распределение, которое соединяет, скажем, северную страну с желаемой южной стороной, делает невозможным соединить восточную страну с желаемой западной стороной квадрата (если речь идет о двухмерной плоскости). Для предотвращения таких ситуаций мы предполагаем, что все страны предполагают нулевую цену границы D.

В 1983 году Хилл доказал, что если каждая отдельная точка в D имеет значение 0 для всех стран, а граница D имеет значение 0 для всех стран, существует пропорциональный делёж с удовлетворением ограничений смежности. Его доказательство касалось лишь существования, никакого алгоритма он не представил^[1].

Через четыре года Анатоль Бек описал протокол для достижения такого дележа^[2]. По сути, протокол является развитием протокола «последний уменьшивший». Протокол позволяет странам выдавать заявку на части территории D, отдаёт часть с наименьшей заявкой заявителю и делит остаток среди оставшихся ${\displaystyle n-1}$ стран. Некоторые вариации нужны, чтобы гарантировать выполнение ограничений смежности.

Если территория D односвязна, используется следующий алгоритм:

1. Находим отображение Римана h, которое отображает D в единичный круг, так что для всех стран значение любой окружности с центром в начале координат равно 0 и значение любого радиуса из начала координат равно 0 (существование такого отображения h доказывается доводами подсчёта).
2. Просим каждую страну нарисовать на единичном круге отображения h(D) диск с центром в начале координат (центр диска h(D)) и значением ${\displaystyle {\tfrac {1}{n}}}$. Это возможно сделать благодаря тому, что все окружности с центрами в начале координат имеют значение 0.
3. Находим диск D₁ с наименьшим радиусом r₁.

Есть два случая.

4. Если D₁ нарисован только одной страной, скажем C_i, то отдаём диск стране C_i. Его значение для других стран строго меньше ${\displaystyle {\tfrac {1}{n}}}$, так что мы можем отдать стране C_i небольшой дополнительный кусок, прилегающий к распределённому диску.

Чтобы это сделать нарисуем сектор, соединяющий D₁ с границей круга D. Пусть каждая страна (отличная от C_i) отрезает от этого сектора так, что значение объединения диска и сектора вместе не превосходят ${\displaystyle {\tfrac {1}{n}}}$. Это возможно благодаря условию, что значения всех радиусов из начала координат равны 0. Отдадим стране C_i объединение D₁ и усечённого сектора.

Оставшаяся территория односвязна и имеет значение по меньшей мере ${\displaystyle {\tfrac {n-1}{n}}}$ для оставшихся ${\displaystyle n-1}$ стран, так что делёж можно продолжить рекурсивно с шага 1.

Если часть D₁ была запрошена k>1 странами, то требуются некоторые более изощрённые аукционы, чтобы найти страну, которой мы можем отдать диск и связывающий сектор.

5. Выберем произвольную страну-победителя и назовём её объявителем, C₁. Пусть она добавит сектор, соединяющий D₁ с её текущей территорией и позволим другим странам отрезать от этого сектора, так что:

• Для любой проигравшей страны значение D₁ плюс отрезанный сектор не превосходят по значимости ${\displaystyle {\tfrac {1}{n}}}$ (это возможно, поскольку значение D₁ для них меньше ${\displaystyle {\tfrac {1}{n}}}$).
• Для любой выигравшей страны значение усечённого сектора меньше ${\displaystyle {\tfrac {1}{n}}}$.

6. Пусть каждая из победивших стран предложит новый радиус r (меньший, чем их начальное предложение), так что значение отрезанной части сектора плюс диск радиуса r оценивается ровно в ${\displaystyle {\tfrac {1}{n}}}$. Выберем наименьший такой диск D₂. Снова имеются два случая:

Если C₁ является одной из стран, подавшей заявку на D₂, то просто отдаём ей область D₂ (которая слегка меньше первоначальной заявки D₁) и соединяющий сектор. C₁ соглашается, что значение равно ${\displaystyle {\tfrac {1}{n}}}$, а другие страны согласны, что значение не превосходит ${\displaystyle {\tfrac {1}{n}}}$, так что мы можем продолжить рекурсивно с шага 1.

В противном случае C₁ соглашается, что полное значение D₂ и соединяющего сектора меньше, чем ${\displaystyle {\tfrac {1}{n}}}$. Все проигравшие должны также согласиться с этим, поскольку D₂ меньше, чем D₁. Таким образом, C₁ и все другие страны, которые согласны с этим, удаляются из множества победителей.

7. Среди оставшихся победителей выберем нового заявителя C₂. Пусть он добавит другой сектор, соединяющий D₂ с текущей территорией, и позволим другим странам усечь этот сектор как на шаге 5.

Заметим, что теперь территория D₂ связана с двумя территориями — C₁ и C₂. Это проблема, поскольку это делает оставшуюся территорию несвязной. Чтобы решить эту проблему, C₂ позволяется выбрать другой сектор, длина которого меньше 1, так что он не нарушает связность^[2]. Этот третий сектор снова обрезается всеми странами, как на шаге 5. В ответ от C₂ требуется отдать некоторую часть сектора, соединяющего D₂ с C₁, значение которой равно значению полученного третьего сектора.

Предложенное страной C₂ разрезание теперь содержит следующие части: D₂, сектор длиной 1, соединяющий D₂ с C₂, и два коротких сектора, которые не достигают границы D. Значение этой конструкции для C₂ равно ${\displaystyle {\tfrac {1}{n}}}$, для проигравших значение меньше чем ${\displaystyle {\tfrac {1}{n}}}$, а значение для других победителей не превосходит ${\displaystyle {\tfrac {1}{n}}}$.

Этот процесс продолжается с оставшимися победителями, пока не останется единственный победитель.

Если территория D k-связна^[англ.] с конечным k, делёж может быть осуществлён по индукции по k.

Если ${\displaystyle k=1,}$ D связно и может быть поделено с помощью протокола из предыдущей секции.

В противном случае ${\displaystyle (k>1)}$, обозначим внешнюю границу D как B₁, а внутренние границы как ${\displaystyle B_{2},\dots ,B_{k}}$.

Находим линию L, связывающую внешнюю границу B₁ с внутренней границей B_k, такую, что для всех стран значение этой линии L равно 0. Это сделать можно ввиду следующего аргумента. Имеется несчётное число попарно непересекающихся линий, связывающих B₁ и B_k, содержащихся в D. Но их мера в D конечна, так что число линий с положительной мерой должно быть счётно, а тогда есть линия с нулевой мерой.

Множество ${\displaystyle D\setminus L}$ является ${\displaystyle (k-1)}$-связным. Разобьём его рекурсивно, затем назначим L произвольно любой стране, с которой эта область граничит. Это не нарушает справедливости дележа, поскольку значение L для всех стран равно 0.

• Задача справедливого разрезания торта

• Hill T. P. Determining a Fair Border // The American Mathematical Monthly. — 1983. — Т. 90, вып. 7. — doi:10.2307/2975720. — JSTOR 2975720.
• Beck A. Constructing a Fair Border // The American Mathematical Monthly. — 1987. — Т. 94, вып. 2. — doi:10.2307/2322417. — JSTOR 2322417.
• Для других решений задачи см. статью Webb W. A. A Combinatorial Algorithm to Establish a Fair Border // European Journal of Combinatorics. — 1990. — Т. 11, вып. 3. — С. 301–304. — doi:10.1016/s0195-6698(13)80129-1.