«Распределите целое число мест в парламенте между штатами (или политическими партиями) справедливо и пропорционально их численности населения».
Столкнувшись с такой задачей, почти каждый человек вспомнит школьную арифметику пропорций и округления: сначала разделим общую численность населения страны на общее число мест в парламенте, чтобы найти «стандартный делитель» (число жителей на один мандат), а затем разделим население каждого штата на этот делитель. Поскольку при делении возникают дробные числа вроде $7{,}73$ или $1{,}36$ места, сначала отдадим каждому штату его целую часть ($7$ и $1$), а оставшиеся места распределим по одному между штатами с наибольшими дробными остатками ($,73$, $,36$ и т. д.). Разве может существовать более естественный и безупречно справедливый метод?
Однако в 1880 году главный клерк Бюро переписи населения США Чарльз Ситон (Charles W. Seaton), рассчитывая распределение мест в Палате представителей именно по этому «самому естественному» правилу (методу Гамильтона, или методу наибольшего остатка / Хэйра — Нимейера), обнаружил леденящую душу аномалию: когда общее число мест в Палате представителей было увеличено всего на одно место — с $299$ до $300$ мест (при неизменной численности населения всех штатов!), — представительство штата Алабама сократилось с $8$ до $7$ мест!
Общий пирог увеличился, но доля участника уменьшилась: вслед за парадоксом Алабамы были открыты парадокс населения (быстрорастущий штат теряет место в пользу медленно растущего штата) и парадокс новых штатов (присоединение нового штата ровно с причитающимся ему числом мест приводит к перераспределению мандатов между старыми штатами). Наконец, в 1982 году математики Мишель Балинский (Michel Balinski) и Пейтон Янг (H. Peyton Young) доказали знаменитую теорему о невозможности Балинского — Янга: математически не существует метода распределения мандатов, который одновременно удовлетворял бы правилу квоты и монотонности (отсутствию парадоксов).
1. Конституционный кризис 1792 года: Гамильтон против Джефферсона и первое президентское вето
Статья I, раздел 2 Конституции США 1787 года гласила, что представители распределяются между штатами «соответственно их численности», но не более одного представителя на каждые $30\,000$ жителей. После первой переписи 1790 года ($P = 3\,615\,920$ человек в $15$ штатах) Конгресс принял законопроект с $H = 120$ местами (стандартный делитель $D = P/H = 30\,132{,}67$).
Министр финансов Александр Гамильтон предложил метод наибольшего остатка (метод Гамильтона): сначала раздать целые части $\lfloor p_i / D \rfloor$ (всего $112$ мест), а оставшиеся $R = 8$ мест отдать $8$ штатам с наибольшими дробными остатками. Госсекретарь Томас Джефферсон и президент Джордж Вашингтон (оба из Виргинии) выступили категорически против: мало того что крупнейшая Виргиния осталась без дополнительного мандата, так ещё и малые штаты, получившие место за счёт округления вверх (например, Делавэр с населением $55\,540$ человек и $2$ местами), оказались представлены из расчёта один депутат на $27\,770$ жителей — в прямое нарушение конституционного порога в $30\,000$!
Джефферсон предложил альтернативу — метод Джефферсона (известный в Европе как метод Д’Ондта): выбрать общий делитель $x$ (например, $x = 33\,000$) и отбрасывать все дробные части ($a_i = \lfloor p_i / x \rfloor$), подбирая $x$ так, чтобы сумма целых частей равнялась $H$. 5 апреля 1792 года президент Вашингтон применил первое в истории США президентское вето, отклонив закон Гамильтона из-за спора о математическом алгоритме округления!
2. Математическая постановка задачи и правило квоты (Quota Rule)
Пусть имеются $s \ge 2$ штатов с вектором населения $\mathbf{p} = (p_1, \dots, p_s)$, общим населением $P = \sum_{i=1}^s p_i$ и общим числом мест $H \in \mathbb{Z}_{>0}$. Стандартный делитель $D$ и точная квота $q_i$ штата $i$ определяются как:
$$D = \frac{P}{H}, \qquad q_i = \frac{p_i}{D} = H \cdot \frac{p_i}{P}, \qquad \sum_{i=1}^s q_i = H$$При округлении вещественной квоты $q_i$ до целого числа мандатов $a_i \in \mathbb{Z}_{\ge 0}$ ($\sum_{i=1}^s a_i = H$) минимальная аксиома справедливости требует, чтобы каждый штат получал либо свою нижнюю квоту $\lfloor q_i \rfloor$, либо верхнюю квоту $\lceil q_i \rceil$. Это правило квоты (Quota Rule):
$$\lfloor q_i \rfloor \le a_i \le \lceil q_i \rceil \quad (\forall i \in \{1, 2, \dots, s\})$$Метод Гамильтона (наибольшего остатка / Хэйра — Нимейера) представляет $q_i = \lfloor q_i \rfloor + r_i$, где $r_i \in [0, 1)$, выделяет каждому штату $\lfloor q_i \rfloor$ мест, а оставшиеся $R = H - \sum \lfloor q_i \rfloor = \sum r_i$ мест отдаёт $R$ штатам с наибольшими остатками $r_i$:
$$q_i = \lfloor q_i \rfloor + r_i \quad (0 \le r_i < 1), \qquad R = H - \sum_{i=1}^s \lfloor q_i \rfloor = \sum_{i=1}^s r_i \in \{0, 1, \dots, s-1\}$$$$a_i = \begin{cases} \lfloor q_i \rfloor + 1 & (\text{if } r_i \text{ is among the } R \text{ largest remainders}) \\ \lfloor q_i \rfloor & (\text{otherwise}) \end{cases}$$По построению метод Гамильтона выполняет правило квоты в $100\%$ случаев.
3. Полная анатомия трёх классических парадоксов распределения
В 1880–1907 годах реальные расчёты переписей населения США выявили три фундаментальных парадокса метода Гамильтона:
flowchart TD
H["Метод Гамильтона (Наибольший остаток / Хэйра — Нимейера)<br/>На 100% гарантирует правило квоты ⌊q_i⌋ ≤ a_i ≤ ⌈q_i⌉"]
P1["1. Парадокс Алабамы (1880)<br/>Общее число мест H растёт, но штат теряет мандат<br/>(Нарушение монотонности размера палаты)"]
P2["2. Парадокс населения (1900)<br/>Быстрорастущий штат теряет мандат в пользу медленно растущего<br/>(Нарушение популяционной монотонности)"]
P3["3. Парадокс новых штатов (1907)<br/>Вступление нового штата со своими местами меняет мандаты старых штатов<br/>(Нарушение согласованности / консистентности)"]
CAUSE["Математическая причина: Точная квота q_i = H·(p_i/P) растёт со скоростью,<br/>пропорциональной доле штата p_i/P, поэтому остатки r_i крупных штатов обгоняют малые"]
H --> P1
H --> P2
H --> P3
P1 --> CAUSE
P2 --> CAUSE
P3 --> CAUSE
3.1 Парадокс Алабамы (1880) и полное доказательство на модели 3 штатов ($H = 10 \to 11$)
В 1880 году при увеличении $H$ с $299$ до $300$ квота Алабамы выросла лишь на $+0{,}025$ ($7{,}646 \to 7{,}671$), тогда как более крупные Техас ($9{,}640 \to 9{,}672$, $+0{,}032$) и Иллинойс ($18{,}640 \to 18{,}702$, $+0{,}062$) нарастили свои остатки быстрее и одновременно обошли Алабаму. Проверим это на точной модели из $3$ штатов ($P = 1000$):
| Штат | Население $p_i$ | Квота $q_i$ ($H=10$) | Целая часть и остаток $r_i$ ($H=10$) | Места $a_i$ ($H=10$) | Квота $q_i'$ ($H=11$) | Целая часть и остаток $r_i'$ ($H=11$) | Места $a_i'$ ($H=11$) |
|---|---|---|---|---|---|---|---|
| Штат A | $433$ | $4{,}330$ | $4$ ($r_A = 0{,}330$: 2-е место) | $4$ места | $4{,}763$ | $4$ ($r_A' = \mathbf{0{,}763}$: 1-е место) | $5$ мест ($+1$) |
| Штат B | $431$ | $4{,}310$ | $4$ ($r_B = 0{,}310$: 3-е место) | $4$ места | $4{,}741$ | $4$ ($r_B' = \mathbf{0{,}741}$: 2-е место) | $5$ мест ($+1$) |
| Штат C | $136$ | $1{,}360$ | $1$ ($r_C = \mathbf{0{,}360}$: 1-е место) | $2$ места | $1{,}496$ | $1$ ($r_C' = 0{,}496$: 3-е место) | $1$ место ($-1$) |
| Итого | $1000$ | $10{,}000$ | Сумма целых $= 9$ ($R=1$) | $10$ мест | $11{,}000$ | Сумма целых $= 9$ ($R'=2$) | $11$ мест |
При переходе $H = 10 \to 11$ квоты крупных штатов A и B прирастают на $+0{,}433$ и $+0{,}431$, а малого штата C — лишь на $+0{,}136$: остатки A и B ($0{,}763$ и $0{,}741$) обгоняют $r_C' = 0{,}496$, и штат C падает с $2$ мест до $1$ места (нарушение монотонности размера палаты).
3.2 Парадокс населения (1900) и парадокс новых штатов (1907)
- Парадокс населения: Между 1890 и 1900 годами население Виргинии выросло на $+12{,}0\%$, а Мэна — лишь на $+5{,}0\%$, но Виргиния потеряла мандат в пользу Мэна. В нашей модели ($H = 10, P = 1000$): в момент 1 $p_A = 427, p_B = 435, p_C = 138 \implies$ места $(4, 4, 2)$, так как $r_C = 0{,}380$ максимален. В момент 2 штат C вырастает на $+8{,}70\%$ ($138 \to 150$), штат B — на $+6{,}90\%$ ($435 \to 465$), а штат A сокращается ($427 \to 385$). Хотя темп роста C выше, чем у B, абсолютный прирост квоты крупного штата B ($+0{,}300 \implies r_B' = 0{,}650$) больше, чем у малого C ($+0{,}120 \implies r_C' = 0{,}500$), а квота A пробивает сверху целую границу $4$ ($q_A' = 3{,}850 \implies r_A' = 0{,}850$). В итоге самый быстрорастущий штат C теряет место ($2 \to 1$) в пользу B ($4 \to 5$)!
- Парадокс новых штатов: В 1907 году присоединение Оклахомы с $5$ мандатами ($H: 386 \to 391$) привело к потере места Нью-Йорком в пользу Мэна. В модели из $2$ штатов ($H = 10, P = 1000$, $p_A = 842, p_B = 158 \implies a_A = 8, a_B = 2$) вступление нового штата C ($p_C = 165$) с его законными $2$ местами ($H' = 12, P' = 1165$) снижает стандартный делитель со $100$ до $97{,}083$. Все квоты умножаются на $1{,}03004$: квота крупного штата A растёт на $+0{,}253$ ($8{,}673$, остаток $0{,}673$) и обгоняет остаток малого штата B ($1{,}627$, остаток $0{,}627$), давая $(9, 1, 2)$!
4. Единая теория методов делителей (наибольших средних) и путевых функций $d(n)$
Методы делителей делят население $p_i$ на регулируемый общий делитель $x > 0$ и округляют частное $q = p_i / x$ с помощью монотонной путевой функции (Signpost Function) $d(n) \in [n, n+1]$:
$$[q]_d = n \iff d(n-1) \le q \le d(n), \qquad a_i = \left[\frac{p_i}{x}\right]_d, \qquad \sum_{i=1}^s a_i = H$$Выражая $x$ из неравенства $d(a_i - 1) \le p_i / x \le d(a_i)$, получаем полную эквивалентность методу наибольших средних (значений приоритета):
$$\frac{p_i}{d(a_i)} \le x \le \frac{p_i}{d(a_i - 1)} \quad \Longleftrightarrow \quad \text{Priority}(i, n) = \frac{p_i}{d(n)}$$Выделение $H$ мест в точности эквивалентно присуждению мандатов $H$ наибольшим значениям приоритета $\text{Priority}(i, n) = \frac{p_i}{d(n)}$. Поскольку глобальный рейтинг не меняется при росте $H$, а отношение приоритетов двух штатов удовлетворяет условию:
$$\frac{p_i'}{p_j'} \ge \frac{p_i}{p_j} \implies \frac{p_i' / d(n)}{p_j' / d(m)} = \frac{p_i'}{p_j'} \cdot \frac{d(m)}{d(n)} \ge \frac{p_i}{p_j} \cdot \frac{d(m)}{d(n)} = \frac{p_i / d(n)}{p_j / d(m)}$$все методы делителей абсолютно защищены от всех трёх парадоксов!
Сравнение пяти исторических методов делителей
| Название метода (Избирательный аналог) | Авторы и год | Путевая функция $d(n)$ | Последовательность $d(0), d(1), d(2), \dots$ | Мин. мест | Смещение по размеру и критерий оптимизации | Поведение относительно правила квоты |
|---|---|---|---|---|---|---|
| 1. Метод Джефферсона (Д’Ондта) | Jefferson (1792) D’Hondt (1878) | $n + 1$ (Округление вниз) | $1, 2, 3, 4, \dots$ | $0$ мест | Сильно благоприятствует крупным штатам/партиям | Нарушает верхнюю квоту ($a_i > \lceil q_i \rceil$) |
| 2. Метод Вебстера (Сент-Лагю) | Webster (1832) Sainte-Laguë (1910) | $n + 0{,}5$ (Среднее арифм.) | $0{,}5, \; 1{,}5, \; 2{,}5, \dots$ (или $1, 3, 5, \dots$) | $0$ мест | Полностью нейтрален к размеру штатов | Может (редко) нарушать верхнюю и нижнюю квоты |
| 3. Хантингтона — Хилла (Равных пропорций) | Hill (1911) Huntington (1921) | $\sqrt{n(n+1)}$ (Среднее геом.) | $0, \sqrt{2}, \sqrt{6}, \sqrt{12}, \dots$ | $1$ место | Минимизирует относительное неравенство $T_{ij}$; Палата представителей США с 1941 г. | Может нарушать верхнюю и нижнюю квоты |
| 4. Метод Дина (Среднее гармоническое) | J. Dean (1832) | $\frac{2n(n+1)}{2n+1}$ (Среднее гарм.) | $0, \frac{4}{3}, \frac{12}{5}, \frac{24}{7}, \dots$ | $1$ место | Минимизирует абсолютную разность размеров округов $p_i/a_i$ | Может нарушать верхнюю и нижнюю квоты |
| 5. Метод Адамса (Наименьших делителей) | J. Q. Adams (1832) | $n$ (Округление вверх) | $0, 1, 2, 3, \dots$ | $1$ место | Сильно благоприятствует малым штатам | Нарушает нижнюю квоту ($a_i < \lfloor q_i \rfloor$) |
Согласно классическому неравенству о средних арифметическом, геометрическом и гармоническом (AM-GM-HM):
$$T_{ij} = \frac{a_i / p_i}{a_j / p_j} - 1, \qquad d(n) = \sqrt{n(n+1)}$$$$n < \underbrace{\frac{2n(n+1)}{2n+1}}_{\text{Dean (HM)}} < \underbrace{\sqrt{n(n+1)}}_{\text{Huntington-Hill (GM)}} < \underbrace{n + 0.5}_{\text{Webster (AM)}} < n + 1$$5. Теорема о невозможности Балинского — Янга (1982)
Даже абсолютно симметричный метод Вебстера / Сент-Лагю ($d(n) = n + 0{,}5$, обычное округление до ближайшего целого) нарушает как нижнюю, так и верхнюю квоту:
- Нарушение нижней квоты ($H = 10, P = 1000$): Пусть крупный штат A имеет $p_A = 832$ ($q_A = 8{,}320$, нижняя квота $8$ мест), а три малых штата B, C, D — по $p_i = 56$ ($q_i = 0{,}560$). При делителе $x = 111$ малые штаты получают $56/111 \approx 0{,}5045 > 0{,}5$ и округляются вверх до $1$ места каждый (всего $3$ места), тогда как штат A получает $832/111 \approx 7{,}4955 < 7{,}5$ и округляется вниз до $7$ мест — нарушая свою нижнюю квоту в $8$ мест!
- Нарушение верхней квоты ($H = 10, P = 1000$): Пусть крупный штат A имеет $p_A = 795$ ($q_A = 7{,}950$, верхняя квота $8$ мест), а пять малых штатов B–F — по $p_i = 41$ ($q_i = 0{,}410$). При $x = 83$ все пять малых штатов получают $41/83 \approx 0{,}4940 < 0{,}5$ ($0$ мест), а штат A получает $795/83 \approx 9{,}5783 > 9{,}5$ и забирает все $10$ мест — превышая верхнюю квоту на $2$ мандата!
В 1982 году Балинский и Янг доказали фундаментальную теорему:
- Теорема 1 (Характеризация методов делителей): Анонимный и однородный метод распределения удовлетворяет популяционной монотонности тогда и только тогда, когда он является методом делителей.
- Теорема 2 (Теорема о невозможности Балинского — Янга, 1982): При числе штатов $s \ge 4$ и числе мест $H \ge 7$ не существует метода распределения мандатов, который одновременно удовлетворял бы популяционной монотонности и правилу квоты ($\lfloor q_i \rfloor \le a_i \le \lceil q_i \rceil$).
Изменение общего делителя $x$ умножает все точные квоты на один и тот же множитель $\lambda = D/x$ ($p_i/x = \lambda q_i$), поэтому абсолютное смещение квоты крупного штата $\Delta q_A = |1 - \lambda| q_A$ растёт пропорционально его размеру $q_A$, неизбежно пересекая целые границы.