Uncovered set: Difference between revisions

Line 1:

The '''uncovered set''' (sometimes referred to as the "'''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 that are involved in a circular tie somehow.

⚫

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

<math>\forall \,z</math>, <math>\exists \,y</math>, <math>x \ge y \ge z</math>.

== Definition ==

⚫

The Landau set is a nonempty subset of the [[Smith set]]. It was discovered by Nicholas Miller.

⚫

Usually, the uncovered set is defined only for situations without pairwise ties. When there are no pairwise ties, then the uncovered set is identical to the set called '''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''.}}

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

⚫

The Landau set is a nonempty subset of the [[Smith set]]. It was discovered by Nicholas Miller.

⚫

~~The '''uncovered set''' is defined for a set of [[preferential voting|rank-order]] preferences.~~ Usually, the uncovered set is defined only for situations without pairwise ties. When there are no pairwise ties, then the uncovered set is identical to the set called '''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''.}}

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 33:

Line 23:

==Formal definition==

⚫

A more formal mathematical definition: <blockquote>it 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

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.

<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 159:

Line 150: