In
voting system
An electoral system or voting system is a set of rules that determine how elections and referendums are conducted and how their results are determined. Electoral systems are used in politics to elect governments, while non-political elections m ...
s, the Schwartz set is the
union of all Schwartz set components. A Schwartz set component is any non-empty set ''S'' of candidates such that
# Every candidate inside the set ''S'' is pairwise unbeaten by every candidate outside ''S''; and
# No non-empty
proper subset
In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset o ...
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 is the scientific study of politics. It is a social science dealing with systems of governance and power, and the analysis of political activities, political thought, political behavior, and associated constitutions and la ...
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, 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 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
In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset o ...
of the
Smith set. 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, if
* 3 voters prefer candidate A to B to C,
* 1 voter prefers candidate B to C to A,
* 1 voter prefers candidate C to A to B,
* 1 voter prefers 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
In computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a directed weighted graph with p ...
in time
Θ(''n''
3) or with a version of
Kosaraju's algorithm in time
Θ(''n''
2).
Complying methods
The
Schulze method always chooses a winner from the Schwartz set.
See also
*
Smith set
*
Condorcet criterion
*
Condorcet method
A Condorcet method (; ) is an election method that elects the candidate who wins a majority rule, majority of the vote in every head-to-head election against each of the other candidates, that is, a candidate preferred by more voters than any oth ...
*
Preorder
In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special c ...
*
Partial order
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
References
* In an analysis of serial decision making based on majority rule, describes the Smith set and the Schwartz set, but apparently fails to recognize that the Schwartz set can have multiple components.
* Introduces the notion of the Schwartz set at the end of the paper as a possible alternative to maximization, in the presence of cyclic preferences, as a standard of rational choice.
* Gives an axiomatic characterization and justification of the Schwartz set as a possible standard for optimal, rational collective choice.
* Proves that the Schwartz set is the set of undominated elements of the transitive closure of the pairwise preference relation.
*{{cite book , first=Thomas , last=Schwartz , year=1986 , title=The Logic of Collective Choice , publisher=Columbia University Press , location=New York , isbn=0-231-05896-9 Discusses the Smith set (named GETCHA) and the Schwartz set (named GOCHA) as possible standards for optimal, rational collective choice.
External links
Example algorithms to calculate the Schwartz set
Voting theory