Задача дележа земли Хилла — Бека
Задача дележа земли Хилла — Бека — это вариант задачи справедливого разрезания торта, предложенный Тэдом Хиллом в 1983 году.
Постановка задачи
Имеется территория D, смежная n странам. Каждая страна оценивает (по-своему) подмножества территории D. Страны хотят поделить территорию D справедливо между собой, где «справедливость» означает пропорциональный делёж. Кроме того, выделяемые каждой стране части должны быть связны и прилегать к выделяемой стране. Эти географические ограничения отличают задачу от классической задачи справедливого разрезания торта.
Формально, любая страна Ci должна получить непересекающиеся куски территории D, которые обозначим Di, такие что порции границы между Ci и D содержится внутри C i ∪ D i {displaystyle C_{i}cup D_{i}} .
Невозможность и возможность
Имеются случаи, когда задача не может быть решена:
1. Если имеется одна точка, в которой сосредотачивается вся ценность земли (например, «святое место»), то очевидно, что территорию невозможно разделить пропорционально. Для предотвращения таких ситуаций мы предполагаем, что все страны назначают значение 0 всем отдельным точкам.
2. Если D является квадратом, имеется 4 страны, которые соприкасаются с 4 сторон этот квадрат, а каждая страна видит всю ценность земли в границе противоположной стороны квадрата, тогда любое распределение, которое соединяет, скажем, северную страну с желаемой южной стороной, делает невозможным соединить восточную страну с желаемой западной стороной квадрата (если мы говорим о двухмерной плоскости). Для предотвращения таких ситуаций мы предполагаем, что все страны предполагают нулевую цену границы D.
В 1983 году Хилл доказал, что если каждая отдельная точка в D имеет значение 0 для всех стран, а граница D имеет значение 0 для всех стран, существует пропорциональный делёж с удовлетворением ограничений смежности. Его доказательство касалось лишь существования, никакого алгоритма он не представил.
Алгоритм
Через четыре года Анатоль Бек описал протокол для достижения такого дележа. По сути, протокол является развитием протокола «последний уменьшивший». Протокол позволяет странам выдавать заявку на части территории D, отдаёт часть с наименьшей заявкой заявителю и делит остаток среди оставшихся n − 1 {displaystyle n-1} стран. Некоторые вариации нужны, чтобы гарантировать выполнение ограничений смежности.
Односвязная территория
Если территория D односвязна, используется следующий алгоритм.
1. Находим a отображение Римана h, которое отображает D в единичный круг, так что для всех стран значение любой окружности с центом в начале координат равно 0 и значение любого радиуса из начала координат равно 0 (существование такого отображения h доказывается доводами подсчёта).
2. Просим каждую страну нарисовать на единичном круге отображения h(D) диск с центром в начале координат (центр диска h(D)) и значением 1 n {displaystyle { frac {1}{n}}} . Это возможно сделать благодаря тому, что все окружности с центрами в начале координат имеют значение 0.
3. Находим диск D1 с наименьшим радиусом r1.
Есть два случая.
Одиночный победитель
4. Если D1 нарисован только одной страной, скажем Ci, то отдаём диск стране Ci. Его значение для других стран строго меньше 1 n {displaystyle { frac {1}{n}}} , так что мы можем отдать стране Ci небольшой дополнительный кусок, прилегающий к распределённому диску.
Чтобы это сделать, нарисуем сектор, соединяющий D1 с границей круга D. Пусть каждая страна (отличная от Ci) отрезает от этого сектора так, что значение объединения диска и сектора вместе не превосходят 1 n {displaystyle { frac {1}{n}}} . Это возможно благодаря условию, что значения всех радиусов из начала координат равны 0. Отдадим стране Ci объединение D1 и усечённого сектора.
Оставшаяся территория односвязна и имеет значение по меньшей мере n − 1 n {displaystyle { frac {n-1}{n}}} для оставшихся n − 1 {displaystyle n-1} стран, так что делёж можно продолжить рекурсивно с шага 1.
Несколько победителей
Если часть D1 была запрошена k>1 странами, то требуются некоторые более изощрённые аукционы, чтобы найти страну, которой мы можем отдать диск и связывающий сектор.
5. выберем произвольную страну-победителя и назовём её объявителем, C1. Пусть она добавит сектор, соединяющий D1 с её текущей территорией и позволим другим странам отрезать от этого сектора, так что:
- Для любой проигравшей страны значение D1 плюс отрезанный сектор не превосходят по значимости 1 n {displaystyle { frac {1}{n}}} (это возможно, поскольку значение D1 для них меньше 1 n {displaystyle { frac {1}{n}}} ).
- Для любой выигравшей страны значение усечённого сектора меньше 1 n {displaystyle { frac {1}{n}}} .
6. Пусть каждая из победивших стран предложит новый радиус r (меньший, чем их начальное предложение), так что значение отрезанной части сектора плюс диск радиуса r оценивается ровно в 1 n {displaystyle { frac {1}{n}}} . Выберем наименьший такой диск D2. Снова имеется две случая:
Если C1 является одной из стран, подавшей заявку на D2, то просто отдаём ей область D2 (которая слегка меньше первоначальной заявки D1) и соединяющий сектор. C1 соглашается, что значение равно 1 n {displaystyle { frac {1}{n}}} , а другие страны согласны, что значение не превосходит 1 n {displaystyle { frac {1}{n}}} , так что мы можем продолжить рекурсивно с шага 1.
В противном случае C1 соглашается, что полное значение D2 и соединяющего сектора меньше, чем 1 n {displaystyle { frac {1}{n}}} . Все проигравшие должны также согласиться с этим, поскольку D2 меньше, чем D1. Таким образом, C1 и все другие страны, которые согласны с этим, удаляются из множества победителей.
7. Среди оставшихся победителей выберем нового заявителя C2. Пусть он добавит другой сектор, соединяющей D2 с текущей территорией и позволим другим странам усечь этот сектор как на шаге 5.
Заметим, что теперь территория D2 связана с двумя территориями – C1 и C2. Это проблема, поскольку это делает оставшуюся территорию несвязной. Чтобы решить эту проблему, C2 позволяется выбрать другой сектор, длина которого меньше 1, так что он не нарушает связность. Этот третий сектор снова обрезается всеми странами как на шаге 5. В ответ от C2 требуется отдать некоторую часть сектора, соединяющего D2 с C1, значение которой равно значению полученного третьего сектора.
Предложенное страной C2 разрезание теперь содержит следующие части: D2, сектор длиной 1, соединяющий D2 с C2, и два коротких сектора, которые не достигают границы D. Значение этой конструкции для C2 равно 1 n {displaystyle { frac {1}{n}}} , для проигравших значение меньше чем 1 n {displaystyle { frac {1}{n}}} , а значение для других победителей не превосходит 1 n {displaystyle { frac {1}{n}}} .
Этот процесс продолжается с оставшимися победителями, пока не останется единственный победитель.
Конечно связная территория
Если территория D k-связна с конечным k, делёж может быть осуществлён по индукции по k.
Если k = 1 , {displaystyle k=1,} D связно и может быть поделено с помощью протокола из предыдущей секции.
В противном случае ( k > 1 ) {displaystyle (k>1)} , обозначим внешнюю границу D как B1, а внутренние границы как B 2 , … , B k {displaystyle B_{2},dots ,B_{k}} .
Находим линию L, связывающую внешнюю границу B1 с внутренней границей Bk, такую что для всех стран значение этой линии L равно 0. Это сделать можно ввиду следующего аргумента. Имеется несчётное число попарно непересекающихся линий, связывающих B1 и Bk, содержащихся в D. Но их мера в D конечна, так что число линий с положительной мерой должно быть счётно, а тогда есть линия с нулевой мерой.
Множество D ∖ L {displaystyle Dsetminus L} является ( k − 1 ) {displaystyle (k-1)} -связным. Разобъём его рекурсивно, затем назначим L произвольно любой стране, с которой эта область граничит. Это не нарушает справедливости дележа, поскольку значение L для всех стран равно 0.
