Uncovered set

From Electowiki
Jump to navigation Jump to search
Wikipedia has an article on:

The uncovered set is defined for a set of rank-order preferences. Usually, the uncovered set is defined only for situations without pairwise ties. When there are no pairwise ties, then the uncovered set is identical to the set called Fishburn winners:

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 every candidate X so that for any Y not in the set, X either beats Y pairwise or X beats someone who beats Y (i.e. X indirectly pairwise beats Y).[1] In this sense, it is related to the concept of a beatpath.

Another definition is:
An alternative a is said to cover alternative b whenever every alternative dominated by b is also dominated by a.[2]
Yet another definition:
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.[3]
When there are pairwise ties, a likely generalized (yet equivalent when there are no pairwise ties) definition is:
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.
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[edit | edit source]

Suppose the following pairwise preferences exist between four candidates (v, x, y, z) (table organized by Copeland ranking):

x y v z Copeland score
x --- Win Lose Win (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, or alternatively by observing that no matter how many candidates you look at from top to bottom, there is still some candidate outside of the group being looked at that one of the candidates in the group lose or tie to). 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. [4] (Notice that the Copeland set is even smaller; it is just x and y).

An alternative way of understanding the uncovered set in this example is to show the size of the smallest-size beatpath from each candidate to another, if one exists (if x>y is 1 here, this means x pairwise beats y. If it's 2, it means x pairwise beats someone who pairwise beats y, etc.). Any candidate with a smallest-size beatpath of 3 or more to another candidate is not in the uncovered set:

Size of smallest-size beatpath

between each pair of candidates

x y v z
x --- 1 Lose 1
y 2 --- 1 1
v 1 2 --- 2
z 2 3 1 ---

Notice that all candidates except z have beatpaths of size 1 or 2, whereas z>y is (z has a smallest beatpath to y of) 3 steps (z>v>x>y), therefore z is not in the uncovered set.

Subsets of the uncovered set[edit | edit source]

The Banks set, Copeland set, Dutta set, and Schattschneider set are all subsets of the uncovered set.[5]

Banks set[edit | edit source]

The Banks set is the set of winners resulting from strategic voting in a successive elimination procedure[6] (the set of candidates who could win a sequential comparison contest for at least one ordering of candidates when voters are strategic).

The Banks set is a subset of the Smith set because when all but one candidate in the Smith set has been eliminated in a sequential comparison election, the remaining Smith candidate is guaranteed to pairwise beat all other remaining candidates, since they are all non-Smith candidates, and thus can't be eliminated from that point onwards, meaning they will be the final remaining candidate and thus win.

Determining if a given candidate is in the Banks set is NP-complete,[7] but it is possible to find some member of the Banks set in polynomial time. One way to do so is to start with a candidate and then keep inserting candidates in some order, skipping those whose insertion would produce a cycle; the winner of the method is then the candidate who pairwise beats every other included candidate.[8]

Dutta set[edit | edit source]

The Dutta set (also known as Dutta's minimal covering set) is the set of all candidates such that when any other candidate is added, that candidate is covered in the resulting set. It is a subset of the Smith set because all candidates in the Smith set cover (i.e. have a one-step beatpath, direct pairwise victory) all candidates not in the Smith set.

Schattschneider set[edit | edit source]

The Schattschneider set is based on spatial voting games, and is a subset of the Banks set.[9] It is rarely referenced.

Notes[edit | edit source]

The uncovered set can be thought of as requiring its candidates to have a two-step beatpath to every candidate not in the uncovered set. The Smith set requires a one-step beatpath (i.e. of at most two candidates, a direct pairwise victory).

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, which further implies Smith and thus 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 adding ballots ranking W first.

The uncovered set implies Pareto, because Pareto implies that the Pareto-dominant candidate pairwise beats any candidates the Pareto-inferior candidate beats. This is because all voters rank the Pareto candidate equal to or better than the Pareto-inferior candidate. [10]

One way that has been suggested to find the uncovered set is:
This suggests the use of the outranking [pairwise comparison] matrix and its square to identify the uncovered set (Banks, 1985):

T = U + U2

where U [is] the tournament matrix. The alternatives represented by rows in T where all non-diagonal entries are non-zero form the uncovered set.[11]
(The square of a matrix can be found using matrix multiplication; here is a video explaining how to do so. The pairwise matrix and its squared matrix can be added together using matrix addition.)

References[edit | edit source]

  1. Munagala, Kamesh; Wang, Kangning (2019-05-04). "Improved Metric Distortion for Deterministic Social Choice Rules". arXiv.org. p. 5. doi:10.1145/3328526.3329550. Retrieved 2020-03-13.
  2. Endriss, U. "Handbook of Computational Social Choice" (PDF). The Reasoner. 2 (10): 57. ISSN 1757-0522. Retrieved 2020-03-13.
  3. https://www.jstor.org/stable/41105997?seq=1
  4. https://economics.stackexchange.com/a/27691
  5. Seising, R. (2009). Views on Fuzzy Sets and Systems from Different Perspectives: Philosophy and Logic, Criticisms and Applications. Studies in Fuzziness and Soft Computing. Springer Berlin Heidelberg. p. 350. ISBN 978-3-540-93802-6. Retrieved 2020-03-13.
  6. http://spia.uga.edu/faculty_pages/dougherk/svt_13_multi_dimensions2.pdf
  7. Woeginger, Gerhard J. (2003). "Banks winners in tournaments are difficult to recognize". Social Choice and Welfare. Springer. 20 (3): 523–528. ISSN 1432-217X. JSTOR 41106539. Retrieved 2022-04-10.
  8. Hudry, Olivier (2004). "A note on ?Banks winners in tournaments are difficult to recognize? by G. J. Woeginger". Social Choice and Welfare. Springer Science and Business Media LLC. 23 (1). doi:10.1007/s00355-003-0241-y. ISSN 0176-1714.
  9. Feld, Scott L.; Grofman, Bernard; Hartly, Richard; Kilgour, Marc; Miller, Nicholas (1987). "The uncovered set in spatial voting games" (PDF). Theory and Decision. Springer Science and Business Media LLC. 23 (2): 129–155. doi:10.1007/bf00126302. ISSN 0040-5833.
  10. "Alternate Definitions of the Uncovered Set and Their Implications".
  11. Kilgour, D (2010). Handbook of group decision and negotiation (PDF). Dordrecht New York: Springer. p. 176. ISBN 978-90-481-9097-3. OCLC 668097926.