Phragmenの投票ルール

フラグメンの投票規則は、複数当選者投票のための規則である。有権者は政党ではなく個々の候補者に投票できるが、それでも比例代表制が保証されている。この規則は、ラース・エドヴァルド・フラグメンによって1893年から1899年にかけてフランス語とスウェーデン語で出版され、 ^[1] 2016年にスヴァンテ・ヤンソンによって英語に翻訳された。 ^[2]

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

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

Phragménは、有権者が候補者を個人の長所に基づいて承認できるように、個々の候補者への投票を保持したいと考えました。各有権者が単一政党の候補者全員のみを承認するという特殊なケースでは、Phragménの方法はD'Hondtの方法と同じ結果をもたらします。^{[2] : Sec.11}しかし、Phragménの方法は、有権者が異なる政党の候補者に投票する可能性のあるより一般的な状況を扱うことができます（実際、この方法ではどの候補者がどの政党に属しているかという情報は無視されます）。

フラグメンの順序なし（承認）投票方法は、いくつかの同等の方法で提示することができる。^{[2] ：第3節}

選出された各候補者は 1 単位の「負担」を負います。候補者の負担は、その候補者を支持する有権者が負わなければなりません。目標は、その負担を有権者間で最も「バランスのとれた」方法で分配できる委員会を見つけることです。

「バランスのとれた」の定義に応じて、いくつかのルールが考えられます。^[3]

• Leximax-Phragmen:最大負荷を最小化し、それに応じて 2 番目に大きい負荷などを決定します (辞書式最大最小最適化を使用)。
• 語彙フレーズ: 最小負荷を最大化し、それに従って 2 番目に小さい負荷など。
• var-Phragmen 法またはEbert 法:負荷の分散を最小化します。

これらのバリアントにはそれぞれ 2 つのサブバリアントがあります。

• 通常、計算が NP 困難なグローバル最適化バリアント。
• 順次的な変種。候補が順番に選択され、各ターンで、すべての候補の中で最適な尺度を達成した候補が次に選出されます (つまり、貪欲アルゴリズム)。

Phragmenのオリジナルの方法は、最大負荷を最小化する逐次法であり、現在ではSeq-Phragmenとして知られています。^[3]

実際には、グローバル最適化カテゴリで最も公理的な保証を持つルールは、leximax-Phragmen と var-Phragmen です。 シーケンシャルバリアントの中では、Seq-Phragmen によって最も保証されます。

フラグメンは、各有権者を容器に例えて、この方法を説明した。すでに選出された候補者は容器の中の水で表されている。別の候補者を選出するには、その候補者に投票した有権者に対応する容器に 1 リットルの水を注ぐ必要がある。水は、水の最大の高さができるだけ小さくなるように分配する必要がある。

Seq-Phragmen は、次のような連続プロセスとして説明することもできます。

• 各投票者は仮想マネー 0 から始まり、1 日あたり 1 の一定の割合でお金を受け取ります。
• 各時点tにおいて、 x を承認する有権者が保有する合計金額が少なくとも 1 である場合、まだ選出されていない候補者x は手頃な価格であると定義されます。
• 候補者が初めて手頃なときに、手頃な候補者y を1 人任意に選択します。y を委員会に追加し、y を承認した有権者の仮想マネーをリセットします (有権者は仮想マネーをy の資金として「使用した」ため)。
• 投票者は、すべてのk人の委員が選出されるまで、仮想マネーを獲得し、候補者に資金を提供し続けます。

次の簡単な例は、政党名簿投票に似ています。議席は k = 6 で、候補者は 9 名、それぞれ a、b、c、d、e、f、g、h、i と表記されます。投票者は 63 名で、次の好みを持っています。31 名の投票者が a、b、c を承認し、21 名の投票者が d、e、f を承認し、11 名の投票者が g、h、i を承認しています。

• 有権者は、1 日あたり 1 の固定レートでお金を稼ぎ始めます。1/31 日 (約 0.0323 日) 後、31 人のabc有権者はそれぞれ 0.0323 を保有するため、全員で承認された候補者の 1 人に資金を提供できます。a、b、c のいずれかが任意に選択されます。それが a であるとします。
• 1/21 日後 (~0.0476 日後)、31 人のabc投票者はそれぞれ ~0.015 しか持っていませんが、21 人のdef投票者はそれぞれ 0.0476 を持っているため、彼らは一緒に承認された候補者の 1 人に資金を提供できます。d、e、f のいずれかが任意に選択されます。それが d であると仮定します。
• 約 0.0646 日後、abc有権者はそれぞれ 0.0323 を再び保有するため、承認された候補者の別の 1 人、たとえば b を購入します。
• 1/11 日後 (約 0.091 日後)、ghi投票者はそれぞれ 0.091 を保有するため、一緒に承認された候補者の 1 人 (たとえば g) に資金を提供できます (この時点で、abc投票者はそれぞれ 0.0264 しか保有しておらず、def投票者はそれぞれ 0.0434 しか保有していないため、どちらも別の候補者を購入できません)。
• 0.0952 日後、反対票を投じた有権者は再びそれぞれ 0.0476 を獲得し、別の候補者 (e とします) を買うことができます。
• 0.0969 日後、abc 有権者は再びそれぞれ 0.0323 を獲得し、別の候補者 (たとえば c) を購入できるようになります。

最終的な委員会は、a、b、c、d、e、g です。各「政党」は、その規模にほぼ比例して代表されることに注意してください。つまり、31 人の有権者に対して 3 人の候補者、21 人の有権者に対して 2 人の候補者、11 人の有権者に対して 1 人の候補者です。

より複雑な例を示します。k =3 議席があり、候補者は 6 人いて、それぞれA、B、C、P、Q、R で表されます。投票結果は、ABC が 1034 票、PQR が 519 票、ABQ が 90 票、APQ が 47 票です。当選者は次のように順番に選出されます。

• まず、各候補者が総投票権 1 を獲得するために必要なtの値を計算します。この値は、A の場合は 1/1171 (A は 1171 票に登場しているため)、B の場合は 1/1124、C の場合は 1/1034、P の場合は 1/566、Q の場合は 1/656、R の場合は 1/519 です。したがって、A が最初に選出されます。
• ここで、各候補者について、候補者が合計投票力を 1 にするために必要なtの値を再計算します。ただし、A を承認した各投票者から 1/1171 を差し引くことを念頭に置いてください。B を承認する投票者は 1124 人で、全員がすでに A を承認しているため、必要な値は 1/1124+1/1171 です。同様に、C の必要な値は 1/1034+1/1171 です。Q の場合は 1/656+(137/656)/1171 です。Q の投票者 656 人のうち 137 人がすでに A に投票しているためです。P の場合は 1/566+(47/566)/1171 です。R の場合は 1/519 です。Q の値は最小であるため、2 番目の勝者として選出されます。
• 同様に、Bが3番目の勝者として選出されます。

Var-PhragmenとLeximax-Phragmenは、各エージェントが2人の候補者を承認し、各候補者が3人の投票者によって承認された場合でも、計算がNP困難です。証明は、立方グラフ上の最大独立集合からの還元によって行われます。^[3]

Leximax-Phragmenは、それぞれO( nm + n2 )個の変数を持つ最大2n個の 混合整数線形計画法^{のシーケンスによって計算できます（ここで、} nは投票者の数、mは候補者の数です）。辞書式最大最小最適化を参照してください。

Var-Phragmenは、O( nm )個の変数を持つ1つの混合整数二次計画を解くことによって計算できます。

Seq-Phragmen は多項式時間で計算できます。単純な計算では、実行時間は O( kmn ) であることが示されています。つまり、 kステップ (選出された候補者ごとに 1 つ) があり、各ステップで、すべての候補者を調べて、どの候補者に資金を提供できるか確認する必要があります。また、各候補者について、すべての投票者を調べて、どの候補者に資金を提供できるか確認する必要があります。ただし、正確に計算するには、有理数で作業する必要があり、その大きさはk log nまで大きくなります。b ビットでの計算には O( b 2 ) 時間が必要になる可能性があるため、^合計実行時間は O( k ³ mn log ² n) です。

Phragménルールは承認投票（つまり、複数勝者承認投票）でよく使用されますが、順位付け投票（つまり、複数勝者順位付け投票）を使用するバリエーションもあります。Seq-Phragmenの適応は、1913年に比例選挙方式に関する王立委員会によって提案されました。この方法は、1921年以来、スウェーデンの選挙で政党内の議席配分に使用されています。^{[2] ：Sec.9}

修正版では、各投票者は各ラウンドで、事実上、残っている候補者の中で最高位の候補者にのみ投票します。また、候補者が選出されると、その候補者の「負荷」1 単位は、その候補者に投票した候補者 (つまり、その候補者を 1 位にランク付けした候補者) の間で分配されます。負荷の分割により、投票者の最大負荷が最小限に抑えられます。

フラグメン法は政党にも適用できる。各有権者は1つ以上の政党を承認できる。手順は以前と同じだが、各政党は0から政党内の候補者総数まで複数回選択できるようになった。^[4]

Seq-Phragmenルールは、より一般的な組み合わせ参加型予算編成の設定に適応されました。^[5]

JaworskiとSkowron ^[6]は、seq-Phragmenを減退比例と回帰比例に一般化する規則のクラスを構築した。直感的には：

• 逓減比例性は、すでに代表者が多い有権者は代表者が少ない有権者よりも収入が減ると仮定することで得られます。
• 逆進比例は、より多くの有権者から支持された候補者は、より少ない有権者から支持された候補者よりも費用が安いと仮定して実行されます。

逐次フラグメン法は、サブセットを選択するだけでなく、選択肢が選択された順序に従って選択肢のランキングを作成するためにも使用できます。ブリルとイスラエル^{[7]は、この方法を}動的ランキングに拡張しました。オンラインQ&Aアプリケーションに触発されて、^[8]彼らはいくつかの候補がすでに選択されていると仮定し、この情報をランキングの計算に使用します。彼らはフラグメンのルールの2つの適応を提案しています。

• 動的フレーズ: 各ステップで、すでに選出された候補者のシーケンスをループし、その「コスト」を支持者間で分配します。これにより、各ユーザーに潜在的な「負債」、つまりマイナス残高が作成されます。負債の計算は、O( mn2 ) の時間で実行できます。ここで、^mは候補者の数、n はユーザー数です。次に、ユーザーは通常どおりにお金を貯め始めます。ユーザーは「負債」を支払った後でのみ、新しい候補者の購入を開始できます。ユーザーは、新しいランキングが計算されるまで、候補者を順番に購入します。新しいランキングは比例します。新しいシーケンスの計算は、O(m2n2) の時間で^実行でき^ます。
• 近視眼的フレーズ: 各ユーザーの「負債」は、動的フレーズと同様に計算されます。次に、シーケンシャル フレーズを実行して完全なランキングを作成する代わりに、候補者はユーザーに対して作成する「負債」の量によってランク付けされます。つまり、候補者は次に選出されるのにふさわしいかどうかによってランク付けされます。結果のランキングは必ずしも比例的ではありません (特に、シーケンスが空の場合、近視眼的フレーズは功利主義的な承認投票と一致します)。新しいシーケンスの計算は、時間 O( mn ² )で実行できます。

彼らは、これらの適応の単調性と公平性の特性を理論的かつ経験的に分析します。

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

投票用紙に候補者が何名か追加されても、そのうちの誰も選出されなかった場合（たとえそのうちの何人かが投票されたとしても）、結果は変わりません。^{[2] : Sec.6}これにより、戦略的な操作のインセンティブが1つ減ります。つまり、投票を集めるために「ダミー」候補者を追加することです。

Seq-Phragménは議席を1つずつ割り当てるため、委員会の単調性特性を満たします。つまり、議席が追加されると、勝者の集合が増加します（議席を失う勝者はいません）。^{[2] ：Sec.5}

これらは他のいくつかの単調性基準も満たしている。^{[2] ：Sec.14}

Phragmén の承認投票方式の場合、ある候補者Cが選出され、その後、候補者CがCに投票する新規有権者またはC を投票用紙に追加する既存有権者から承認を得て、他の変更がない場合は、依然としてCが選出されます。ただし、この単調性は、候補者のペアが常に一緒に登場する場合であっても当てはまりません。たとえば、候補者 C と D がすべての投票で一緒に登場し、2 議席を獲得するが、C と D に別の投票が追加された場合、一緒に 1 議席しか獲得できない可能性があります (したがって、どちらかが議席を失います)。^{[2] : 例 14.4、14.5}同様に、単調性は政党のバリエーションでは当てはまりません。政党はより多くの承認を得ても、議席は少なくなる可能性があります。例: ^[4]

• k =3 議席があり、候補者が a、b、c の 3 人いるとします。投票は、a が 4 票、b が 7 票、a+b が 1 票、a+c が 16 票、b+c が 4 票です。この場合、選出された委員会は {a、b、a} です。ただし、b の投票者の 1 人が a も承認した場合 (投票は、a が 4 票、b が 6 票、a+b が 2 票、a+c が 16 票、b+c が 4 票)、選出された委員会は {a、c、b} です。したがって、政党 a は承認されましたが、議席を失いました。

Phragmén の順位付け投票方式の場合、候補者Cが当選し、その後候補者Cがいくつかの投票で昇格したり、新しい票を獲得したりして、他の変化が起こらなければ、Cは当選します。しかし、他の変化が同時に起こった場合、C は議席を失う可能性があります。たとえば、一部の有権者が考えを変え、A と B に投票する代わりに C と D に投票し、この変化によって C が議席を失う可能性があります。^{[2] : Ex.13.16}

シーケンシャルフラグメンルールは、比例正当化表現（PJR）と呼ばれる公理を満たしています。 ^[3]これにより、PJRと単調性の両方を満たす数少ない方法の1つになります。

しかし、これは拡張正当化表現（EJR）と呼ばれるより強力な公理に反しています。一例を次に示します。^[3]

• 候補者は 14 人います: a、b、c1、...、c12。埋めるべき席は 12 あります。
• 投票者は 24 人います。そのうち 2 人が {a,b,c1} を承認し、2 人が {a,b,c2} を承認し、6 人が {c1,c2,...,c12} を承認し、5 人が {c2,c3,...,c12} を承認し、9 人が {c3,c4,...,c12} を承認しています。
• Seq-Phragmen は c1、...、c12 を選択します。{a、b、c1} と {a、b、c2} を承認する 4 人の投票者に対して EJR に違反します。このグループには 2 つの割り当てがあり、2 つの凝集性がありますが、どのメンバーにも 2 人の承認された勝者がいません。

もう一つの例を次に示します（パーティーの設定について）：^[9]

• 候補者政党は3つあり、埋めるべき議席は10あります。
• 投票者は 10 人おり、承認セットは ab、ab、ab、ac、ac、ac、ac、bc、bc、b です。
• Seq-Phragmen は a (1/7 の時点で)、次に b、次に a、b、a、b、a、b、a、b を選択します。
• 投票者 1、2、3 は 10 人の候補者全員を承認しましたが、投票者 4、...、10 は 5 人の候補者のみを承認しました。ただし、投票者 4、5、6、7、8、9 のグループはすべて政党 c に同意しているため、EJR ではそのうちの少なくとも 1 人が 6 人の候補者を承認する必要があるため、EJR に違反しています (10 人の候補者全員がグループの少なくとも 1 人のメンバーによって承認されているため、そのグループでは PJR に違反していないことに注意してください)。

Seq-Phragmen は、 Perfect Representation (PER) と呼ばれる、互換性のない別の公理にも違反します。

Var-Phragmen は PER を満たしますが、PJR と EJR を満たしません (L=1 の場合を除く)。

Leximan-Phragmen は PJR と PER の両方を満たしますが、EJR には依然として不合格です。

Phragménの方法は一貫性基準を満たしていない。さらに、完全な投票を無視していないので、すべての候補者に投票する（したがって全く無関心な）有権者を加えると、結果に影響を与える可能性がある。^{[2] : 例15.4、15.6、15.8、15.9}

座席が 1 つの場合 ( k =1):

• Phragmén の承認投票方式は承認投票に帰着し、常に最も多くの承認を得た候補者を選択します。
• フラグメンの順位付け投票方式は、多数決投票にまで縮小され、常に最多の投票者によって第 1 位にランクされた候補者が選出されます。

• Phragménの方法の詳細については、こちらをご覧ください。^[10]
• Phragmen法とThiele法の数学的性質^[11]
• エネストロムとフラグメンの方法^[12]

• Phragmén の投票ルールの一部は、Python パッケージ abcvoting に実装されています。
• Phragmén の投票ルールの一部は、pref.tools ウェブサイトでオンラインで試すことができます。
• シンプルなバージョンと複雑なバージョンの両方^{[13] [14]が}暗号通貨 ポルカドットの基盤として使用されています。^[15]

Motamed、Soeteman、Rey、Endriss ^[16]は、フラグメンのルールを複数のリソースによる参加型予算編成に一般化した 順次負荷分散メカニズムを提示している。

• 単記譲渡投票
• 承認ルールの拡大
• 均等割方式
• ティールの投票ルール