比例承認投票

比例承認投票（PAV）は、複数当選者選挙のための比例 選挙制度である。これは、政党名簿比例代表の配分を計算するために一般的に使用されるドント配分法を拡張した複数当選者承認方式である。^{[1]しかし、PAVでは、有権者は特定の}政党名簿上のすべての候補者を承認または拒否することを強制されるのではなく、承認する候補者のみを支持できる。^[2]

PAV では、有権者は自分が承認するすべての候補者に印をつけて承認投票を行います。各有権者の投票は、投票用紙上のすべての候補者が自分の「政党名簿」に載っているかのように扱われます。その後、すべての連合が比例代表されるように、候補者間で 議席が配分されます。

PAVは、 Thorvald N. Thieleによって提案されたThieleの投票規則の特殊なケースです。^{[3] [4]}これは、1909年から1921年までのスウェーデンの選挙で、政党内および地方選挙での議席配分のために順位投票と組み合わせて使用​​されました。 ^[4] PAVは2001年にForest Simmonsによって再発見され、^[5]彼はこれを「比例承認投票」と名付けました。

類似の満足度承認投票と同様に、PAV は、すべての可能性のある委員会をテストして委員会を選択し、最も多くの票を獲得した委員会を選択するものと考えることができます。満足度承認投票では、各投票者の投票は、承認するすべての候補者に均等に分割され、各人に投票権が与えられます。投票者が完全に戦略的で、政党が認める数の候補者のみを支持する場合、SAV は比例結果を生み出します。 ${\displaystyle r}$${\displaystyle 1/r}$

PAV は、この戦略の必要性をなくすために 1 つの変更を加えています。つまり、有権者が候補者を選んだ後にのみ、投票用紙を分割するのです。その結果、有権者は投票用紙を薄めることなく、負けた候補者を自由に承認することができます。有権者は、最初に支持して当選した候補者に 1 票を投じ、2 番目に支持した候補者に半票を投じる、というように続きます。

したがって、投票によって選出された候補者が承認された場合、その投票は委員会の投票総数に第 -調和数を加えます。言い換えると、次のようになります。 ^{[5] [6]}${\displaystyle r}$${\displaystyle r}$

${\displaystyle \mathrm {H} (r)=1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{r}}}$

特定の委員会のスコアは、すべての投票者から得たスコアの合計として計算されます。その後、最も高いスコアを獲得した委員会が選出されます。

正式には、候補者の集合、投票者の集合、委員会の規模 があると仮定します。が投票者 によって承認された候補者の集合を表します。規模の委員会の PAV スコアは と定義されます。PAV は最大スコアを持つ 委員会を選択します。${\displaystyle C=\{c_{1},c_{2},\ldots ,c_{m}\}}$${\displaystyle N=\{1,2,\ldots ,n\}}$${\displaystyle k}$${\displaystyle A_{i}}$${\displaystyle i\in N}$${\displaystyle W\subseteq C}$${\displaystyle |W|=k}$${\displaystyle \textstyle \mathrm {sc} _{\mathrm {PAV} }(W)=\sum _{i=1}^{n}\mathrm {H} (|A_{i}\cap W|)}$${\displaystyle W}$

埋めるべき議席が 2 つあり、候補者は Andrea (A)、Brad (B)、Carter (C)、Delilah (D) の 4 名、投票者は 30 名であるとします。投票用紙は次のとおりです。

• 5人の投票者がAとBに投票しました
• 17人の投票者がAとCに投票した
• 8人の投票者がDに投票した

結果は AB、AC、AD、BC、BD、CD の 6 つが考えられます。

アンドレアとカーターが選出される。

シンプル承認では、アンドレアが 22 票、カーターが 17 票、デリラが 8 票、ブラッドが 5 票を獲得していることが示されています。この場合、PAV によるアンドレアとカーターの選択は、シンプル承認のシーケンスと一致しています。ただし、上記の投票がわずかに変更され、A と C が 16 票、D が 9 票を獲得すると、A と C のスコアが 29 になり、A と D のスコアが 30 のままになるため、アンドレアとデリラが選出されます。また、シンプル承認を使用して作成されたシーケンスは変更されません。これは、PAV が、シンプル承認によって暗示されるシーケンスに単純に従う方法と互換性のない結果をもたらす可能性があることを示しています。

選出される議席が 10 あり、候補者が赤、青、緑の 3 つのグループに分かれているとします。投票者は 100 人です。

• 60人の有権者が青候補者全員に投票した。
• 30人の有権者が赤の候補者全員に投票した。
• 10人の有権者が緑の党の候補者全員に投票した。

この場合、PAVは6人の青、3人の赤、1人の緑の候補者を選択します。このような委員会のスコアは、他のすべての委員会のスコアが低くなります。たとえば、青の候補者のみで構成された委員会のスコアは、 $${\displaystyle 60\cdot \mathrm {H} (6)+30\cdot \mathrm {H} (3)+10\cdot \mathrm {H} (1)=60\cdot \left(1+{\tfrac {1}{2}}+\ldots +{\tfrac {1}{6}}\right)+30\cdot \left(1+{\tfrac {1}{2}}+{\tfrac {1}{3}}\right)+10\cdot 1=147+55+10=212{\text{.}}}$$

${\displaystyle 60\cdot \mathrm {H} (10)+30\cdot \mathrm {H} (0)+10\cdot \mathrm {H} (0)=60\cdot \left(1+{\tfrac {1}{2}}+\ldots +{\tfrac {1}{10}}\right)\approx 175.73{\text{.}}}$

この例では、PAVの結果は比例的です。つまり、各グループから選出される候補者の数は、そのグループに投票する有権者の数に比例します。これは偶然ではありません。上記の例のように、候補者が別々のグループを形成し（グループは政党と見なすことができます）、各有権者が1つのグループ内のすべての候補者に排他的に投票する場合、PAVは政党名簿比例代表制のドント方式と同じように機能します。^[1]

このセクションでは、比例承認投票の公理的な特性について説明します。

勝者が 1 人だけの選挙では、PAV は承認投票とまったく同じように機能します。つまり、最も多くの投票者から承認された候補者で構成される委員会を選出します。

比例代表制のほとんどの制度では政党名簿が使用される。PAV は比例代表制と個人投票 (有権者は候補者に投票するのであって政党名簿に投票するのではない) の両方を持つように設計された。投票が党派的計画に従う場合 (各有権者が 1 つの政党のすべての候補者に投票し、他の候補者には投票しない)、各政党からその政党を選んだ有権者の数に比例した数の候補者が選出されるため、この制度は「比例」制度と呼ばれるにふさわしい (例 2 を参照)。^{[1]さらに、対称性、連続性、}パレート効率などの緩やかな仮定の下では、PAV は個人投票を許可し、一貫性基準を満たすドント法の唯一の拡張である。^[2]

たとえ有権者が党派的制度に従わなくても、この規則は比例性の保証を提供する。例えば、PAVは拡張正当化表現と呼ばれる強い公平性特性^[6]と、関連する特性である比例正当化表現^[7]も満たしている。また、最適比例次数も持っている。^{[8] [9]}これらすべての特性は、凝集性（類似性）のある選好を持つ有権者のグループが、少なくともグループのサイズに比例する数の候補者によって代表されることを保証する。PAVは、PAVのような最適化手法（定義で調和数以外の数値を使用する場合もある）の中で、このような特性を満たす唯一の手法である。^[6]

PAVによって返される委員会はコアに含まれない可能性がある。^{[専門用語] [6] [10]}しかし、コアの2近似^{[専門用語]が保証され、これは}ピグー・ドルトンの移転原理を満たす規則によって達成できる最適な近似比である。^[10]さらに、選挙で十分に多くの類似した候補者が立候補している場合、PAVはコアの特性を満たします。^[11]

PAVは価格可能性を満たしておらず（つまり、PAVの選択は、有権者が一定額の仮想通貨を与えられ、そのお金を使って好きな候補者を買うというプロセスでは必ずしも説明できない）、層状比例性を満たしていない。^[10]価格可能性と層状比例性を満たし、PAVと同等に比例性に関する特性を持つ2つの代替ルールは、均等割付法とフラグメンの逐次ルールである。^[12]これら2つの代替方法も多項式時間で計算可能であるが、パレート効率を満たしていない。

比例性に関する特性とは別に、PAV は次の公理 を満たします。

• パレート効率
• 一貫性
• 支持単調性（勝利した候補者の支持が増加、つまりより多くの有権者がこの候補者に投票した場合、この候補者は勝利し続ける）^[13]
• ピグー・ドルトン原理^[10]

PAV は次のプロパティ を満たしていません。

• ハウス単調性[ ^12]ハウス単調性を満たし、PAVと同等に比例性に関する特性を持つ2つの代替手法は、Sequential Proportional Approval VotingとPhragménのSequential Rulesである。^[12]これら2つの代替手法も多項式時間で計算可能であるが、パレート効率、一貫性、ピグー・ドルトン原理を満たしていない。^[12]

PAVの解とその品質は多項式時間で検証できるため[ ^{15] [16]、}透明性が容易になります。ただし、最悪の場合の時間計算量はNP完全であり、一部の選挙ではPAVの理論的特性すべてを保証する正確な解を見つけることが困難または不可能になる可能性があります。

実際には、PAV の結果は、整数計画ソルバー (abcvoting Python パッケージで提供されているものなど)を使用して、中規模委員会 (候補者 50 人未満) に対して正確に計算できます。正確な解を見つけるには、 k議席とn投票者の場合に時間がかかります。 ${\displaystyle O(nm^{k})}$

パラメータ化された複雑性の観点から見ると、PAVを計算する問題は、いくつかの例外的な簡単なケースを除いて理論的に困難です。^{[15] [17] [18]}幸いなことに、そのようなケースは実際の選挙の良い近似であることが多いため、正しい解を見つけるための計算労力を大幅に削減するヒューリスティックとして使用することができます。たとえば、有権者と候補者が1次元の政治的スペクトルに沿っている場合は、正確な選挙結果を多項式時間で解決できます。^[14]また、有権者が強力な党派である場合（つまり、候補者ではなく政党のリストに投票する場合）は線形時間で解決できます。

逐次比例承認投票はPAVの貪欲近似であり、最悪の場合の近似率は であるため、結果として得られる委員会のPAVスコアは最適値の少なくとも63%になります。^[16]この方法は多項式時間で計算でき、選挙結果は手動で決定できる可能性があります。非ランダム化丸め（条件付き確率法 を使用）を含む別のアプローチでは、最悪の場合の近似率は0.7965になります。^[19]複雑性理論の標準的な仮定の下では、これがPAVに対して多項式時間で達成できる最良の近似率です。^[19] PAVを近似する問題は、最小化問題として定式化することもできます（ を最大化するのではなく、を最小化します）。その場合、既知の最良の近似率は2.36です。^[20]${\displaystyle 1-1/e\approx 0.63}$${\displaystyle \textstyle \mathrm {sc} _{\mathrm {PAV} }(W)}$${\displaystyle \textstyle \sum _{i\in N}\mathrm {H} (k)-\mathrm {sc} _{\mathrm {PAV} }(W)}$

• Lackner, Martin; Skowron, Piotr (2023).承認選好による複数勝者投票. SpringerBriefs in Intelligent Systems. arXiv : 2007.01795 . doi :10.1007/978-3-031-09016-5. ISBN 978-3-031-09015-8. S2CID  244921148。
• Piotr Faliszewski、Piotr Skowron、Arkadii Slinko、Nimrod Talmon (2017-10-26)。「複数勝者投票: 社会選択理論の新たな課題」。Endriss、Ulle (編)。計算社会選択の動向。AI アクセス。ISBN 978-1-326-91209-3。{{cite book}}: CS1 maint: multiple names: authors list (link)

• 均等割方式
• ドント法
• 逐次比例承認投票
• Phragmenの投票ルール

• PAV やその他の承認ベースの複数勝者方式を計算するためのオンライン ツール
• PAV の実装を含む Python パッケージ abcvoting (pypi)