Schwartz set

"Schwartz criterion" redirects here. For the term in statistics (model comparison), see Schwarz criterion.

In voting systems, 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

  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 Thomas Schwartz.

Properties

Smith set comparison

The Schwartz set is closely related to and is always a subset 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, given:

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 time Θ(n3) or with a version of Kosaraju's algorithm in time Θ(n2).

Complying methods

The Schulze method always chooses a winner from the Schwartz set.

See also

References

External links

This article is issued from Wikipedia - version of the 8/4/2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.