User:DCary/WIP/Schwartz set

From electowiki

The Schwartz set is defined for an election in which candidates are evaluated in pair-wise contests and each such contest results either in a tie or exactly one of the two candidates beating the other.

Definition

The Schwartz set is the union of all sets that are Schwartz set components.

A Schwartz set component is any non-empty set of candidates, such that:

  1. Every candidate inside the set pair-wise beats or ties any other candidate outside the set, and
  2. No non-empty proper (smaller) subset of the set fulfills the first property


Beatpath Order

The Schwartz set is the union of all of the cycle equivalence classes that are maximal in the beatpath order. A set is a Schwartz set component if and only if it is a cycle equivalence class that is maximal in the beatpath order.

This characterization of the Schwartz set follows from two characteristics of any set S that fullfills the first property of a Schwartz set component:

  • No beatpath starts outside and finishes inside S.
  • If X is in S, then the set S \ {Y : Y is in S and there is no beatpath from Y to X} also fullfills the first property of a Schwartz set component.


Smith Set

The Schwartz set is a subset of the Smith set. The Schwartz set is equal to the Smith set if and only if every candidate in the Schwartz set pair-wise beats every candidate outside the Schwartz set, that is, no candidate in Schwartz set pair-wise ties with any candidate outside of the Schwartz set.

The Smith set can be constructed from the Schwartz set by repeatedly adding two types of candidates until no more such candidates exist outside the set:

  • candidates that have pair-wise ties with candidates in the set,
  • candidates that start a beatpath that ends in the set.

Note that candidates of the second type can only exist after candidates of the first type have be added.


Other Characteristics

Other characteristics of the Schwartz set include:

  • If a Condorcet winner exists, it is the one and only candidate in the Schwartz set.
  • All weak Condorcet winners are in the Schwartz set. The weak Condorcet winners are the candidates in the Schwartz set that are not in a cycle, i.e. they are each in their own Schwartz set component.
  • If the Schwartz set contains only one candidate, it is the weak Condorcet winner. If that candidate has no pair-wise ties, it is the Condorcet winner.
  • The Schwartz set is never empty. At least one Schwartz set component exists. (Assuming the number of candidates is finite.)
  • There is no beatpath that starts outside and ends inside a Schwartz set component.
  • Schwartz set components are disjoint. No candidate is in more than one Schwartz set component.
  • Any two candidates from different Schwartz set components are pair-wise tied with each other.
  • Any two distinct candidates X and Y from the same Schwartz set component are in a cycle with each other; there is a beatpath from X to Y and there is a beatpath from Y to X.
  • For any candidate Y not in the Schwartz set, there is at least one candidate X in the Schwartz set that has a beatpath from X to Y. However, it is possible that there exists a candidate outside the Schwartz set that is pair-wise tied with every candidate in the Schwartz set.
  • A Schwartz set component may contain 1, 3, or more candidates, but never exactly two candidates.
  • If there are no pair-wise ties, as is typical in larger-scale elections, the Schwartz set will consist of either:
    • a single candidate that is the Condorcet winner, or
    • a set of three or more candidates that are all in cycles with each other.


Examples

Examples with 3 candidates are here.

An example with 12 candidates is here.

Retrieved from "https://electowiki.org/wiki/User:DCary/WIP/Schwartz_set?oldid=3535"