ティールの投票ルール

ティーレの投票規則は、複数勝者投票のための規則である。有権者は政党ではなく個々の候補者に投票できるが、それでも比例代表制が保証される。この規則は1895年にデンマーク語でトールヴァルド・ティーレによって出版され、 ^[1] 2016年にスヴァンテ・ヤンソンによって英語に翻訳された。 ^{[2]この規則は、}スウェーデンの議会選挙で政党内の議席配分に使用され、現在でも市議会選挙で使用されている。

複数勝者承認投票では、各有権者は 1 人以上の候補者に投票でき、固定数のk名の勝者を選択することが目標となります ( kは、たとえば国会議員の数です)。問題は、勝者の集合をどのように決定するかです。

• 最も単純な方法は、複数回の譲渡不能投票であり、最も多くの支持を得たk人の候補者が選出されます。しかし、この方法では最大政党のk人の候補者が選ばれる傾向があり、小規模政党にはまったく代表者がいないことになります。
• 19 世紀には、比例代表制を保証できる選挙制度について多くの議論がありました。1878 年にドントが提唱した解決策の 1 つは、個々の候補者ではなく政党名簿に投票するというものでした。この解決策は今日でも非常に一般的です。

ティールは、有権者が候補者の個人的な長所に基づいて候補者を承認できるように、個々の候補者への投票を維持したいと考えていました。しかし、ティールの方法は、有権者が異なる政党の候補者に投票する可能性のある、より一般的な状況にも対応できます（実際、この方法では、どの候補者がどの政党に属しているかという情報は無視されます）。^{[2] : Sec.1}

投票者数をn、候補者数をm、必要な委員数をk で表します。承認投票では、各投票者i は承認セット A _iを持ち、これにはi が承認する候補者のサブセットが含まれます。目標は、セットA _iが与えられたときに、| W |= kとなる勝利候補者のサブセットW を選択することです。このサブセットは選出された委員会を表します。

ティールの規則は満足度関数の概念に基づいています。これは、投票者が承認した委員の数を、委員会に対するこの投票者の満足度を表す数値にマッピングする関数fです。したがって、投票者iが候補者の集合A _{i を}承認し、選出された候補者の集合がWである場合、投票者の満足度は です。ティールの方法の目標は、総満足度を最大化する委員会W を見つけることです (功利主義規則に従います)。結果は明らかに関数 f に依存します。一般性を失うことなく、 f(0)=0 および f(1)=1 となるようにf を正規化できます。ティールは、 fの選択は選挙の目的に依存するべきだと主張しています: ^{[2] : Sec.4}${\displaystyle f(|A_{i}\cap W|)}$

• 政府を選出する場合、すべてのメンバーの重要性は同じであるため、すべてのrに対して恒等関数 f( r )= rが成り立ちます。
• 調査委員会を選出するには多様性が重要であるため、彼は f( r )= ind (r≥1) を提案しています。つまり、r≥1 の場合は f (r)= 1、それ以外の場合は 0 です。
• 代表機関を選出するために、彼は f( r )= Harmonic (r) = 1/1 + 1/2 + ... + 1/ rを提案しています。

fの各選択に対して、Thiele は 3 つの方法を提案しました。

最適化手法: 総合的な満足度を最大化する委員会を見つけます。

• f(r)=r の場合、 Thiele の最適化手法は、承認投票 (AV)と呼ばれる手法と同等です。承認投票では、総投票数が最も多いk 人の候補者を選択するだけであり、少数派グループに対して比例しません。
• f( r )=ind( r≥1 ) の場合、Thiele の最適化法は、少なくとも 1 人の委員によって代表される市民の数を最大化することを目的とするChamberlin-Courant 投票規則 (CC)として知られる方法と同等です。多様性は高まりますが、多数派グループに比例するわけではありません。
• f( r )=Harmonic(r)のとき、ティーレの最適化手法は比例承認投票(PAV)と同等であり、2001年にフォレスト・シモンズによって再発見された。^[3]これは正当な表現を保証する唯一のfの選択である。

一般に、グローバル最適化問題を解くことは、 f( r )= rの場合を除き、NP困難な計算問題です。そのため、Thieleは2つの貪欲近似アルゴリズムを提案しました。

追加方式: 候補者は 1 人ずつ選出されます。各ラウンドで、総満足度の増加を最大化する候補者が選出されます。これは、これまでにr _{i 人}の勝者が承認された各投票者iの重みが f( r _i +1)-f( r _i ) である加重投票に相当します。

• f( r )=rのとき、投票者iの重みは、これまでに承認した勝者の数に関係なく、常に1です。したがって、結果として得られるルールは、再び承認投票になります。
• f( r )=Harmonic( r )のとき、投票者iの重みは1/ r _iです。この方法は、Sequential PAVと呼ばれることがよくあります。
• f( r )=ind(r≥1)のとき、投票者iの重みは、彼がまだ代表されていない場合は1、すでに代表されている場合は0になります。この方法は、貪欲承認投票^[4]ま​​たは貪欲チャンバーリンクーランと呼ばれます。

除去法は、追加法とは逆の方向に機能します。つまり、 m個の候補すべてから始めて、 k個だけが残るまで候補を 1 つずつ削除します。各ラウンドで削除される候補は、全体の満足度の低下を最小限に抑える候補です。

• f( r )=Harmonic( r )のとき、結果として得られる規則は、電子投票システムLiquidFeedbackの表示用に選択肢を順序付ける方法として再発明されたHarmonic Weightingと呼ばれる規則と同等である。^[5]

ティールの加算法には順位付け投票バージョンがあります。各ラウンドで、これまでに承認された勝者r _{i 名}を持つ各投票者iの投票重みは f( r _i +1)-f( r _i ) です。各投票者の重みは、残っている最上位の候補者に対してのみカウントされます。合計重みが最も高い候補者が選出されます。

これは1912年にスウェーデン議会で提案され、却下されたが、後に市議会と郡議会の選挙に採用され、現在でもその目的で使用されている。^{[2] ：第10条}

各投票用紙bについて、ちょうどb に投票した投票者の数をv _bとする（例えば、まったく同じ候補者群を承認した）。ちょうどb に投票した投票者の割合をp _bとする（= v _b / 投票総数）。投票方法がp _{b の}割合のみに依存する場合、その投票方法は同次的であると呼ばれる。つまり、投票数がすべて同じ定数で乗算された場合、その方法は同じ結果を返す。その意味で Thiele の方法は同次的である。^{[2] : Rem.2.1}

ティールの加算法はハウス単調性と呼ばれる性質を満たしている。つまり、委員の数が増えても、以前に選出された委員は全員引き続き選出される。これは、方法の説明からすぐにわかる。ティールの消去法もハウス単調性である。しかし、ティール自身が指摘しているように、ティールの最適化法は一般にハウス単調性に違反している。実際、ティールの最適化法は、（正規化された）満足度関数 f( r )= rに対してのみハウス単調性を満たしている。次に例を挙げる: ^{[2] : Sec.5.1}

• まず、 f (2)<2 であると仮定します。3 人の候補者 x、y、z と、承認セット xy、xz、y、z を持つ 4 人の市民がいるとします。k =1 のとき、すべての委員会 {x}、{y}、{z} の合計満足度は同じです。2f(1)+2f(0) = 2+0 = 2 (正規化により) なので、委員会は同点決着により選出されます。{x} が選出されると仮定します。ここで、k が2 に増加するとします。{x,y} と {x,z} の満足度は f(2)+2f(1)+f(0) = f(2)+2 です。{y,z} の満足度は 4f(1) = 4 です。f(2)<2 の場合、{y,z} が選出され、ハウス単調性に違反します。
• 次に、 f (2)>2 であると仮定します。3 人の候補者 x、y、z と、承認セット x と yz を持つ 2 人の市民がいるとします。k =1 のとき、すべての委員会 {x}、{y}、{z} の合計満足度は同じ 1 です。{x} が選出されるとします。ここで、k が2 に増加するとします。{x,y} と {x,z} の満足度は 2f(1) = 2 です。{y,z} の満足度は f(2) です。f(2)>2 の場合、{y,z} が選出され、ハウス単調性に違反します。
• したがって、ハウス単調性が成立するためには、 f(2)=2 が成立する必要があります。同様の議論を使用して、すべてのrに対してf( r )= r であることを証明できます。

これはまた、Thieleの最適化法がf( r )= rの場合にのみ加法法と一致することを意味している。^{[2] : Rem.5.2}

ラックナーとスコウロン^[6]は、ティールの投票ルールが回帰比例と減退比例の間を補間するために使用できることを示している。PAVは比例であり、スコア関数の傾きがPAVの傾きよりも大きいルールは回帰比例を満たし、スコア関数の傾きがPAVの傾きよりも小さいルールは減退比例を満たします。さらに、承認されたi番目の候補者の満足度スコアが(1/ p ) ⁱである場合、さまざまなpの値に対して、CCとAVの間のスペクトル全体が得られます。^[7]

• Phragmenの投票ルール