Uncovered set: Difference between revisions
m
no edit summary
Psephomancy (talk | contribs) (try definition template) |
mNo edit summary |
||
| (31 intermediate revisions by 5 users not shown) | |||
Line 1:
{{Wikipedia|Landau set}}
The '''minimal''' '''uncovered set''' (sometimes referred to as the "'''[[Lev Landau|Landau]] set'''" or "'''[[Peter Fishburn|Fishburn]] set'''") is defined for a set of [[preferential voting|rank-order]] preferences, and generalizes the Condorcet winner (making it a kind of "top cycle"). The set contains all candidates on the "Pareto frontier" for pairwise-victories.
A Landau candidate will beat every non-Landau candidate one-on-one, and cannot be replaced by a "strictly better" candidate. "Strictly better" means a candidate that would win every pairwise matchup won by the Landau candidate (and some additional matchups).
== Definition ==
We assume here that there are no pairwise-ties. Let some set be called the Fishburn set, and the candidates outside the set are called the '''Fishburn losers'''. A Fishburn loser is a candidate who is '''dominated''' or '''covered''' by some other candidate: the dominating candidate wins every pairwise matchup that the other candidate would win. The uncovered set is therefore equivalent to the set of '''Fishburn winners''':
{{definition|Select the candidate or candidates that are not Fishburn losers. A candidate ''loser'' is a Fishburn loser if there exists some other candidate ''cover'' satisfying:
# Every candidate that beats ''cover'' one-on-one also beats ''loser'' one-on-one, and
# At least one candidate beats ''loser'' one-on-one but does not beat ''cover'' one-on-one.
}}
The Fishburn winners are a kind of Pareto frontier for the set of candidates, where the frontier is measured by the pairwise-victories. It is impossible to gain some extra pairwise victories, but no pairwise losses, by switching from a candidate in the Landau set to a candidate outside the Landau set.
The Landau set is a nonempty subset of the [[Smith set]]. It was discovered by Nicholas Miller.
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).<ref name="Munagala Wang 2019">{{cite web | last=Munagala | first=Kamesh | last2=Wang | first2=Kangning | title=Improved Metric Distortion for Deterministic Social Choice Rules | website=arXiv.org | date=2019-05-04 | doi=10.1145/3328526.3329550 | url=https://arxiv.org/abs/1905.01401v1 | access-date=2020-03-13|page=5}}</ref> In this sense, it is related to the concept of a [[beatpath]].
Another definition is:<ref name="Endriss p. 57">{{cite journal | last=Endriss | first=U. | title=Handbook of Computational Social Choice | journal=The Reasoner | volume=2 | issue=10 | issn=1757-0522 | page=57 | url=http://www.cse.unsw.edu.au/~haziz/comsoc.pdf | access-date=2020-03-13}}</ref>
{{definition|An alternative a is said to cover alternative b whenever every alternative dominated by b is also dominated by a.}}
Yet another definition:<ref name="Laffond Laslier 1991 pp. 365–369">{{cite journal | last=Laffond | first=Gilbert | last2=Laslier | first2=Jean-François | title=Slaters's winners of a tournament may not be in the Banks set | journal=Social Choice and Welfare | publisher=Springer | volume=8 | issue=4 | year=1991 | issn=01761714 | jstor=41105997 | pages=365–369 | url=http://www.jstor.org/stable/41105997 | access-date=2022-09-11}}</ref> {{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.}}
{{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''.}}
When there are pairwise ties, many generalizations are possible, all of which are equivalent when there are no pairwise ties.<ref name="Miller">{{cite web | last=Miller | first=Nicholas M. |title=Alternate definitions of the covering relation: an extended tour |url=https://userpages.umbc.edu/~nmiller/RESEARCH/COVERING.REV3.pdf}}</ref> One generalization by Fishburn is:
{{definition|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.
==Formal definition==
A more formal mathematical definition: <blockquote>it is the set of candidates <math>x</math> such that for every other candidate <math>z</math>, there is some candidate <math>y</math> (possibly the same as <math>x</math> or <math>z</math>) such that <math>y</math> is not preferred to <math>x</math> and <math>z</math> is not preferred to <math>y</math>. In notation, <math>x</math> is in the Landau set if
<math>\forall \,z</math>, <math>\exists \,y</math>, <math>x \ge y \ge z</math>.</blockquote>The uncovered set is based on the ''covering relation'', which is a notion of a candidate being at least as good as another candidate (e.g. by beating everybody the other candidate beats, or by being beaten by nobody who beats the other candidate). The uncovered set is then defined as the set of candidates who are not covered by anyone else.
For the Fishburn winner definition of the uncovered set, the covering relation is:
{{definition|x covers y (x C y) if every candidate that beats x also beats y.}}
To be a proper covering relation, the relation should be transitive (if x covers y and y covers z, then x covers z) and antisymmetric (it's impossible to both cover x and be covered by x). This is true for the Fishburn definition when there are no pairwise ties, but it has to be generalized if it's to retain the properties in the presence of pairwise ties.
When there are pairwise ties, one may also refer to weak and strict covering relations. The former drops antisymmetry, and is analogous to x beating or tying y, while the latter retains antisymmetry and is analogous to x definitely beating y.<ref name="Miller" />
==Example==
Suppose the following pairwise preferences exist between four candidates (v, x, y, z) (table organized by [[Copeland]] ranking):
{| class="wikitable"
|+
!
!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. <ref>https://economics.stackexchange.com/a/27691</ref> (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:
{| class="wikitable"
! colspan="5" |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
|'''<big><u>3</u></big>'''
|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==
The Banks set, [[Copeland]] set, Dutta set, and Schattschneider set are all subsets of the uncovered set.<ref name="Seising 2009 p.">{{cite book | last=Seising | first=R. | title=Views on Fuzzy Sets and Systems from Different Perspectives: Philosophy and Logic, Criticisms and Applications | publisher=Springer Berlin Heidelberg | series=Studies in Fuzziness and Soft Computing | year=2009 | isbn=978-3-540-93802-6 | url=https://books.google.com/books?id=yCBqCQAAQBAJ | access-date=2020-03-13 | page=350}}</ref>
=== Banks set ===
The '''Banks set''' is the set of winners resulting from strategic voting in a successive elimination procedure<ref>http://spia.uga.edu/faculty_pages/dougherk/svt_13_multi_dimensions2.pdf</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).
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,<ref name="Woeginger 2003 pp. 523–528">{{cite journal | last=Woeginger | first=Gerhard J. | title=Banks winners in tournaments are difficult to recognize | journal=Social Choice and Welfare | publisher=Springer | volume=20 | issue=3 | year=2003 | issn=1432217X | jstor=41106539 | pages=523–528 | url=http://www.jstor.org/stable/41106539 | access-date=2022-04-10}}</ref> 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.<ref name="Hudry 2004 p. ">{{cite journal | last=Hudry | first=Olivier | title=A note on 'Banks winners in tournaments are difficult to recognize' by G. J. Woeginger | journal=Social Choice and Welfare | publisher=Springer Science and Business Media LLC | volume=23 | issue=1 | year=2004 | issn=0176-1714 | doi=10.1007/s00355-003-0241-y | page=}}</ref>
=== Dutta set ===
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. The Dutta set can be calculated in polynomial time.<ref name="Brandt Fischer 2008">{{cite journal | last=Brandt | first=Felix | last2=Fischer | first2=Felix | title=Computing the minimal covering set | journal=Mathematical Social Sciences | publisher=Elsevier BV | volume=56 | issue=2 | year=2008 | issn=0165-4896 | doi=10.1016/j.mathsocsci.2008.04.001 | pages=254–268|url=https://pub.dss.in.tum.de/brandt-research/covering.pdf}}</ref>
=== Essential set ===
In a game where two players choose candidates and then the player who chose the candidate who beats the other candidate pairwise wins, there's a randomized strategy (a [[Nash equilibrium]]) where no other strategy can be used against it to consistently win at this game. The '''essential set''', a subset of the Dutta set, is the set of all candidates who are chosen some of the time when using a Nash equilibrium strategy.<ref name="Brandt Fischer 2008" />
=== Minimal extending set ===
{{Expand section|date=April 2024}}
The minimal extending set is a subset of the Banks set. It's relevant to strategic voting: narrowing the set of winners to this set when there is no Condorcet winner has not been shown to introduce an incentive to strategically create a cycle when a sincere [[Condorcet winner]] exists.<ref name="Botan Endriss 2021 pp. 5202–5210">{{cite journal | last=Botan | first=Sirin | last2=Endriss | first2=Ulle | title=Preserving Condorcet Winners under Strategic Manipulation | journal=Proceedings of the AAAI Conference on Artificial Intelligence | publisher=Association for the Advancement of Artificial Intelligence (AAAI) | volume=35 | issue=6 | date=2021-05-18 | issn=2374-3468 | doi=10.1609/aaai.v35i6.16657 | pages=5202–5210}}</ref>
A method electing from this set must fail [[monotonicity]].<ref name="Brandt Harrenstein Seedig 2017 pp. 55–63">{{cite journal | last=Brandt | first=Felix | last2=Harrenstein | first2=Paul | last3=Seedig | first3=Hans Georg | title=Minimal extending sets in tournaments | journal=Mathematical Social Sciences | publisher=Elsevier BV | volume=87 | year=2017 | issn=0165-4896 | doi=10.1016/j.mathsocsci.2016.12.007 | pages=55–63}}</ref> However, the proof is nonconstructive and no concrete nonmonotonicity examples have been found so far.
=== Schattschneider set ===
The '''Schattschneider set''' is based on spatial voting games, and is a subset of the Banks set.<ref name="Feld Grofman Hartly Kilgour 1987 pp. 129–155">{{cite journal | last=Feld | first=Scott L. | last2=Grofman | first2=Bernard | last3=Hartly | first3=Richard | last4=Kilgour | first4=Marc | last5=Miller | first5=Nicholas | title=The uncovered set in spatial voting games | journal=Theory and Decision | publisher=Springer Science and Business Media LLC | volume=23 | issue=2 | year=1987 | issn=0040-5833 | doi=10.1007/bf00126302 | pages=129–155|url=https://userpages.umbc.edu/~nmiller/RESEARCH/T&D.87.pdf}}</ref> It is rarely referenced.
==Notes==
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 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 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. <ref>{{Cite web|url=https://www.researchgate.net/publication/225729286_Alternate_Definitions_of_the_Uncovered_Set_and_Their_Implications|title=Alternate Definitions of the Uncovered Set and Their Implications|last=|first=|date=|website=|url-status=live|archive-url=|archive-date=|access-date=}}</ref>
One way that has been suggested to find the uncovered set is:<blockquote>This suggests the use of the outranking [pairwise comparison] matrix and its square to identify the uncovered set (Banks, 1985):
T = U + U<sup>2</sup>
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.<ref name="Kilgour 2010 p. ">{{cite book | last=Kilgour | first=D | title=Handbook of group decision and negotiation | publisher=Springer | publication-place=Dordrecht New York | year=2010 | isbn=978-90-481-9097-3 | oclc=668097926 | page=176 |url=https://core.ac.uk/download/pdf/11047227.pdf}}</ref></blockquote>(The square of a matrix can be found using matrix multiplication; here is a [https://www.youtube.com/watch?v=3c2rzaO1h28 video] explaining how to do so. The pairwise matrix and its squared matrix can be added together using [https://www.purplemath.com/modules/mtrxadd.htm matrix addition].)
==References==
*Nicholas R. Miller, "Graph-theoretical approaches to the theory of voting", ''American Journal of Political Science'', Vol. 21 (1977), pp. 769–803. {{doi|10.2307/2110736}}. {{JSTOR|2110736}}.
*Nicholas R. Miller, "A new solution set for tournaments and majority voting: further graph-theoretic approaches to majority voting", ''American Journal of Political Science'', Vol. 24 (1980), pp. 68–96. {{doi|10.2307/2110925}}. {{JSTOR|2110925}}.
*Norman J. Schofield, "Social Choice and Democracy", Springer-Verlag: Berlin, 1985.
*Philip D. Straffin, "Spatial models of power and voting outcomes", in ''Applications of Combinatorics and Graph Theory to the Biological and Social Sciences'', Springer: New York-Berlin, 1989, pp. 315–335.
*Elizabeth Maggie Penn, "[https://web.archive.org/web/20060913022520/http://www.people.fas.harvard.edu/~epenn/covering.pdf Alternate definitions of the uncovered set and their implications]", 2004.
*Nicholas R. Miller, "In search of the uncovered set", ''Political Analysis'', '''15''':1 (2007), pp. 21–45. {{doi|10.1093/pan/mpl007}}. {{JSTOR|25791876}}.
*William T. Bianco, Ivan Jeliazkov, and Itai Sened, "[https://web.archive.org/web/20181220033859/https://pdfs.semanticscholar.org/b15e/72fc147a0421f710b349bf346deeb30aef8b.pdf The uncovered set and the limits of legislative action]", ''Political Analysis'', Vol. 12, No. 3 (2004), pp. 256–276. {{doi|10.1093/pan/mph018}}. {{JSTOR|25791775}}.
=== Footnotes ===
<references />
[[Category:Voting theory]]
[[Category:Condorcet-related sets]]
| |||