Set theory: Difference between revisions
no edit summary
No edit summary |
|||
| (8 intermediate revisions by the same user not shown) | |||
Line 1:
'''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 [https://en.wikipedia.org/wiki/Nakamura_number Nakamura number].
=== Voting criteria ===
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
Some criteria dealing with sets are:
[[Mutual majority criterion]], [[Proportionality for Solid Coalitions]], [[Cloneproofness]]
=== Ranked method candidate sets ===
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]]; see the below Condorcet section for other sets. Note that several set-related criteria can be thought of as requiring the election of a candidate from a smallest set of candidates meeting some requirement, because though there may be several sets meeting that requirement, only the smallest of these sets (supposing all of the sets are nested) ensures that the voting method elected someone in every possible set meeting the requirement.
== Definitions ==
'''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.
'''Nested''': When several sets are all either subsets or supersets of each other. <blockquote>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.</blockquote>
== Notation ==
A set can be referred to using parentheses i.e. [A, B] refers to the objects A and B as a set.
See [https://en.wikipedia.org/wiki/Set_theory#Basic_concepts_and_notation] for more details.
== Combinatorics ==
[[W:Combinatorics|Combinatorics]] is the study of how to create combinations and permutations of objects. It goes hand in hand with set theory. In the context of voting theory, combinatorics is often used when analyzing [[Proportional Representation]] and [[PSC]] to determine which candidates or groups of candidates should win. In this context, it can be used to find all possible [[Winner set|winner sets]] and compare them to each other.
A good combinatorics calculator: <ref>{{Cite web|url=https://www.mathsisfun.com/combinatorics/combinations-permutations-calculator.html|title=Combinations and Permutations Calculator|website=www.mathsisfun.com|access-date=2020-05-14}}</ref>
== Condorcet ==
Because of [[Condorcet cycle|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.
See [[:Category:Condorcet-related sets|Category:'''Condorcet-related sets'''.]]
Some Condorcet methods pass [[IIA]]-like properties related to the sets they choose from, such as [[Independence of Smith-dominated Alternatives]].
== Multi-winner elections ==
=== Proportional representation ===
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:
Line 13 ⟶ 47:
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
When discussing [[PSC]], one can look at subfactions of [[faction]]<nowiki/>s by looking at subsets of the faction's overall preferred candidates. Different notations are possible for this; for example: <blockquote><small>Since (B1, B2, B3, B4) is its own Droop semi-solid coalition (actually a solid coalition as well; 50 voters, the 2nd through 4th lines, prefer them over all other candidates), we can come up with the following visualization of the semi-solid coalition-based proportionality guarantees each set of candidates has:</small>
D:1, ((A, B1):1, (B1-4):1, (C, B3):1):2<ref>{{Cite web|url=https://www.reddit.com/r/EndFPTP/comments/euiup2/a_new_pr_concept_of_semisolid_coalitions/|title=r/EndFPTP - A new PR concept of "semi-solid coalitions"|website=reddit|language=en-US|access-date=2020-05-14}}</ref></blockquote>
== See also ==
*[[Order theory]]
*[[Stable Winner Set]]
[[Category:Binary relations theory]]
| |||