Uncovered set: Difference between revisions
m
no edit summary
(Copied most of current w:Landau set article (this version: https://en.wikipedia.org/w/index.php?title=Landau_set&oldid=1020697182 ). I plan to incorporate the text a bit better later) |
mNo edit summary |
||
| (7 intermediate revisions by 3 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.
In [[voting system]]s, the '''Landau set''' (or '''uncovered set''', or '''[[Peter Fishburn|Fishburn]] set''') 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 ▼
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).
The Landau set is a nonempty subset of the [[Smith set]]. It was discovered by Nicholas Miller.▼
==
*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}}.▼
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 ''
# 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.
▲{{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''.}}
▲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]].
Line 25 ⟶ 23:
{{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:
Line 33:
==Formal definition==
▲
<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:
Line 140 ⟶ 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" />
=== 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 ===
Line 159 ⟶ 168:
==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 />
| |||