Uncovered set: Difference between revisions
Content added Content deleted
No edit summary |
(Added minimal extending set stub) |
||
| Line 141: | Line 141: | ||
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" /> |
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 instances have of the minimal extending set being non-monotone yet been found. |
|||
=== Schattschneider set === |
=== Schattschneider set === |
||