議会の議席配分

現実世界のアルゴリズムの例をもう一つ示しましょう。このアルゴリズムは政治的に非常に重要です。アメリカ合衆国憲法第 1 条第 2 節は次のことを定めています:

下院議員と直接税はこの連邦に加入することを認められた州の人口に比例して各州で配分される。 ... 下院議員の定数は人口3万人に対し1人を超えてはならないが、各州は少なくとも1人の下院議員を持たなくてはならない。 ...

下院議会の議席は有限なので、議席を完全に人口に比例して配分するには複数の州に所属する議員あるいは州に部分的に所属する議員が必要です。しかしどちらも許されていないので、議席の小数部分を公平に配分するためのアルゴリズムが憲法が施行されてから数十年間に渡っていくつも提案されました。

現在使われているアルゴリズムは Huntington-Hill (ハンティントン-ヒル) 方式、あるいは等割合方式 (method of equal proportions) などと呼ばれます。このアルゴリズムは国勢調査局の統計学者 Joseph Hill (ジョセフ・ヒル) によって 1911 年に提案され、ハーバード大学の Edward Huntington (エドワード・ハンティントン) によって 1920 年に改良されました。その後このアルゴリズムは 1941 年に連邦法 (2 U.S.C. §2a) に組み込まれ、1992 年の最高裁判所に対する異議申し立てでも撤回されることはありませんでした¹。

Huntington-Hill 方式は州に一人ずつ議員を割り当てます。前処理の段階で各州に一人の議員を割り当て、メインループで 優先度 (priority) が最も高い州に議員を一人ずつ割り当てます。州の優先度は人口を \(P\) 、これまでに割り当てられた議員の数を \(r\) として \(P / \sqrt{r(r + 1)}\) と定義されます。

このアルゴリズムの疑似コードを次に示します。入力は \(n\) 個の州の人口を収めた配列 \(\mathit{Pop}[1..n]\) と割り当てようとしている議席数 \(R\) であり、\(R \geq n\) が仮定されます (現在の合衆国では \(n=50\) および \(R = 435\) です)。出力は各州に割り当てられた議席数を収めた配列 \(\mathit{Rep}[1..n]\) です。

procedure \(\texttt{ApportionCongress}\)(\(\mathit{Pop}[1..n], R\))

\(PQ \leftarrow \)\(\texttt{NewPriorityQueue}\)()

⟨⟨全ての州に一人目の議員を配る⟩⟩

for \(s \leftarrow 1\) to \(n\) do

\(\mathit{Rep}[s] \leftarrow 1\)

\(\texttt{Insert}\)(\(PQ, s, \mathit{Pop}[i]/\sqrt{2}\))

⟨⟨残りの \(R - n\) 人の議員を配る⟩⟩

for \( s \leftarrow 1 \) to \(R - n\) do

\( s \leftarrow \)\(\texttt{ExtractMax}\)(PQ)

\( \mathit{Rep}[s] \leftarrow \mathit{Rep}[s] + 1 \)

\( \mathit{priority} \leftarrow \mathit{Pop}[s] / \sqrt{\mathit{Rep} [s] {(}\mathit{Rep} [s] + 1)} \)

\(\texttt{Insert}\)(\( PQ, s, \mathit{priority} \))

return \(\mathit{Rep}[1..n]\)

図 0.5

Huntington-Hill のアルゴリズム

Huntington-Hill 方式のこの実装は \(\textsc{NewPriorityQueue}\), \(\textsc{Insert}\), \(\textsc{ExtractMax}\) という操作を持つ優先度付きキューを使います (もちろん実際の法律は優先度キューに言及していません)。アルゴリズムの出力およびその正しさが、優先度付きキューがどのように実装されるかに全く依存していないことに注目してください。国勢調査局はキューとしてエクセルのスプレッドシートに収められたソート済み配列を使い、配列は反復のたびにゼロから作り直されます。ただデータ構造の学部講義を受けたあなたなら、これよりも効率的な実装を知っているでしょう。

似たような議席配分アルゴリズムは世界中の政党議会選挙で使われています。政党議会選挙では各政党に割り当てられる議席数を政党の得票数に比例させる必要があるためです。有名なのは D'Hondt (ドント) 方式²と Webster-Sainte-Laguë (ウェブスター・サン=ラグ) 方式³の二つであり、これらの方式で使われる優先度は Huntington-Hill 方式における平方根の中身をそれぞれ \(P/(r+1)\) および \(P / (2r + 1)\) としたものです。合衆国憲法が各州に最低一人の議席を割り当てることを定めていることもあって、 Huntington-Hill 方式はアメリカ合衆国下院だけでしか使われていません。

最高裁判所はそれまでの連邦地方裁判所の判決を覆し、信義則に則って採択された (adopted by good faith) どんな議席の配分方法も憲法に違反しないと全会一致で表明しました。現在使われている議席配分のアルゴリズムは合衆国国勢調査局のウェブサイト http://www.census.gov/topics/public-sector/congressional-apportionment.html で詳細に説明されています。また議席配分の問題に関する歴史は http://www.thirty-thousand.org/pages/Apportionment.html に詳しく載っています。様々な議席配分法を解説した議会調査局によるレポートは http://www.fas.org/sgp/crs/misc/R41382.pdf から手に入ります。^[return]
Thomas Jefferson (トーマス・ジェファーソン) によって 1792 年に考案され、1792 年から 1832 年まで合衆国の議席配分に使われました。1878 年にベルギー人数学者 Victor D'Hondt (ビクター・ドント) によって再発見され、1888 年にスイス人物理学者 Eduard Hagenbach-Bischoff (エドアルド・ハーゲンバハ・ビスチョフ) によって改良されました。^[return]
Daniel Webster (ダニエル・ウェブスター) によって 1832 年に考案され、1843 年から 1911 年まで画集国の議席配分に使われました。1910 年にはフランス人数学者 André Sainte-Laguë (アンドレ・サン=ラグ) によって、1980 年にはドイツ人物理学者 Hans Schepers (ハンス・シェーパース) によって再発見されました。^[return]