スミスセット

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

投票システムでは、ジョンH.スミスにちなんで名付けられたスミスセットですが、トップサイクル、または一般化されたトップチョイス仮定(GETCHA)とも呼ばれ、特定の選挙で空でない候補の最小のセットであり、メンバーはペアワイズ選挙でセット外のすべての候補者を打ち負かします。スミスセットは、選挙結果のための最適な選択の1つの基準を提供します。スミスセットから常に候補者を選出する投票システムは、スミス基準に合格し、「スミス効率的」またはスミス基準を満たすと言われます

それぞれのメンバーがセット外のすべての候補をペアで打ち負かす候補のセットは、支配集合と呼ばれます。

スミスセットは、 IRVタイブレークによってスミス/ IRVまたはタイドマンの代替として、またはミニマックスによってスミス/ミニマックスとして拡張されたときに最も頻繁に遭遇する投票方法(スミスの方法)を定義するものと見なすことができます

スミスセットのプロパティ

  • スミスセットは常に存在し、明確に定義されています(次のセクションを参照)。
  • スミスセットは、ペアワイズタイのため、またはコンドルセのパラドックスのようにサイクルのために、複数の候補を持つことができます。
  • コンドルセットの勝者は、存在する場合、スミスセットの唯一のメンバーです。弱いコンドルセットの勝者が存在する場合、それらはスミスセットに含まれています。
  • スミスセットは、相互に多数派が優先する候補のセット(存在する場合)のサブセットです。[1]

支配集合の性質

定理:支配集合はネストされています; つまり、選挙で支配的な2つのセットのうち、一方が他方のサブセットです。

証明:反対に、2つの支配集合DEが存在し、どちらも他方のサブセットではないとします。次に d∉Eおよびe∉Dなる候補d∈D e∈E 存在 する必要ありますしかし、仮説によれば、 dはDに含まれないすべての候補( eを含む)を打ち負かし、 eはEに含まれないすべての候補( dを含む)を打ち負かします。これは矛盾です。fetch

当然の結果として、スミス集合は最小の空でない支配集合であり、明確に定義されています。

定理: Dが支配集合である場合、D要素が正確にコープランドスコアが少なくともθDである候補であるようなしきい値θDがあります。(候補者のコープランドスコアは、彼または彼女が敗北した他の候補者の数に、彼または彼女が結びついている他の候補者の数の半分を加えたものです。)

証明:最小のコープランドスコアを持つDの要素としてdを選択、このスコアをθDで識別しますここで、ある候補e∉DのコープランドスコアがθD以上であると仮定します。次に、 dはDに属し eは属さないため、 dはeを打ち負かします。また、 eのコープランドスコアが少なくともdのスコアと等しくなるためには、 eがdよりも優れたスコアを取得する3番目の候補fが存在する必要がありますもしもf∈Dの場合、 eを打ち負かさないD要素があり、 f∉Dの場合、 dの外にdが打ち負かさない候補があり、どちらの場合も矛盾が生じますfetch

シュワルツセット比較

Generalized Optimal-Choice AxiomまたはGOCHAとして知られるSchwartzセットは、Smithセットと密接に関連しており、常にサブセットです。スミスセットは、シュワルツセット内の候補が、シュワルツセット内にない候補とペアワイズタイである場合にのみ大きくなります。

スミスセットは、セットの外にそのような候補がなくなるまで2種類の候補を繰り返し追加することにより、シュワルツセットから構築できます。

  • セット内の候補とペアワイズ関係にある候補、
  • セット内の候補を打ち負かす候補。

2番目のタイプの候補は、最初のタイプの候補が追加された後にのみ存在できることに注意してください。

スミス基準

スミス基準は、勝者が常にスミスセットに属する投票方法によって満たされます。スミス基準を満たすメソッドは、コンドルセット基準も満たす必要があります。したがって、Condorcetと一貫性のないメソッド(IRVなど)もSmith基準に合格しない必要があります。ミニマックスは、スミス基準を満たさない最もよく知られているコンドルセット法です。

スミスセットの計算

上記の支配集合の論理特性を使用して、スミス集合を計算するための効率的なアルゴリズムを構築できます。支配集合はCopelandスコアによってネストされていることがわかりました。したがって、Copelandしきい値を調整することにより、支配集合に到達するまで、サイズの昇順でネストされた集合を処理することができます。このセットは必然的にスミスセットです。ダーリントンはこの方法をスケッチしています。[2]

セットが各段階で支配集合であるかどうかをテストすると、いくつかの計算が繰り返される可能性がありますが、これはかなり簡単に回避でき、候補の数で作業係数が2次のアルゴリズムになります。

詳細なアルゴリズム

アルゴリズムは、例を通して詳細に提示することができます。結果マトリックスが次のようになっているとします。

2位
1位
A B C D E F G スコア
A 1 1 1 1 1 0 5
B 0 0 0 1 0 0 1
C 0 1 0 1 1/2 1 31/2
D 0 1 1 1 1 1 5
E 0 0 0 0 0 0 0
F 0 1 1/2 0 1 0 21/2
G 1 1 0 0 1 1 4

ここで、最初の候補者が最初の候補者より2番目の候補者よりも多くの有権者によって2番目の候補者に優先された場合、メインテーブルのエントリは1です。反対の関係が成り立つ場合は0。1/2同点の場合。最後の列は、最初の候補者のコープランドスコアを示しています。

スミスセットを計算するアルゴリズムは凝集的です。コープランドセットから始まります。コープランドセットはそのサブセットであることが保証されていますが、多くの場合は小さくなり、不要になるまでアイテムが追加されます。最初のステップは、スコアに従って候補をソートすることです。

2位
1位
A D G C F B E スコア
A 1 0 1 1 1 1 5
D 0 1 1 1 1 1 5
G 1 0 0 1 1 1 4
C 0 0 1 1/2 1 1 31/2
F 0 0 0 1/2 1 1 21/2
B 0 0 0 0 0 1 1
E 0 0 0 0 0 0 0

最高スコア– 5 –を見て、スコアが少なくともこれほど高い、つまり{A、D}の候補者(コープランドの勝者)を検討します。これらは確かにスミスセットに属しており、敗北しない候補者は追加する必要があります。無敗の候補を見つけるために、{A、D}を含む左上の2×2の正方形の下の表のセルを調べます(この正方形は破線の境界線で示されています)。問題のセルは表で黄色で網掛けされています。これらのセルの中で最も低い(位置的に)非ゼロのエントリ、つまりG行のセルを見つける必要があります。この行までのすべての候補、および同じスコアの下位行をセットに追加する必要があります。セットは{A、D、G}に展開されます。

ここで、考慮する必要のある新しいセルを調べます。これは、{A、D、G}を含む左上の正方形の下にあるセルですが、すでに説明した最初の2列のセルは除きます。注意が必要なセルは淡い青色で表示されます。前と同じように、新しいセルの中で位置的に最も低い非ゼロエントリを見つけ、その下にあるすべての行と、それと同じスコアを持つすべての行を、現在{A、D、G、C}で構成される拡張セットに追加します。 。

スミスセットに属することがわかっている4つのメンバーの下の新しいセルに対して操作を繰り返します。これらはピンク色で表示され、{A、D、G、C}のいずれにも負けていない候補を見つけることができます。ここでも、セットに追加するFが1つだけあります。

考慮されるセルは淡い緑色で網掛けされており、すべてのエントリがゼロであるため、セットに新しい候補を追加する必要はありません。したがって、{A、D、G、C、F}として固定されます。また、ブラックボックス内のすべてのエントリがゼロであることに気付くことで、その上のすべての候補がその中のすべての候補を打ち負かすことを確認できます。

次のC関数は、与えられた2倍の結果行列rと2倍のコープランドスコアの配列sに対して設定されたスミスのカーディナリティを返すことによってアルゴリズムを示しています。n人の候補者がいます。r i j、より多くの有権者がjよりiよりもiを好む場合は2 、数が等しい場合は1、より多くの有権者がiよりもj好む場合は0です 。s iは、 rijのj合計です。 候補者は、コープランドスコアの降順でソートされていると想定されます。

  int smithset int ** r int * s int n     
  { int row col lhs rhs ;   
    for rhs = 1 lhs = 0 ; lhs < rhs ; lhs = rhs rhs = row + 1 
    { for (; rhs < n && s [ rhs ] == s [ rhs -1 ]; rhs ++ ; /*この行はオプションです*/   
      for col = rhs row = n ; col == rhs && row > = rhs ; row- for col = lhs ; col < rhs && r [ row -1 ] [ col ] == 0 ; col ++ ; }   
    
    lhsを返す; }   
  

スミスの方法

スミスセットは、ランク付けされた投票方法を定義していると見なすことができます...

スミスセットのすべてのメンバーが勝者です。通常、別の方法と組み合わせます。[3]

スミスの組み合わせの方法の注目すべき例は、スミス/ IRVです。これは、候補のフィールドをスミスセットに減らし、このセットに複数の要素がある場合は、優先順位付投票を使用して同点を打ち破ります。より複雑な方法(これもIRVを呼び出す)はTideman's Alternativeであり、その記事には2つの方法の重要な特性をリストした表が含まれています。スミス/ミニマックスは、タイを壊すために大幅に異なる手順を使用します。[2]

エリミネーションタイ

Smith /IRVとTideman'sAlternativeの両方のIRVコンポーネントは、最初の優先順位の中で最下位の同点に遭遇することがあります(投票者の数が増えるにつれて、この確率は任意に小さくなります)。そのような結びつきが生じるとき、それは様々な方法で壊されるかもしれません。Smith / IRVの場合、1次投票数が最も少なく、投票数の合計が他のどの候補者よりも少ないすべての候補者のセットを、結果を変更せずに削除できます。Tideman's Alternativeは、単一の除去ごとにスミスセットを再計算するため、この方法で最適化することはできません。

優先順位付投票では、同じランクの2人の候補者がいる投票用紙を受け入れることはできませんが、投票者が候補者間の同点を示した場合でも、フィールドをスミスセットに減らすことは可能です。スミス以外の候補者を排除 した後、第一候補のランキングが等しい投票用紙は、廃棄する必要があります。

も参照してください

参照

  1. ^ http://dss.in.tum.de/files/brandt-research/dodgson.pdf [裸のURLPDF ]
  2. ^ a b R. B.ダーリントン、「コンドルセとミニマックス投票システムは最高ですか?」(v8、2021)。
  3. ^ Condorcet.orgミラーページ

さらに読む

  • ワード、ベンジャミン(1961年)。「多数決と割り当て」。Journal ofConflictResolution5(4):379–389。土井10.1177/002200276100500405 多数決に基づく一連の意思決定の分析では、スミスセットとシュワルツセットについて説明します。
  • スミス、JH(1973)。「可変選挙人による選好の集約」。エコノメトリカ計量経済学会。41(6):1027–1041。土井10.2307/1914033JSTOR1914033 _ ペアワイズ選挙が単純な多数決に基づいている場合に満たされる一般化されたコンドルセット基準のバージョンを紹介します。支配集合の場合、集合内の候補は、集合内にない候補よりも集合的に優先されます。しかし、スミスは最小の支配集合のアイデアについては説明していません。
  • フィッシュバーン、ピーターC.(1977)。「コンドルセット社会選択関数」。応用数学に関するSIAMジャーナル33(3):469–489。土井10.1137/0133030 スミスの一般化されたコンドルセット基準を最小の支配集合に狭め、それをスミスのコンドルセット原理と呼びます。
  • シュワルツ、トーマス(1986)。集合的選択の論理ニューヨーク:コロンビア大学出版。 最適な集合的選択のための可能な基準として、スミスセット(GETCHAという名前)とシュワルツセット(GOTCHAという名前)について説明します。
  • Somdeb Lahiri(nd)、「グループおよび多基準意思決定」。選択セットのいくつかのプロパティの概要を説明します。

外部リンク