Uncovered set: Difference between revisions
More intuitive definition
(Linking to Lev Landau for alliterative linking.) |
(More intuitive definition) |
||
Line 1:
{{Wikipedia|Landau set}}
The '''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. An informal definition: the Condorcet winner, or a set of candidates
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 ''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''.}}▼
{{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:
1. Every candidate that beats ''cover'' one-on-one also beats ''loser'' one-on-one, and
2. 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.
Line 15 ⟶ 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:
| |||