Uncovered set: Difference between revisions
no edit summary
No edit summary |
No edit summary |
||
Line 5:
{{definition|Select the candidate or candidates that are not Fishburn losers. A candidate ''i'' is a Fishburn loser if there is some other candidate ''j'' such that every candidate that pairwise beats ''j'' also pairwise beats ''i'' and there is at least one candidate that pairwise beats ''i'' but does not pairwise beat ''j''.}}An equivalent definition is that it is the set of all candidates X such that for each candidate X, they either pairwise beat each candidate not in the set, or for those candidates not in the set they don't pairwise beat (i.e. directly), they pairwise beat some candidate who pairwise beats that candidate (i.e. indirectly).<ref>https://arxiv.org/pdf/1905.01401.pdf Uncovered. The uncovered set of a tournament graph consists of those candidates A ∈ C such that for any other candidate B, either there is an edge from A to B, or there is another candidate C so that there are an edge from A to C and an edge from C to B [19].</ref> In this sense, it is related to the concept of a [[beatpath]]. Another definition is: <blockquote>An alternative a is said to cover alternative b whenever every alternative dominated by b is also dominated by a.<ref>https://dss.in.tum.de/files/brandt-research/tsolutions.pdf</ref> </blockquote>Yet another definition: <blockquote>The ''uncovered set'' is the set of all outcomes ''x'' such that there is no outcome beating ''x'' and all the outcomes that ''x'' beats.<ref>https://www.jstor.org/stable/41105997?seq=1</ref> </blockquote>When there are pairwise ties, a likely generalized (yet equivalent when there are no pairwise ties) definition is: <blockquote>In voting systems, the '''Landau set''' (or '''uncovered set''', or '''Fishburn set''') is the set of candidates ''x'' such that for every other candidate ''z'', there is some candidate ''y'' (possibly the same as ''x'' or ''z'') such that ''y'' is not preferred to ''x'' and ''z'' is not preferred to ''y''. </blockquote>The uncovered set is a nonempty subset of the [[Smith set]]. The reason is that every candidate in the Smith set is preferred to every candidate not in the Smith set, therefore each candidate in the Smith set can be considered a candidate ''x'' and be their own candidate ''y''; since a candidate can't be preferred to themselves (''y'' is not preferred to ''x''), and since candidates in the Smith set being preferred to every candidate not in the Smith set implies that candidates not in the Smith set are not preferred to candidates in the Smith set (''z'' is not preferred to ''y''), the uncovered set must be a subset of the Smith set.
== Example ==
'''Independence of covered alternatives''' says that if one option (X) wins an election, and a new alternative (Y) is added, X will win the election if Y is not in the [[uncovered set]]. Independence of covered alternatives implies [[Independence of Smith-dominated Alternatives]] (since independence of covered alternatives implies that one can eliminate everyone outside of the uncovered set without changing the winner, and the uncovered set is a subset of the Smith set, therefore eliminating everyone outside of the Smith set also can't change the winner), which further implies [[Smith criterion|Smith]] and thus [[Condorcet criterion|Condorcet]]. If a method is independent of covered alternatives, then the method fails monotonicity if perfect ties can always be broken in favor of a choice W by using ballots ranking W first.▼
Suppose the following pairwise preferences exist between four candidates (v, x, y, z) (table organized by [[Copeland]] ranking):
{| class="wikitable"
|+
!
!x
!y
!z
!v
!Copeland score
|-
|x
| ---
|Win
|Win
|Lose
|(2-1)=1
|-
|y
|Lose
| ---
|Win
|Win
|(2-1)=1
|-
|v
|Win
|Lose
|Lose
| ---
|(1-2)=-1
|-
|z
|Lose
|Lose
| ---
|Win
|(1-2)=-1
|}
Notice that the Smith set includes all candidates (this can be seen by observing that there is a [[beatpath]] of x>y>z>v>x). But the uncovered set is all candidates except z; this is because y>z and all candidates who beat y (just x) also beat z. <ref>https://economics.stackexchange.com/a/27691</ref> (Notice that the Copeland set is even smaller; it is just v and x).
== Notes ==
▲'''Independence of covered alternatives''' says that if one option (X) wins an election, and a new alternative (Y) is added, X will win the election if Y is not in the [[uncovered set]]. Independence of covered alternatives implies [[Independence of Smith-dominated Alternatives]] (since independence of covered alternatives implies that one can eliminate everyone outside of the uncovered set without changing the winner, and the uncovered set is a subset of the Smith set, therefore eliminating everyone outside of the Smith set also can't change the winner), which further implies [[Smith criterion|Smith]] and thus [[Condorcet criterion|Condorcet]]. If a method is independent of covered alternatives, then the method fails monotonicity if perfect ties can always be broken in favor of a choice W by using ballots ranking W first.
The Banks set<ref>http://spia.uga.edu/faculty_pages/dougherk/svt_13_multi_dimensions2.pdf "The Banks set (BS) is the set of alternatives resulting from strategic voting in a successive elimination procedure"</ref> (the set of candidates who could win a [[:Category:Sequential comparison Condorcet methods|sequential comparison]] contest for at least one ordering of candidates when voters are strategic), [[Copeland]] set (set of candidates with the highest Copeland score), and Schattschneider set are all subsets of the uncovered set. <ref>https://books.google.com/books?id=yCBqCQAAQBAJ p. 350 "the uncovered set includes the Copeland winning set and the Banks set" </ref> <ref>https://link.springer.com/article/10.1007/BF00126302 "We examine the [...] uncovered set [...] and [...] two important subsets of the uncovered set, the Banks set and the Schattschneider set.</ref>
| |||