In voting system

Voting system

A voting system or electoral system is a method by which voters make a choice between options, often in an election or on a policy referendum....

s, the Schwartz set is the union

Union (set theory)

In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...

 of all Schwartz set components. A Schwartz set component is any non-empty set S of candidates such that

1. Every candidate inside the set S is pairwise unbeaten by every candidate outside S; and
2. No non-empty proper subset of S fulfills the first property.

A set of candidates that meets the first requirement is also known as an undominated set.

The Schwartz set provides one standard of optimal choice for an election outcome. Voting systems that always elect a candidate from the Schwartz set pass the Schwartz criterion. The Schwartz set is named for political scientist

Political science

Political Science is a social science discipline concerned with the study of the state, government and politics. Aristotle defined it as the study of the state. It deals extensively with the theory and practice of politics, and the analysis of political systems and political behavior...

 Thomas Schwartz.

Properties

• The Schwartz set is always non-empty—there is always at least one Schwartz set component.
• Any two distinct Schwartz set components are disjoint.
• If there is a Condorcet winner
  Condorcet criterion
  The Condorcet candidate or Condorcet winner of an election is the candidate who, when compared with every other candidate, is preferred by more voters. Informally, the Condorcet winner is the person who would win a two-candidate election against each of the other candidates...
  
  , it is the only member of the Schwartz set. If there is only one member in the Schwartz set, it is at least a weak Condorcet winner.
• If a Schwartz set component contains only a single candidate, that candidate is a weak Condorcet winner. If a Schwartz set component contains multiple candidates, they are all in a beatpath cycle with each other, a top cycle.
• Any two candidates that are in different Schwartz set components are pairwise tied with each other.

Smith set comparison

The Schwartz set is closely related to and is always a subset

Subset

In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

 of the Smith set

Smith set

In voting systems, the Smith set, named after John H. Smith, is the smallest non-empty set of candidates in a particular election such that each member beats every other candidate outside the set in a pairwise election. The Smith set provides one standard of optimal choice for an election outcome...

. The Smith set is larger if and only if a candidate in the Schwartz set has a pairwise tie with a candidate that is not in the Schwartz set.
For example, given:

• 3 voters preferring candidate A to B to C
• 1 voter preferring candidate B to C to A
• 1 voter preferring candidate C to A to B
• 1 voter preferring candidate C to B to A

then we have A pairwise beating B, B pairwise beating C, and A tying with C in their pairwise comparison, making A the only member of the Schwartz set, while the Smith set on the other hand consists of all the candidates.

Algorithms

The Schwartz set can be calculated with the Floyd-Warshall algorithm

Floyd-Warshall algorithm

In computer science, the Floyd–Warshall algorithm is a graph analysis algorithm for finding shortest paths in a weighted graph and also for finding transitive closure of a relation R...

 in time Θ

Big O notation

In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...

(n³) or with a version of Kosaraju's algorithm

Kosaraju's algorithm

In computer science, the Kosaraju-Sharir algorithm is an algorithm to find the strongly connected components of a directed graph. Aho, Hopcroft and Ullman credit it to an unpublished paper from 1978 by S. Rao Kosaraju and Micha Sharir...

 in time Θ

Big O notation

In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...

(n²).

See also

• Smith set
  Smith set
  In voting systems, the Smith set, named after John H. Smith, is the smallest non-empty set of candidates in a particular election such that each member beats every other candidate outside the set in a pairwise election. The Smith set provides one standard of optimal choice for an election outcome...
  
  
• Condorcet criterion
  Condorcet criterion
  The Condorcet candidate or Condorcet winner of an election is the candidate who, when compared with every other candidate, is preferred by more voters. Informally, the Condorcet winner is the person who would win a two-candidate election against each of the other candidates...
  
  
• Condorcet method
  Condorcet method
  A Condorcet method is any single-winner election method that meets the Condorcet criterion, which means the method always selects the Condorcet winner if such a candidate exists. The Condorcet winner is the candidate who would beat each of the other candidates in a run-off election.In modern...
  
  
• Preorder
  Preorder
  In mathematics, especially in order theory, preorders are binary relations that are reflexive and transitive.For example, all partial orders and equivalence relations are preorders...
  
  
• Partial order

External links

• Example algorithms to calculate the Schwartz set