Алгоритм метода Гамильтона

1. Найти стандартные квоты для всех представляемых групп.

2. Для каждой стандартной квоты найти целую и дробную часть (напомним, что целой частью любого числа z называется максимальное целое число, не превосходящее данное число z, а дробной частью – разница между числом z и его целой частью).

3. Каждой представляемой группе выделить число мест, равное целой части стандартной квоты данной группы.

4. Занумеровать все группы в порядке убывания дробных частей стандартных квот.

5. Добавить одно место к числу ранее выделенных для группы мест, начиная с 1-ой (в по-строенном порядке) группы.

6. Добавления на шаге 5 прекращаются, как только суммарная численность выделенных мест окажется равной числу n – числу мест в данном органе, представляющим рассмот-ренные группы ■

Пример 13. Продолжение примеров 11 и 12. Предположим, что консорциум решил рас-ширить совет до десяти членов. Использование метода Гамильтона для распределения мест в совете, состоящем из десяти членов, проиллюстрировано в таблице 11.

Таблица 11

Компания	Процент держа-телей акций	Пропорциональное число мест в совете	Число мест по ме-тоду Гамильтона
Наксон		0,47´10 = 4,7
Ароко		0,37´10 = 3,7
Евробайл		0,16´10 = 1,6
Всего		9,0

Заметим, что в данном случае Евробайл потерял одно место в совете, несмотря на то, что все доли держателей акций остались теми же, а число мест даже выросло ■

В 1881 Конгресс сделал удивительное открытие. Численный состав Палаты Представите-лей был увеличен с 299 человек до 300 (т.е. всего на одно место). При перераспределении мест методом Гамильтона оказалось, что Алабама вместо 8 мест получила 7, при расчётах, базирую-щихся на той же самой численности населения во всех штатах. Конечно, в этом нет ничего удивительного (тот же эффект имеет место в искусственном примере 13), но в Палате Предста-вителей США это случилось впервые. Более того, оказалось, что этот же эффект (получивший название Алабамского парадокса) повторился через несколько лет при увеличении численности Палаты Представителей с 359 до 360: одно место потерял Арканзас, то же самое случилось и со штатом Мэн.

Задание 4. Для данных, представленных в таблице 12, разделить пропорционально числу студентов заданное число преподавательских позиций по трём факультетам методом Гамильто-на.

Таблица 12

№ пп	Колледж	Образования	Свободных искусств	Бизнеса	Число позиций
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов
	Число студентов

3.2. Методы Джефферсона и Адамса.Эти два метода (связанные с именами 3-его и 2-го президентов США) используют вместо стандартного делителя (см. формулу (9)) его изменён-ное значение, называемое модифицированным делителем. При делении численности группы s на модифицированный делитель получаем модифицированную квоту (вместо стандартной квоты).

Идея метода Джефферсона такова: округлять все квоты (до целых чисел) в мéньшую сто-рону. Если сумма мест окажется меньше, чем заданное суммарное число мест n, то надо умень-шить модифицированный делитель (при этом, в силу формулы (9), модифицированные квоты увеличатся); если сумма мест окажется больше, чем суммарное число мест n, то надо увеличить модифицированный делитель (при этом, в силу формулы (9), модифицированные квоты умень-шатся). Подбираем модифицированный делитель так, чтобы сумма мест в конце концов оказа-лась равной заданному число мест n (это всегда возможно).

Идея метода Адамса такова: округлять все квоты (до целых чисел) в бóльшую сторону. Если сумма мест окажется больше, чем заданное суммарное число мест n, то надо увеличить модифицированный делитель (при этом, в силу формулы (9), модифицированные квоты умень-шатся); если сумма мест окажется меньше, чем суммарное число мест n, то надо уменьшить мо-дифицированный делитель (при этом, в силу формулы (9), модифицированные квоты увеличат-ся). Подбираем модифицированный делитель так, чтобы сумма мест в конце концов оказалась равной заданному число мест n (это всегда возможно).

Проиллюстрируем оба метода на следующем примере.

Пример 14. При указанных ниже данных разделим 16 преподавательских позиций методами Джефферсона и Адамса. Как уже говорилось, в методе Джефферсона вместо стандар-

Колледж	Образования	Свободных искусств	Бизнеса	Всего
Число студентов

тного делителя D = (см. формулу (9)) используется его изменённое значение D_М, называемое модифицированным делителем. При делении численности s на модифицированный делитель (вместо стандартного делителя) получаем модифицированную квоту x_M (вместо стандартной квоты x).

Метод Джефферсона состоит из следующих шагов.

Шаг 0.Найти стандартный делитель D = .

Шаг 1. Выбрать модифицированный делитель D_М мéньшим, чем стандартный делитель.

Шаг 2. По формуле x_M = , полученной из формулы (9) подстановкой модифицированного делителя D_М и модифицированной квоты x_M вместо стандартного делителя и стандартной кво-ты, находим модифицированную квоту для всех колледжей.

Шаг 3. Округлить все найденные на шаге 2 квоты в мéньшую сторону.

Шаг 4. Если сумма округлённых квот окажется меньше, чем заданное суммарное число пози-ций n, то уменьшить модифицированный делитель и перейти к шагу 2. Если сумма округлён-ных квот окажется больше, чем заданное суммарное число позиций n, то увеличить модифици-рованный делитель и перейти к шагу 2. Если сумма округлённых квот окажется равной задан-ному суммарному числу позиций n, то округлённые квоты и представляют собой искомое рас-пределение позиций.

Шаг 5. Остановка алгоритма.

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

Колледж	Образования	Свободных искусств	Бизнеса	Модифици- рованный делитель
Число студентов
Модифицированная квота	800:190≈4.21	1300:190≈6.84	1100:190≈5.79
Округлённая квота
Модифицированная квота	800:150≈5.33	1300:150≈8.67	1100:150≈7.33
Округлённая квота
Модифицированная квота	800:180≈4.44	1300:180≈7.22	1100:180≈6.11
Округлённая квота
Модифицированная квота	800:185≈4.32	1300:185≈7.03	1100:185≈5.95
Округлённая квота

Дадим необходимые пояснения. До начала заполнения таблицы выполняется шаг 0, т.е. вычис-ляется стандартный делитель D = . Поскольку в данном случае t = 3200, n = 16, то D = 200.

На шаге 1 положим D_М = 190 < 200 и запишем D_М = 190 в правую колонку таблицы сразу под за-головком столбца «Модифицированный делитель».

На шаге 2 произведём указанные в алгоритме вычисления и заполним верхнюю строку с именем «Модифицированная квота».

На шаге 3 округлим найденные на шаге 2 числа в сторону уменьшения и запишем их в следую-щую строку таблицы. Поскольку сумма 15 меньше заданного числа 16, то в соответствии с ша-гом 4 алгоритма уменьшим D_М, положив D_М = 150, и вернёмся к шагу 2.

На шаге 2 произведём указанные в алгоритме вычисления и заполним следующую строку с име-нем «Модифицированная квота».

На шаге 3 округлим найденные на шаге 2 числа в сторону уменьшения и запишем их в следую-щую строку таблицы. Поскольку сумма 20 больше заданного числа 16, то в соответствии с ша-гом 4 алгоритма увеличим D_М, положив D_М = 180, и вернёмся к шагу 2.

На шаге 2 произведём указанные в алгоритме вычисления и заполним следующую строку с име-нем «Модифицированная квота».

На шаге 3 округлим найденные на шаге 2 числа в сторону уменьшения и запишем их в следую-щую строку таблицы. Поскольку сумма 17 больше заданного числа 16, то в соответствии с ша-гом 4 алгоритма увеличим D_М, положив D_М = 185, и вернёмся к шагу 2.

На шаге 2 произведём указанные в алгоритме вычисления и заполним следующую строку с име-нем «Модифицированная квота».

На шаге 3 округлим найденные на шаге 2 числа в сторону уменьшения и запишем их в следую-щую строку таблицы. Поскольку сумма оказалась равной заданному числу 16, то в соответствии с шагом 5 алгоритма прекращаем вычисления. Последняя строка таблицы даёт распределение позиций методом Джефферсона

Конечно, неформальный подбор модифицированного делителя может показаться слишком уж неформальным. На самом же деле теория таких поисковых методов детально разработана. Известны точные оптимальные (по числу шагов) алгоритмы. Однако освоение этих методов оказывается значительно более трудоёмким, чем простой подбор, который всё же гарантиро-ванно (и обычно за 2-3 шага) приводит к правильному результату. Заметим также, что при вы-полнении подбора у нас всегда получается «вилка»: D_М = 190 даёт меньше позиций, чем надо, а D_М = 150 даёт больше позиций, чем надо. Это даёт гарантию, что «правильное» значение D_М будет больше, чем 150, но меньше, чем 190. Следующая точка 180 уменьшила интервал неопре-делённости: «правильное» значение D_М будет между 180 и 190. Действительно, очередное зна-чение 185 оказалось «правильным», т.е. приводящим к распределению всех позиций.

Метод Адамса отличается от метода Джефферсона только тем, что округления квот про-исходят путём увеличения до ближайшего целого, а не уменьшения, как в методе Джефферсо-на. Проиллюстрируем его использование на тех же исходных данных. Результаты вычислений будем записывать в аналогичную таблицу. Заметим, что стандартный делитель в этом случае является, естественно таким же самым, а в качестве начального значения возьмём D_М = 220 (бóльшее, чем стандартный делитель). Последовательные вычисления показаны в следующей таблице:

Колледж	Образования	Свободных искусств	Бизнеса	Модифици- рованный делитель
Число студентов
Модифицированная квота	800:220≈3.64	1300:220≈5.91	1100:220≈5
Округлённая квота
Модифицированная квота	800:210≈3.81	1300:210≈6.19	1100:210≈5.24
Округлённая квота
Модифицированная квота	800:215≈3.73	1300:215≈6.05	1100:215≈5.12
Округлённая квота
Модифицированная квота	800:218≈3.67	1300:218≈5.96	1100:218≈5.05
Округлённая квота

Обратим внимание, что распределения позиций, найденные методом Джефферсона и методом Адамса, не совпадают. Это не ошибка: речь ведь не идёт о разных методах решения одной и той же формальной задачи, а о разных формализациях самого понятия справедливости ■

Задание 5. Для данных, представленных в таблице 12, разделить пропорционально числу студентов заданное число преподавательских позиций по трём факультетам методом Джеффер-сона ■

Задание 6. Для данных, представленных в таблице 12, разделить пропорционально числу студентов заданное число преподавательских позиций по трём факультетам методом Адамса ■

Задание 7. Сравнить результаты деления позиций всеми тремя рассмотренными методами для одних и тех же исходных данных (вариантов), сведя ответы в таблицу. Есть ли варианты, когда все три ответа совпадут и когда все три ответа окажутся разными? ■

3.3. Метод Хантингтона-Хилла. Этот метод состоит в следующем. Обозначим через s_p численность p-ой группы, через k_p- число мест, выделенных этой группе в представительном органе. Отношение s_p к k_p представляет собой среднее число членов группы, приходящееся на одного представителя от данной группы. В идеале все эти числа должны совпадать; в реальнос-ти это невозможно, и их следует сделать как можно ближе друг к другу, в чём и состоит задача пропорционального представительства.

Положим b_p = (p = 1, ..., m), где m-число групп. Пусть i и j- номера двух групп. По-ложим

M = min{b_i, b_j}, (10)

a_ij = (i, j = 1, ..., m; i ≠ j). (11)

Величина a_ij называется относительной несправедливостью для групп i и j. Распределение Хантингтона-Хилла определяется как такое распределение (т.е. набор чисел k₁, ..., k_m, в сумме равных n, где n-общее число мест), для которого величина принимает минимально возможное значение. Таким образом, распределение Хантингтона-Хилла минимизирует макси-мальную относительную несправедливость. Именно такой способ распределения мест между штатами в Палате Представителей принят в США с 1941 года, когда президент Франклин Дела-но Рузвельт подписал соответствующий закон.

На первый взгляд может показаться, что нахождение распределения Хантингтона-Хилла является вычислительно сложной задачей, требующей анализа всех возможных распределений и вычисления для каждого из них относительной несправедливости. Однако есть достаточно простой алгоритм, основанный на последовательном выделении мест для различных групп. Да-дим его описание.