Проблема разделения земель Хилла-Бека

Следующий вариант задачи о разрезании торта был предложен Тедом Хиллом в 1983 году. ^{[ 1 ]}

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

Формально каждая страна C _i должна получить непересекающийся кусок D , отмеченный D _i , такой, чтобы часть границы между C _i и D находилась внутри C _i ∪ D _i .

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

Бывают случаи, в которых проблему решить невозможно:

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

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

Алгоритм

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

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

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

1. Найдите риманово отображение h , которое отображает D в единичный круг , такое, что для всех стран значение каждого круга с центром в начале координат равно 0, а значение каждого радиуса от начала координат равно 0 (существование такого h доказывается счетным рассуждением).

2. Попросите каждую страну нарисовать на карте единичного диска h ( D ) диск с центром в начале координат и значением 1/ n . Это возможно благодаря тому, что значение всех кругов с центром в начале координат равно 0.

3. Найдите диск D ₁ наименьшего радиуса r ₁ .

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

Единственный победитель

4. Если D ₁ вытащила только одна страна, скажем C _i , то отдайте этот диск C _i . Его значение для других стран строго меньше 1/ n , поэтому мы можем дать C _i небольшой дополнительный фрагмент, соединяющий его с выделенным ему диском.

Для этого нарисуйте сектор, соединяющий D ₁ с изображением границы между C _i и D . Пусть каждая страна (кроме C _i ) обрежет этот сектор так, чтобы все страны оценили объединение диска и сектора не более чем 1/ n . Это возможно благодаря условию, что значение всех радиусов от начала координат равно 0. Выделим C _i объединение D ₁ и обрезанного сектора.

Остаток является односвязным и имеет значение не менее ( n - 1)/ n для оставшихся n - 1 стран, поэтому на шаге 1 деление можно продолжить рекурсивно.

Множество победителей

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

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

Для каждой страны-непобедителя значение D ₁ плюс урезанный сектор не превышает 1/ n (это возможно, поскольку значение D ₁ для них меньше 1/ n ).
Для каждой страны-победителя стоимость одного урезанного сектора меньше 1/ n .

6. Пусть каждая из стран-победителей предложит новый радиус r (меньший, чем ее первая ставка), такой, чтобы значение обрезанного сектора плюс диск радиуса r составляло ровно 1/ n . Выберите самый маленький такой диск D ₂ . И снова есть два случая:

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

противном случае C1 _{соглашается ,} что общее значение D2 _В плюс соединительный сектор меньше 1/ n . Все непобедители также должны согласиться с этим, поскольку D ₂ меньше D ₁ . Таким образом, С ₁ и все остальные страны, согласившиеся на это, исключаются из числа победителей.

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

что теперь D2 _, подключен к двум разным территориям C1 _– и C2 _{Обратите внимание} . Это проблема, потому что это делает оставшуюся территорию отключенной. Чтобы решить эту проблему, C ₂ разрешается занять другой сектор, на этот раз длиной меньше 1, чтобы это не повредило соединению. ^{[ 2 ]} Этот третий сектор снова обрезается всеми странами, как и на шаге 5. Взамен C ₂ должен отказаться от некоторой части сектора, соединяющего D ₂ с C ₁ , стоимость которого равна стоимости полученного им третьего сектора.

Распределение кандидатов C ₂ теперь содержит следующие части: D ₂ , один сектор длиной 1, соединяющий D ₂ с C ₂ , и два коротких сектора, которые не достигают границы D . Ценность этой конструкции для C ₂ равна 1/ n , ее ценность для непобедителей меньше 1/ n , а ее ценность для остальных победителей не превышает 1/ n .

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

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

Если территория D с k -связна конечным k , то деление можно провести индукцией по k .

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

В противном случае ( k > 1) обозначьте внешнюю границу D буквой B ₁ , а ее внутренние границы - B ₂ , ..., B _k .

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

Множество D \ L ( k − 1)-связно. Разделите его рекурсивно, а затем произвольно присвойте L любой соседней с ним стране. Это не влияет на справедливость распределения, поскольку значение L равно 0 для всех стран.

См. также

Ссылки

^ Jump up to: ^а ^б Хилл, Т.П. (1983). «Определение справедливой границы» . Американский математический ежемесячник . 90 (7): 438–442. дои : 10.2307/2975720 . JSTOR 2975720 .
^ Jump up to: ^а ^б Бек, А. (1987). «Построение справедливой границы». Американский математический ежемесячник . 94 (2): 157–162. дои : 10.2307/2322417 . JSTOR 2322417 .

Дополнительное решение проблемы см.: Уэбб, Вашингтон (1990). «Комбинаторный алгоритм установления справедливой границы». Европейский журнал комбинаторики . 11 (3): 301–304. дои : 10.1016/s0195-6698(13)80129-1 .

[Hill-1] Jump up to: ^а ^б Хилл, Т.П. (1983). «Определение справедливой границы» . Американский математический ежемесячник . 90 (7): 438–442. дои : 10.2307/2975720 . JSTOR 2975720 .

[Beck-2] Jump up to: ^а ^б Бек, А. (1987). «Построение справедливой границы». Американский математический ежемесячник . 94 (2): 157–162. дои : 10.2307/2322417 . JSTOR 2322417 .

[ 1 ]

[ 2 ]