We note here several differences between the covering relation C and the majority preferencerelation P on which covering is based. First, like P, the covering relation C is a binary relation; but unlike P it is not "independent of irrelevant alternatives" (in both of the two senses of this term). Second, in a spatial context, P is a "local" matter (in a sense that can be precisely specified), while C for the most part constitutes "action at a distance."
 

1. Dependence of Covering on "Irrelevant Alternatives"

        Suppose we have a finite set of alternatives X and a complete majority preference relation P over the elements of X. Thus the voting situation is represented by the tournament (X,P), i.e., the complete asymmetric directed graph in which the vertices correspond to the elements of X, and there is a directed line from vertex x to vertex y if and only if x P y.

        Given any point x in a majority preference tournament (X,P), all remaining points are partitioned into two sets: the win set of x as W(x) = {y | y P x} and the dominion of x as D(x) = {z | x P z}. We say x C y ("x covers y") if and only if x P y and x P z for all z in D(y). This implies that W(x) subset W(y). If ~ x C y ("x does not cover y" or "y is uncovered by x"), i.e., if y P x or there is some z such that y P z P x, we write y UC(x). The uncovered set UC(X) is the set of all points not covered by any alternative, i.e., intersection UC(x), where the intersection is taken over all x X.

        Suppose we have a tournament in which x P y and also x C y. We can modify the tournament (X,P) in either of two ways that will have no impact on the relationship x P y but may change the relationship x C y.

        The first is to remove alternatives (not including x and y) from the agenda, i.e., remove vertices from the tournament, while the majority preference relation P (over the remaining alternatives) remains unchanged.

        Suppose we start with the tournament (X,P) in which x P y, and then several alternatives (not including x and y) are removed from the agenda, resulting in the tournament (X',P) where X' subset  X. Obviously, x P y as before. More generally, let W_X(x) be the win set of x in the more inclusive agenda X, and W_X' (x) be the win set of x in the less inclusive agenda X'. Then it follows that W_X' (x) = W_X (x) intersect X', i.e., the new win set is simply the old win set excluding whatever alternatives may have been removed from the agenda. Thus, even if we allow an agenda to expand or contract, there is little reason to subscript win sets with respect to the agenda. (The same consideration apply to D(x), of course.)

        However, the covering relation is not "independent of irrelevant alternatives" in this sense -- it is conditioned on the particular agenda. Thus, if we allow the agenda to vary, we must subscript accordingly -- that is, we need say x C_X y (not just x C y) and UC_X(x) (not just UC(x). But there are logical interconnection among covering relations when we allow the agenda to expand or contract.

 LEMMA 1.      If x and y both belong to X'  which is a subset of X, then

            (1a)  x C_X y implies x C_X' y (but not conversely);
            (1b)  y UC_X' (x) implies y UC_X(x) (but not conversely);
            (2a)  x C_X y implies ~ y C_X x; and
            (2b)  y UC_X' (x) implies x UC_X(y); and
            (3)   UC(X) intersect  X' is a subset of UC(X').

        In words, (1a) if x covers y in a more inclusive agenda, then x also covers y in any less inclusive agenda (preferences remaining constant), but the reverse is not true. Stating the matter the other way around (1b), if y is not covered by x in a less inclusive agenda, it cannot be covered in any more inclusive agenda (preferences remaining constant), but the reverse is not true. However (2a), if x covers y in a less inclusive agenda, then y cannot cover x in more less inclusive agenda (preferences remaining constant). Stating the matter the other way around (2b), if y is not covered by x in a less inclusive agenda, x cannot be covered by y in any more inclusive agenda (preferences remaining constant). All this implies that the uncovered set in the less inclusive agenda may include alternatives that are covered in the more inclusive agenda.

        With respect to (1a), x C_X y means that (x P y and) x P z for all z in D_X(x) so certainly x P z for all z in D_X(x) intersect X'. However, x C_X y means that (x P y and) x P z for all z in D_X(x) intersect X', but this does not preclude the possibility that there is some z in X (but z not in X') such that y P z P x, in which case x does not cover y in A. (1b) just restates (1a) in different notation. With respect to (2a and 2b), x C_X' y implies that x P y, so y cannot cover x in any agenda with the same preferences. Point (3) follows from (1) and (2).

        Lemma 1 specifies the dependence of the covering relation on "irrelevant alternatives" in the sense of whether such "irrelevant alternatives" are actually available ("on the agenda") or not. "Independence of Irrelevant Alternatives" in this sense has often been confused with the condition of "Independence of Irrelevant Alternatives" in Arrow's General Impossibility Theorem (indeed, the confusion goes back to Arrow's original discussion), which pertains to changes in preferences for "irrelevant alternatives," not their availability. The majority preference relation is "independent of irrelevant alternatives" in this sense as well, while the covering relation is once again "dependent on irrelevant alternatives" in this sense.

LEMMA 2.   If we have two tournaments (X,P) and (X,P') such that x P y and x P' y, x C y does not imply that x C' y; however, it does imply that ~ y C' x.

        Suppose we start with the tournament (X,P) in which x P y and also x C y, and then preferences with respect to some pairs of alternatives (not including the xy pair) are changed, resulting in the tournament (X,P'). Clearly we still have x P' y. But x C y in (X,P) does not assure us that x C' y in (X,P'), since we may have y P' z P' x in (X,P) for some z in X but either z P y or x P z in (X,P). However, since we still have x P' y, we are assured that ~ y C' x.
 

2. Spatial Properties of Majority Preference and Covering

        Suppose that the alternative set X is not finite but is the set of all points in a space of one or more dimensions. Suppose also that all individual have standard spatial preferences, i.e., single-peaked over all straight lines through the space. In this context it is known that the majority preference relation operates "locally," in the following precise sense (where N(x) is any neighborhood of point x, i.e. the set of points lying within any arbitrarily small distance from x):

LEMMA 3.   If W(x) , then the intersection of W(x) and N(x) is not empty . Moreover, if y in W(x), then z in W(x) for all z lying on the straight line between x and y.

        In words, if x is beaten any points, it is beaten by adjacent points. Moreover, if x is beaten by distant points, it is also beaten by all intermediate points. (This defines the "starlike" property of win sets.)

        However, except under two special circumstances, covering is "action at a distance" in the following sense (where x UP y means that x is unanimously preferred to y):

LEMMA 4.  If x C y, then y N(x) if and only if (1) x UP y or (2) x P y and the majority preference relation P is transitive.

        In words, point x covers a neighboring point y if and only if (1) x is unanimously preferred to y (so y must lie outside of the Pareto set PO(X)) or (2) x P y and the configuration of preferences is such that the majority preference relation P is transitive. In the latter event, x C y if (and, as always, only if) x P y, so covering inherits all the properties of P (including "local action"). Thus covering operates locally in the special case of a one-dimensional space, but in a space of two or more dimensions covering operates locally only if the Plott type of symmetry conditions are met. Moreover, satisfaction of the Plott condition is sufficient for transitive P and locally operating C in the event preferences are Euclidean (but not otherwise).

        To see this, consider a two-dimensional space, a distribution of ideal points, and an arbitrary point x. Recall that x C y implies that W(x) subset W(y).

        Consider Figure 1, in which x is centrally located relative to the ideal points (that do not meet the Plott symmetry condition). W(x) is the union of distinct segments (or "petals"), which (since x is "surrounded" by all limiting median lines) "sprout out" from x "in all directions" and each of which reflects the common preferences of a distinct minimal majority of individuals. (If such segments overlap, their intersection reflects the common preferences of a larger than minimal majority coalition.) If we displace x ever so slightly in any direction to some position x, we note that the petals of W(x) are likewise displaced so that parts of W(x) must intersect some parts of D(x) and vice versa. Thus neither x nor x can cover the other.

        Consider Figure 2, in which x is less centrally located but still in the Pareto set. In this case (because x lies "outside" of all limiting median lines), it is possible to draw a straight (in this case, horizontal) line through x such that W(x) lies entirely on one side of (in this case, below) this line. Even so, any slight displacement of x to position x must change the boundaries of the win set in such a way that some parts of W(x) intersect some parts of D(x) and vice versa, so neither point can cover the other.

        On the other hand, consider Figure 3, in which point x lies outside the Pareto set. If x is displaced downward so x lies in the "unanimity set" of x, all petals constituting W(x) shrink so that each is a subset of the corresponding petal in W(x). Thus W(x) W(x) and x covers x "locally."

        Likewise consider Figure 4, in which the Plott radial symmetry condition is met for a configuration of five ideal points. Voter 5's ideal point is the "total median," so majority preference is identical to voter 5's individual preference relation (all win sets are identical to 5's preference sets), so we get local covering throughout the space.

        Otherwise, the covering relation x C y can occur only if W(x) lies entirely within one segment or "petal" of W(y). But this can occur only if x is at some distance from (and more central than) y. See Figure 5, which accounts for Hartley and Kilgour's result that, in the three voter case, points within the Pareto set but in the vicinity of the more extreme ideal points are covered (by relatively central points).

        [Clearly this examination of Figures 1-5 provides only an illustration of Lemma 4, not a definitive proof. Moreover, the definition of covering given at the outset does not quite do in the spatial case, since we must allow for "tie sets" (in particular on the boundary of win sets). So there is clearly more work to do here.]