Uncovered set: Difference between revisions
Added essential set and references
(Separate out the subsets of the uncovered set from the Notes section, and add some references.) |
(Added essential set and references) |
||
Line 97:
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
=== 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" />
=== Schattschneider set ===
| |||