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

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

Постановка задачиПравить

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

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

Невозможность и возможностьПравить

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

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

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

АлгоритмПравить

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

Односвязная территорияПравить

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

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

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

Одиночный победительПравить

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

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

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

Несколько победителейПравить

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

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

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

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

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

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

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

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

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

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

Конечно связная территорияПравить

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

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

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

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

Множество $D\setminus <!--\; \setminus \; -->L$$D\setminus L$  является $(k-<!--\; -\; -->1)$$(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.