スミスセット

スミス集合^{[注 1]}はトップサイクルとも呼ばれ、コンドルセ勝者の考え方をそのような勝者が存在しない場合に一般化します。 これは、候補者のサイクルを単一のコンドルセ勝者であるかのようにまとめて扱うことを可能にします。^[1]スミス集合から常に候補者を選出する投票システムは、スミス基準を満たします。スミス集合とスミス基準はどちらも数学者ジョン・H・スミスにちなんで名付けられました。

スミス集合は、選挙結果に対する最適な選択の 1 つの基準を提供します。代替の、より厳格な基準は、ランダウ集合によって与えられます。

スミス集合は、集合S内のすべての候補者が、集合S外のすべての候補者によってペアで負けない最小の集合として正式に定義されます。

あるいは、それを、それらを破る任意の候補者への （非厳密な）ビートパスを持つすべての候補者の集合として定義することもできます。

それぞれの候補者がペアでその集合外のすべての候補者に勝利する候補者の集合は、支配集合と呼ばれます。したがって、スミス集合は最小の支配集合とも呼ばれます。

シュワルツ集合はスミス集合と同等ですが、同票を無視します。正式には、シュワルツ集合とは、集合内のどの候補者も、自分を破ったどの候補者に対しても厳密な ビートパスを持つ集合です。

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

• セット内の候補者とペアで同点の候補者、
• セット内の候補者を破った候補者。

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

• スミス集合は常に存在し、空ではありません。また、明確に定義されています (次のセクションを参照)。
• スミス集合には、ペアワイズ同点のため、またはコンドルセのパラドックスのようなサイクルのため、複数の候補が存在する場合があります。
• コンドルセ勝者が存在する場合、それはスミス集合の唯一のメンバーです。弱いコンドルセ勝者が存在する場合、それらはスミス集合に含まれます。
• スミス集合は常に、候補者の最小の相互多数派優先集合の部分集合である。^[2]

定理:支配集合は入れ子になっています。つまり、選挙における任意の 2 つの支配集合のうち、一方は他方のサブセットです。

証明:逆に、どちらも他方の部分集合ではない2 つの支配集合DとEが存在するとします。このとき、 d ∈ D、 e ∈ Eの候補が存在し、 d ∉ Eかつe ∉ Dである必要があります。しかし、仮定により、 d はDに含まれないすべての候補( eを含む)に勝ち、 e はEに含まれないすべての候補( dを含む)に勝つ、矛盾が生じます。∎

系:スミス集合は最小の空でない支配集合であり、明確に定義されているということになります。

定理: D が支配集合である場合、 Dの要素がコープランド スコアが少なくとも θ _Dである候補者だけになる_{ようなしきい値 θ D}が存在します。(候補者のコープランド スコアは、その候補者が勝った他の候補者の数と、同点の候補者の数の半分を加えたものです。)

証明:最小のコープランドスコアを持つDの要素としてd を選択し、このスコアを θ _{Dと同一視します。ここで、 θ D}以上のコープランドスコアを持つ候補者e ∉ Dがあるとします。dはDに属し、 e は属さないため、 d はe に勝つことになります。また、 e のコープランドスコアがdのものと少なくとも等しいためには、 e がdよりも良いスコアを獲得する者f が存在する必要があります。 f ∈ Dの場合、e に勝てないDの要素が存在し、 f ∉ Dの場合、 d に勝てないDの外部の候補者が存在し、どちらにしても矛盾が生じます。 ∎

スミス基準は、コンドルセ基準よりも強力な多数決の考え方を形式化した投票システムの基準です。投票システムが常にスミス集合から候補者を選択する場合、その投票システムはスミス基準を満たします。

あまり一般的ではないが、スミス効率的という用語は、スミス集合から選択する方法にも使用されている。^[3]

以下は、コンドルセ勝者がいない選挙区の例です。候補者は A、B、C、D の 4 人です。投票者の 40% は、D>A>B>C と評価しています。投票者の 35% は、B>C>A>D と評価しています。投票者の 25% は、C>A>B>D と評価しています。スミス集合は {A、B、C} です。スミス集合の 3 人の候補者はすべて、D よりも多数派が好まれています (60% がそれぞれを D よりも多く評価しているため)。スミス集合は {A、B、C、D} ではありません。定義では、他の条件を満たす最小のサブセットが要求されるためです。スミス集合は {B、C} ではありません。B は A よりも多数派が好まれておらず、65% が A を B よりも多く評価しているためです (など)。

この例では、ミニマックスでは A と D が同点ですが、スミス//ミニマックスでは A が勝ちます。

上記の例では、スミス セットの 3 人の候補者は「じゃんけん」の多数決サイクルにあります。つまり、A は B より 65% 多く、B は C より 75% 多く、C は A より 60% 多くランク付けされます。

スミス基準に適合する選挙方法は、コンドルセ勝者基準にも適合します。コンドルセ勝者がいる場合、それはスミス集合の唯一の候補者だからです。スミス方法はコンドルセ敗者基準にも適合します。コンドルセ敗者がスミス集合に含まれることは決してないからです。また、スミス集合はMMC集合のサブセットであるため、相互多数基準も意味します。 ^[2]逆に、これら3つの多数派基準（相互多数、コンドルセ敗者、コンドルセ勝者）のいずれかを満たさない方法は、スミス基準にも満たないでしょう。

スミス基準は、ランク付けペア、シュルツ法、ナンソン法、およびその他のいくつかの方法によって満たされます。さらに、スミス集合を見つけてその外側の候補者を排除することで、任意の投票方法をスミス基準を満たすように変更できます。

たとえば、投票方法 Smith//Minimax は、Smith 集合内の候補者に Minimax を適用します。別の例としては、Tideman 代替法があります。これは、Condorcet 勝者が見つかるまで、Smith 集合外の候補者を排除することと、多数決で敗退した候補者を排除すること ( instant-runoffに類似) を交互に繰り返します。別のアプローチは、投票方法の順位が最も高い Smith 集合のメンバーを選出することです。

コンドルセ基準を満たさない方法は、スミス基準も満たしません。ただし、一部のコンドルセ法 (ミニマックスなど) はスミス基準を満たさない場合があります。

スミス集合には、コープランド集合とランダウ集合がサブセットとして含まれます。

これにはバンクス集合と二党集合も含まれる。スミス集合の他の部分集合も数多く定義されている。^[4]

スミス集合は、フロイド・ワーシャルアルゴリズムで^はΘ ⁽ n3 )時間で、コサラジュアルゴリズムではΘ ( n2 )時間で計算できる。

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

ここで、メインテーブルのエントリは、第 1 候補が第 2 候補よりも支持された投票者の数が第 2 候補を第 1 候補よりも支持された投票者の数より多い場合は 1 になり、逆の関係が成立する場合は 0 になります。1/2同点の場合は、最後の列に最初の候補者の Copeland スコアが表示されます。

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

最高スコア (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 倍の Copeland スコアの配列sに対する Smith セットの濃度を返すことで、アルゴリズムを示しています。候補者はn人います。r _{i j}は、 iをj より好む投票者が jをiより好む投票者より多い場合は 2 、数が等しい場合は 1、 j を i より好む投票者が i を j より好む投票者より多い場合は 0 です。 s iは、r i  jの_jに対する_合計 です。候補者は、 Copeland スコアの降順で並べ替えられているものと想定されます。

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 ++ ); } return lhs ; }         
      
                    
                
                  
                   
  
   

• コンドルセ基準
• コンドルセ法
• ランダウ集合
• 予約注文
• 部分的な順序
• 最大要素と最小要素- スミス集合は、特定の半順序の最大要素として定義できます。

• Ward, Benjamin (1961). 「多数決と配分」.紛争解決ジャーナル. 5 (4): 379–389. doi :10.1177/002200276100500405. S2CID  145231466.多数決に基づく連続意思決定の分析では、スミス集合とシュワルツ集合について説明します。
• スミス、JH ( 1973)。 「可変有権者による選好の集約」。Econometrica 41 (6)。計量経済学会: 1027–1041。doi :10.2307 / 1914033。JSTOR  1914033。一般化されたコンドルセ基準のバージョンを導入します。これは、一対一の選挙が単純な多数決に基づいており、任意の支配集合について、集合内の任意の候補者が集合外の任意の候補者よりも集合的に好まれる場合に満たされます。ただし、スミスは最小の支配集合のアイデアについては説明していません。
• フィッシュバーン、ピーター C. ( 1977)。「コンドルセの社会的選択関数」。SIAM応用数学ジャーナル。33 (3): 469–489。doi :10.1137/0133030。スミスの一般化されたコンドルセ基準を最小の支配集合に絞り込み、それをスミスのコンドルセ原理と呼びます。
• シュワルツ、トーマス（1986年）。集団選択の論理。ニューヨーク：コロンビア大学出版局。最適な集団選択の可能な標準として、スミス集合 (GETCHA という名前) とシュワルツ集合 (GOTCHA という名前) について説明します。
• シュワルツ、トーマス（1970）。「合理的政策評価の可能性について」。理論と決定。1 ：89-106。doi ： 10.1007/BF00132454。S2CID 154326683  。 論文の最後では、循環的な選好が存在する場合の合理的選択の基準としての最大化の代替案として、シュワルツ集合の概念を紹介しています。
• シュワルツ、トーマス (1972)。「合理性と最大値の神話」。Noûs 6 ( 2) 。Noûs、第6巻、第2号: 97–117。doi :10.2307/2216143。JSTOR  2216143。 最適かつ合理的な集団選択の可能な標準としてのシュワルツ集合の公理的な特徴付けと正当性を示します。
• デブ、ラジャット（ 1977年）。「シュワルトの法則について」経済理論ジャーナル16 ： 103-110。doi ：10.1016/0022-0531（77）90125-9。 シュワルツ集合が、ペアワイズ選好関係の推移閉包の非劣要素の集合であることを証明します。
• グリーン・アーミテージ、ジェームズ。「単一勝者選挙のための 4 つのコンドルセ-ヘアハイブリッド法」
• Somdeb Lahiri (nd)、「グループおよび多基準意思決定」。選択セットのいくつかの特性について概説します。