Uncovered set: Difference between revisions

==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 ===

=== 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>