Set theory

From Electowiki
Jump to navigation Jump to search

Set theory is the investigation of sets, which can be informally considered groups of objects. Within the context of voting theory, sets are often used to discuss voting method criteria (which sets of candidates should be eligible to win or not under particular circumstances, for example) and certain other things, such as the Nakamura number.

Many voting method criteria can be thought of in terms of sets. For example, the unanimity criterion requires that if between two candidates, all voters prefer the former over the latter, then the latter candidate must not win; this can be interpreted in set theory (when solely looking at the winner(s) of the election) as "the winner set selected by a voting method must always be a subset of the largest "unanimity-compliant" set of candidates such that there is no candidate who is unanimously preferred over one of the candidates in the unanimity-compliant set."

In the context of ranked methods, several sets have been proposed for the purposes of identifying which candidates or groups of candidates are better than others. One of the most notable of these is the Smith set.

Definitions[edit | edit source]

Subset: One set is a subset of another set if all elements in the first set can be found in the other set.

Proper subset: between two sets, the former set contains only elements from the latter set, but the latter set contains at least one more element than the former set.

Superset: If one set has every element that another set has, then it is a superset.

Singleton: A set with exactly one alternative in it.

An inclusion-wise maximal set among a collection of sets is a set that is not a subset of some other set in the collection. An inclusion-wise minimal set among a collection of sets is a set in the collection that is not a superset of any other set in the collection.

Condorcet[edit | edit source]

Because of Condorcet cycles, there isn't always a single unambiguously best candidate according to the Condorcet criterion. Because of this, most Condorcet methods narrow down their selection to a best set of candidates when selecting a winner. The Smith set is by far the most common one, with some Condorcet methods choosing from more specific subsets of the Smith set, such as the Schwartz set. Criteria such as the Smith criterion show which sets each method chooses from.

Some Condorcet methods pass IIA-like properties related to the sets they choose from, such as Independence of Smith-dominated Alternatives.

Multi-winner elections[edit | edit source]

In the context of Proportional Representation for multi-winner elections, there are several set-related concepts that are often used to decide who should win and who should not. For example, if the following ranked votes are cast in a 2-winner election:

 49 A>B>D
 2 B>D  
 49 C>B>D   

Droop Proportionality for Solid Coalitions would require that one candidate from the set (A) should win, and one candidate from the set (B) should win, since for each of them, a different Droop quota of voters prefers them above all other candidates. So using combinatorics (a calculator to do combinatorics can be found at https://www.mathsisfun.com/combinatorics/combinations-permutations-calculator.html), the only Droop-PSC compliant winner set would be (A, B) i.e. A and B must win the election.

Notes[edit | edit source]

Order theory is often used for more advanced discussions on ranked methods. For example, a beatpath is an ordering of candidates such that the first candidate in the ordering pairwise beats the second, the second pairwise beats the third, etc. all the way until the last candidate.

See also[edit | edit source]