スミスセット

シュワルツ集合は、同票を考慮しない点を除けば、スミス集合と同等である。厳密に言えば、シュワルツ集合とは、その集合内のどの候補者も、自分を破るどの候補者に対しても、厳密な勝利経路を持つような集合のことである。

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

• セット内の候補とペアワイズで同点の候補、
• セット内の候補者を破る候補者。

第二種の候補は、第一種の候補が追加された後にのみ存在できることに注意してください。

定理：支配集合は入れ子構造になっている。つまり、選挙における任意の2つの支配集合のうち、一方は他方の部分集合である。

証明：仮に、互いに部分集合ではない2つの支配集合DとEが存在すると仮定する。すると、d ∈ D、e ∈ Eとなるような候補dが存在しなければならない。しかし、仮定により、 dはDに含まれないすべての候補（eを含む）を打ち負かし、 eはEに含まれないすべての候補（ dを含む）を打ち負かすことになる。これは矛盾である。∎

系：したがって、スミス集合は最小の空でない支配集合であり、かつ適切に定義されている。

定理： Dが支配集合である場合、 Dの要素がコープランドスコアが少なくともθD_以上の候補者となる_{ような閾値θD}が存在する。（候補者のコープランドスコアは、その候補者が打ち負かした他の候補者の数と、その候補者と同点だった他の候補者の数の半分を足した数である。）

証明： Dの要素のうち、コープランドスコアが最小となる要素をdとし、このスコアをθDとする_{。ここで、} Dに属さない候補eが_θD以上のコープランドスコアを持つ。dはDに属し、 eはDに属しないため、 dはeに勝つ。eのコープランドスコアがdのスコア以上となるためには、 eがdよりも高いスコアを獲得するな第三の候補fが存在しなければならない。fがDに属する場合、eに勝てないDの要素が存在し、 fがDに属さない場合、 dに勝てないD外の候補が存在することになり、いずれの場合も矛盾が生じる。∎

スミス基準を満たす選挙方法は、コンドルセ勝者基準にも適合します。なぜなら、コンドルセ勝者がいる場合、それはスミス集合内の唯一の候補者だからです。スミス方式は、コンドルセ敗者基準にも適合します。なぜなら、コンドルセ敗者はスミス集合には決して含まれないからです。また、スミス集合はMMC集合の部分集合であるため、相互多数決基準も意味します。 ^{[ 2 ]}逆に、これら3つの多数決基準（相互多数決、コンドルセ敗者、コンドルセ勝者）のいずれかに不合格となる方法は、スミス基準にも不合格となります。

スミス基準は、順位付けペア、シュルツェ法、ナンソン法、その他いくつかの方法で満たされます。さらに、スミス集合を見つけてその外にある候補を除外することで、どの投票方法もスミス基準を満たすように修正できます。

例えば、投票方法であるスミス//ミニマックス方式では、スミス集合内の候補者にミニマックス法を適用します。別の例として、タイドマン方式があります。この方式では、スミス集合外の候補者を排除するのと、最多得票で敗れた候補者を排除する（即時決選投票に類似）ことを交互に繰り返し、コンドルセ方式の勝者が見つかるまで続けます。別の方法としては、投票方法の順位で最も上位に位置するスミス集合のメンバーを選出するという方法もあります。

コンドルセ基準を満たさない手法は、スミス基準も満たさない。ただし、コンドルセ基準を満たす手法の中には（ミニマックス法など）、スミス基準を満たさないものもある。

このアルゴリズムは、例を通して詳細に説明することができます。結果行列が以下のようになっていると仮定します。

メインテーブルのエントリは、最初の候補者が2番目の候補者よりも多くの有権者から支持された場合は1、その逆の場合は0、同数の場合は1/2となります。最後の列には、最初の候補者のコープランドスコアが示されています。

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

最高得点 (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人だけなので、Fを集合に追加します。

検討対象となるセルは薄緑色で網掛けされており、すべてのエントリがゼロであるため、新たな候補をセットに追加する必要はありません。したがって、セットは{A,D,G,C,F}に固定されます。また、黒いボックス内のすべてのエントリがゼロであることから、その上のすべての候補が、その中のすべての候補を上回っていることが確認できます。

以下の C 関数は、与えられた 2 倍化結果行列rと2 倍化コープランド スコアの配列sに対して、スミス集合の要素数を返すことでアルゴリズムを示します。候補者はn名います。r i _jは、  iをjより好む有権者の数がjをiより好む有権者の数より多い場合は 2、同じ場合は 1、jをiより好む有権者の数がiをjより好む有権者の数より多い場合は 0となります。s _iは、 jに関するr _{i 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 ++ ); } return lhs ; }