Uncovered set: Difference between revisions
Cleaned up definitions and added a formal definition section about the covering relation.
(Added essential set and references) |
(Cleaned up definitions and added a formal definition section about the covering relation.) |
||
Line 7:
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]].
Another definition is:<ref name="Endriss p. 57">{{cite journal | last=Endriss | first=U. | title=Handbook of Computational Social Choice | journal=The Reasoner | volume=2 | issue=10 | issn=1757-0522 | page=57 | url=http://www.cse.unsw.edu.au/~haziz/comsoc.pdf | access-date=2020-03-13}}</ref>
{{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.}}
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:
{{definition|In voting systems, the '''Landau set''' (or '''uncovered set''', or '''Fishburn set''') is the set of candidates ''x'' such that for every other candidate ''z'', there is some candidate ''y'' (possibly the same as ''x'' or ''z'') such that ''y'' is not preferred to ''x'' and ''z'' is not preferred to ''y''.}}
The uncovered set is a nonempty subset of the [[Smith set]]. The reason is that every candidate in the Smith set is preferred to every candidate not in the Smith set, therefore each candidate in the Smith set can be considered a candidate ''x'' and be their own candidate ''y''; since a candidate can't be preferred to themselves (''y'' is not preferred to ''x''), and since candidates in the Smith set being preferred to every candidate not in the Smith set implies that candidates not in the Smith set are not preferred to candidates in the Smith set (''z'' is not preferred to ''y''), the uncovered set must be a subset of the Smith set.
==Formal definition==
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:
{{definition|x covers y (x C y) if every candidate that beats x also beats y.}}
To be a proper covering relation, the relation should be transitive (if x covers y and y covers z, then x covers z) and antisymmetric (it's impossible to both cover x and be covered by x). This is true for the Fishburn definition when there are no pairwise ties, but it has to be generalized if it's to retain the properties in the presence of pairwise ties.
When there are pairwise ties, one may also refer to weak and strict covering relations. The former drops antisymmetry, and is analogous to x beating or tying y, while the latter retains antisymmetry and is analogous to x definitely beating y.<ref name="Miller" />
==Example==
| |||