Geometry of Voting (based on paper by N. Miller, et. al.)

Majority Rule

Given voter preferences, a majority preference relation is generated between every pair of points. x beats y if more than half of all voters prefer x to y (rather than more than half of all voters who are not indifferent between x and y), y beats x if the reverse, and x and y tie otherwise.

Win Set

The set of points that beat x is the win set of x, designated W(x). A point that cannot be beaten under majority rule, i.e., a point x such that W(x) is empty, is variously called a "majority rule equilibrium," a "Condorcet winner," or a majority rule "core." Here we call it simply an unbeaten point.

Assumptions

1. All voters have "Euclidean" (or "Downsian," or "Type I") preferences: individual preference is based on simple Euclidean distance, i.e., each voter has an ideal point (point of highest preference) in the space and, in comparing any two points in the space, prefers the point closer to his ideal to the point more distant from his ideal and is indifferent between them if they are equidistant from his ideal

2. In two dimensions, the locus of points equidistant from a fixed point is a circle, a voter's preferences relative to an arbitrary point x in a two-dimensional space can be represented by a circle (called an indifference curve) centered on the voter's ideal point and passing through x; every point inside the circle is closer to the voter's ideal point than x is, so the voter prefers any such point to x.

3. The number of voters n is odd

4. Any line L through a two-dimensional alternative space partitions the ideal points into three sets: those that lie on one side of L, those that lie on the other side of L, and those that lie on L.

Lemma 1 below indicates the import of Assumption 3. It should be noted that two points might tie even if n is odd, because an odd number of voters may be indifferent between them.

Median Line

A median line partitions the ideal points so that no more than half of them lie on either side of the line.

Figure - Median Line

LEMMA 0

If the number of ideal points n is odd:

1) any median line M must pass through at least one point

2) no two median lines M and M' can be parallel

Proof:

1) Otherwise there would be at least (n+1)/2 points on one or other side of M

2) There must be at least (n+1)/2 points on and to either side of median line M and thus at least the same number strictly to one side of any other median line M' parallel to M.

Figure – Lemma 0

Limiting Median Lines

Usually, an ideal point has a infinite number of median lines passing through it, and (with n odd) most median lines pass through just one point each. For some purposes, we need be concerned only with a finite subset of median lines that may be called limiting median lines, each of which passes through (at least) two ideal points.

Figure - Limiting Median Lines

LEMMA 1

Given any line L, there is some median line perpendicular to L. If n is odd, there exactly one median line perpendicular to L.

Proof:

Erect a line perpendicular to L. Now shift this perpendicular line to the left or right until it is a median line. With n odd, only one line will do (because we cannot have parallel median lines). It will pass through one and, almost always, only one point.

Figure – Lemma 1

LEMMA 2

Given any two points x and y, if the median line M perpendicular to the line through x and y is closer to x than to y, then x beats y, and if M is closer to y, then y beats x. And x ties y only if M is equidistant from x and y.

Proof:

Given Euclidean preferences, every voter prefers x to y or y to x according to which is closer to his ideal point. The division of preferences between x and y is determined by the perpendicular bisector of the line segment from x to y -- that is, all ideal points on the x side of the bisector are closer to x than y, all ideal points on the y side are closer to y than x, and all ideal points on the bisector are equidistant from x and y. If the median line perpendicular to the line through x and y is on the x side of the perpendicular bisector, it follows that more than half the ideal points are on the x side of the bisector, so x beats y. Conversely, if the median line is on the y side, y beats x. If, fortuitously, the perpendicular bisector is also the median line perpendicular to the line through x and y, x ties y, unless, even more fortuitously, two (or a larger even number of) ideal points lie on the median line (in which event x beats y or y beats x depending on how the remaining odd number of ideal points are distributed on either side of the median bisector)

Note: Given majority rule in the absolute sense, x and y tie in any event. This indicates how absolute majority rule leads to slightly cleaner results.

Figure – Lemma 2

Reflection Line

Consider any point x in the space and any line L. Drop a perpendicular line of length d from x to L, intersecting L at the point x' (which is called the projection of x on L); if L happens to pass through x, then x'=x. Now project the line segment from x to x' an equal distance d beyond L to the point x* that we call the reflection of x through L (x is also the reflection of x* through L); if L happens to pass through x, then x*=x. Call the line segment from x to x* the reflection line

of x (or x*) through L.

Figure - Reflection Line

LEMMA 3

Let y be any point other than x and x* on the reflection line of x through any median line M. Then y beats x.

Proof.

The median line M is the perpendicular bisector of the reflection line of x through m. Point y lies somewhere strictly between x and x*. Thus the perpendicular bisector of the line segment from x to y lies on the x side of M. By Lemma 2, y beats x.

Figure - Lemma 3

THEOREM 1

For any line L through x:

1) if x is beaten by any point y on L, it is beaten by every point on L between x and y

2) if x is beaten by points on L on one side of x, x is not beaten by any points on L on the other side of x

3) x is tied by at most one point on L and only if it is beaten by points on L on the same side of x.

Proof.

By Lemma 3, x is beaten by all points on a line L through x that lie between x and its reflection x* through the median line perpendicular L. By Lemma 2, x is beaten only by these points on L. Points (1) and (2) then follow immediately. And by Lemma 2, on any line L through x, x may be tied only by its reflection through the median line perpendicular to L. Thus, if no point on L on one side of x beats x (i.e., if the perpendicular median line does not intersect L on that side of

x), no such point ties x either. This establishes (3).

Figure – Theorem 1 (parts 1 and 2)

Note: (1) implies that if x is beaten by any point, it is beaten by some neighboring point. Note also that the converse of (2) does not hold; if and only if the median line perpendicular to L passes through x, no points on L (on either side of x) beat x. Finally note that by (3), we can use interchangeably the phrases "x is unbeaten" and "x beats every point," when referring to points on a line L to one side of x.

Starlike Set

A set W(x) is starlike about x if and only if W(x) includes all points lying on any straight line between x and any point in W(x).

Polarized Set

A set W(x) is polarized about x if and only if, when points on a line through x on one side of x belong to W(x), no points on the line on the other side of x belong to W(x).

Thin Set

A set X is thin if it has no interior, i.e., if any neighborhood of any point in X includes points not in X. (In a two-dimensional space, any line is a thin set.)

THEOREM 1'

For any point x:

1) W(x) is starlike about x;

2) W(x) is polarized about x; and

3) the set of points that tie x is thin

Proof.

See proof for Theorem 1.

Note: W(x) is an "open set" -- that is, a set that does not include its boundary. The boundary of W(x) is formed by the tie set of x. The "closure" of W(x) is the set of points that beat or tie x, i.e., the union of W(x) with its boundary.

THEOREM 2

A point x is unbeaten if and only if every median line passes through x.

Proof.

Sufficiency follows from Lemma 2. If every median line passes through x, then for any y distinct from x, the median line perpendicular to the line through x and y is closer to x than to y (for indeed it passes through x), so x beats y. Necessity follows from Lemma 3. If x lies off any median line M, it has a reflection line of positive length through M, and any point on this reflection line between x and x* beats x.

Figure – Theorem 2

COROLLARY 2.1.

There is at most one unbeaten point.

Proof.

Every median line can pass through at most one point (the intersection of any two lines is unique).

COROLLARY 2.2.

If point x is unbeaten, every line through x is a median line.

Proof.

Consider any line L through x and the line L' through x and perpendicular to L. By Lemma 1, there is (for n odd) a unique median line M perpendicular to L'. Since every median line passes through x, it must be that M = L, so L is a median line.

COROLLARY 2.3.

If point x is unbeaten, x is an ideal point.

Proof.

Since every line through x is a median line, there are an infinite number of median lines through x. But there are only a finite number of ideal points, so only a finite number of median lines through x can pass through ideal points other than x. Since (with n odd) every median line must pass through some ideal point, it must be that x is an ideal point.

COROLLARY 2.4.

If point x is unbeaten, x is the unique median of all ideal points that lie on each line through x.

Proof.

Let k (where 1≤ k ≤ n) be the number of ideal points on line L through x. (Usually, of course, k = 1, and almost always k ≤ 3.) We consider two cases: (1) k is odd and (2) k is even. We show that no more than (k-1)/2 (if k is odd) or k/2 - 1 (if k is even) ideal points can lie on L on either side of x. (If k were even and exactly k/2 points lay on the same side of x, x would be a median point but not the unique median.)

(1) The number of ideal points not on L is n - k; since n is odd and k is odd, n - k is even. The number of ideal points that lie on the side of L that has the most ideal points is at least (n-k)/2; let W1 be this set of at least (n-k)/2 points, and let W2 be the set of no more than (n-k)/2 ideal points on the other side of L. Suppose, contrary to Corollary 2.4, that at least (k+1)/2 ideal points lie on L on the same side of x. We now rotate L infinitesimally about x to generate a new line L' through x. The rotation can be so slight that the division of the n - k ideal points into two sets W1 and W2 on either side of L remains unchanged visa vis L'. But even the slightest rotation means that none of the k - 1 ideal points on L, other than x, lies on L'. We rotate in the direction so that the (k+l)/2 or more ideal points on L on the same side of x are placed on the same side of L' as the set W1. Thus there are at least [(n-k)/2] + [(k+1)/2] = (n+1)/2 ideal points on the same side of L'. But this is impossible, since L' passes through x and is therefore a median line. Thus no more than (k-1)/2 ideal points can lie to one side of x on any line L through x, and x must be the unique median ideal point on L.

(2) The number of ideal points not on L is n - k; since n is odd and k is even, n - k is odd. The number of ideal points that lie on the side of L that has the most ideal points is at least (n-k+1)/2. Again let W1 designate this set of at least (n -k+1)/2 points and W2 the remaining set of no more than (n-k-1)/2 points. Suppose, contrary to Corollary 2.4, that at least k/2 ideal points lie on L on the same side of x. As before, we rotate L infinitesimally about x to generate a new line L' through x. And we rotate in the direction so that the at least k/2 ideal points on L on one side of x are placed with the set W1. Thus there are at least [(n-k+1)/2] + k)/2 =(n+1)/2 ideal points on the same side of L', which again leads to a contradiction. Thus no more than k/2 - 1 ideal point can lie to one side of x on any line L through x, and x must be the unique median ideal point on L.

Pairwise Symmetry Condition

Thus, if the condition specified in Theorem 2 is to hold, and if all voter preferences are diverse -- in particular if the unbeaten point is the ideal point of only one voter, there must be one ideal point x_i such that all remaining ideal points can be paired off in such a way that the two points in each pair lie on a straight line with, and on opposite sides of, x_i. (Two or more such pairs may lie on the same straight line.)

Figure – Pairwise Symmetry Condition

If the group size is even or two or more ideal points coincide, it is possible to have an unbeaten point without the Pairwise symmetry condition. The figure below illustrates this for a group of size 5. In this case the points x₄ and x₅ are unbeaten.

Figure – An Unbeaten Point with Non-Diverse Preferences

THEOREM 3.

Given an unbeaten point c, if point y is further from c than point x is, x beats y.

Proof.

Since there is an unbeaten point c, from Theorem 2 every median line passes through c. Consider any point x at a distance d from c and any line L through x, as shown in Figure – Theorem 3. M is the median line perpendicular to L. By Lemma 3, x is beaten by every point on L between x and its reflection x* through M and, by Lemma 2, x is beaten only by these points (and possibly by x* itself) on L. Since M is the perpendicular bisector of the reflection line, x and x* are equidistant from all points on M, including c. Thus the distance from x* to c is d, and the distance from c to any point on L between x and x* is less than d (as is shown clearly in Figure – Theorem 3 by drawing in part of the circle with center c and radius d). So, in any event, x is beaten by every point on L that is closer to c than x is (and beats every point on L that is further from c than x is). Restating these conclusions for all lines through x gives the theorem.

Figure – Theorem 3

Ray From A Point

We can derive a simple formula for the distance from x to the boundary of its win set in any direction, i.e., from x to x* on any line through x. A ray from a point x is a half line beginning at x and pointing outward from x in any direction. We may specify a ray from point x in terms of the angle between the given ray and the ray from x through c. (See Figure – Ray From a Point; in fact there are two rays for each: the one drawn in the figure and the one in the mirror image of the figure below the line through c and x) Note that x, c, and the projection c' of c on L form the vertices of a right triangle. Recall that the cosine of an angle in a right triangle is the ratio of the length of the adjacent side to the length of the hypotenuse. Thus if p is the distance from x to c', cos = p/d , so p = d cos , and the distance from x to x* (i.e., the distance from x along the ray specified by to the boundary of its win set ) is 2p = 2dcos . The locus of points at a distance 2dcos from x is the circle centered on c and passing through x.

Figure – Ray From a Point

Yolk

The region bounded by the circle of minimum radius that intersects every median line.

Yolk Estimation Heuristic

A circle that intersects every limiting median line necessarily intersects every other median line as well, as non-limiting median lines through any point x lie between pairs of limiting median lines through x. McKelvey (1986) provides a linear programming method for computing the exact location and size of the yolk, i.e., its center c and radius r; but the location and size of the yolk can be determined with fair accuracy on the basis of visual inspection once limiting median lines are drawn in.

Figure – Yolk Estimation Heuristic

LEMMA 4

In the absence of an unbeaten point, at least three median lines are tangent to the yolk.

Proof.

It is a basic result of geometry that a circle can be inscribed within any triangle, so that each of the three sides of the triangle is tangent to the circle. Any three limiting lines (that do not intersect at a common point) enclose a triangle, and the circle inscribed within this triangle is clearly the smallest circle intersecting all three median lines. Consider a fourth limiting median line. If it does not intersect the circle, the additional median line together with two of the original three form a triangle whose inscribed circle intersects all four median lines, and which is the smallest circle to do so. So in any event, the smallest circle intersecting all four median lines is tangent to at least three of them. And so forth until we have considered every limiting median line (which are finite in number). As previously noted, this circle must intersect all non-limiting median lines as well.

LEMMA 5

In the absence of an unbeaten point, for any point x, there is some median line M such that x and the center of the yolk c lie on the same side of M.

Proof.

Figure – Lemma 5 shows the yolk with center c and the three median lines known to be tangent to the yolk. Regardless how these median lines are drawn, they partition the space into three subsets labeled A, B, and C. (For precision, we should specify that B includes the lines themselves.) Consider positioning the point x in each of these regions and observe that for each such placement both x and c are on the same side of at least one median line. Indeed when x is in A, x and c are on the same side for all three median lines; when x is in B, x and c are on the same side of two median lines; when x is in C, x and c are on the same side of exactly one of the three median lines.

Figure – Lemma 5

THEOREM 4

In the absence of an unbeaten point, for any point x there is some other point y that both beats x and is further from the center of the yolk than x is.

Proof.

Lemma 5 which tells us that, for any point x, there is some line L passing through x such that the median line M perpendicular to L lies beyond the center of the yolk, as shown in Figure – Theorem 4, where e is the perpendicular distance from c to M. As we saw in connection with Theorem 3 (and Figure - Theorem 3), if x could not be beaten by points more distant than x is from the center of the yolk, the point on L most distant from x that could beat x would be x", the reflection of x through the line passing through c and perpendicular to L (at a distance of 2dcos from x). But in fact x is beaten by every point on L up to (and possibly including) x*, the reflection of x through the median line perpendicular to L (at a distance of 2dcos + 2e from x). Thus x*, further from c than x is, demarcates the boundary of W(x) along L.

Reversing the roles of the two points, it follows also that for any point x there is some other point z that x beats and that is closer to the center of the yolk than x is.

Thus, in the absence of an unbeaten point, the win set W(x) of a point x is never contained in the circle centered on the center of the yolk and passing through x (as is always the case given an unbeaten point). W(x) always extends beyond this circle in some places (and falls short of it in other places).

Figure – Theorem 4

Note: This result drives McKelvey's (1976) "global cycling" theorem. By repeated application we can construct a majority preference trajectory of this form: x is beaten by y, y is beaten by z, z is beaten by v, and so forth, such that each new point in the trajectory is further from the center of the yolk than the preceding point. It this way, the trajectory can move outward from the center of the yolk without limit. We will prove as a corollary to a subsequent theorem the converse (on its face very plausible), namely, that if the trajectory moves far enough outward, it can always move back in to x to complete the cycle.

Domination

Given an arbitrary point x at a distance d from the center of the yolk c, demarcate W(x) by examining every line L through x and determining where the median line M perpendicular to L intersects L.

If the only information concerning the configuration of ideal points is the size and location of the yolk (i.e., that information conveyed by the parameters c and r), the exact location of the median line M perpendicular to L is unknown. It must lie between the two tangent lines T1 and T2 perpendicular to L and tangent to opposite sides of the yolk, for by definition every median line passes through the yolk.

Figure – Median Line Perpendicular to L Bounded by T₁ and T₂

If T1 and T2 both intersect L on the same side of x (which can be true only if x lies outside of the yolk), see Figure – Domination: Case A, M must lie on that side of x, so (regardless of the particular configuration of ideal points) points on L on that side of x must beat x. And by the polarity property of win sets (Theorem 1'), x cannot be beaten by any points on L on the other side of x.

Figure – Dominating Ray

If T1 and T2 intersect L on opposite sides of x (which must be true if x lies inside the yolk), see Figure – Contingent Ray, we cannot say on which side of x M lies, but (unless it happens that M passes through x, in which event no point on L beats x) x is beaten by points on L on one or other side of x (depending on the particular configuration of ideal points), but in any case (by polarity) not both sides.

Figure – Contingent Ray

Thus, given the parameters c (the center of the yolk), r (the radius of the yolk), and d (the distance from c to x), we can partition all lines through x into two classes, according to whether the T1 and T2 intersect the line on the same side of x or not.

In turn, we can partition all rays from x into three classes:

1) dominating rays, which must intersect W(x) regardless of the particular configuration of ideal points, because both T1 and T2 strictly intersect each such ray;

2) dominated rays, which cannot intersect W(x) regardless of the particular configuration of ideal points, because neither T1 nor T2 strictly intersect each such ray;

3) contingent rays, which may or may not intersect W(x) depending on the particular configuration of ideal points, because either T1 or T2, but not both, strictly intersects each such ray.

A ray is undominated if it is either dominating or contingent.

In the event that a ray is dominating, then by convention T2 lies closer to x than T1 and, in the event that a ray is contingent, the ray intersects T1 but not T2.

Two rays are opposites if they lie on the same line pointing in opposite directions. Then, from the polarity property, if a ray from x is dominating, its opposite is dominated, and vice versa; and if a ray is contingent, so is its opposite. Thus the sets of dominating and dominated rays constitute the two napes of a cone with vertex at x and centered on the line through c and x. These sets constitute the dominating cone and the dominated cone, respectively, with respect to x; the dominating cone faces toward the yolk and the dominated cone faces away from the yolk. The set of contingent rays is the complement of these cones; we may call it the chaotic region.

The next question is how to specify which rays are of which type and thus to specify exactly where these regions about x lie. (We have already observed that, if point x is inside the yolk, all rays from x are contingent; thus the chaotic region with respect to such a point fills the entire space.) As before we specify rays from x in terms of the angle between the ray in question and the ray from x through the center of the yolk. The following theorem provides the desire classification of ray types.

THEOREM 5

For any point x at a distance of d from the center of the yolk c, and for any ray from x specified by :

(1) if l cos > r/d, the ray is dominating;

(2) if r/d < 1 (i.e., if x is outside the yolk) and -r/d cos -1 , the ray is dominated; and

(3) if r/d cos > -r/d or if r/d 1 (i.e., if x is in the yolk), the ray is contingent.

Proof.

Compute the critical angles θ* and θ** that separate dominating from contingent rays and contingent from dominated rays, respectively, as shown in Figure – Theorem 5a. Each angle is a function of r, the radius of the yolk, and d, the distance from x to c.

Figure – Theorem 5a

Angle θ* defines the ray such that T2 passes through x, see Figure-Theorem 5b.

Figure – Theorem 5b

Angle θ** defines the ray such that T1 passes through x, and is simply 180 – θ, see Figure – Theorem 5c.

Figure – Theorem 5c

Thus cos θ* = r/d and cos θ** = -r/d.

(Recall that cos θ decreases as θ increases, in particular, cos 0 = l, cos 90 = 0, and cos 180 = -1.)

Given these relationships, we can readily see what happens to the three regions of the space about x as the ratio r/d changes.

As x moves further from the yolk (as d increases), or the radius of the yolk shrinks (as r decreases), so that the ratio r/d decreases and approaches zero, the critical angles θ and θ’ approach 90 (from below and above, respectively). Thus the dominating and dominated cones widen and the chaotic region contracts. Therefore, as distance from the yolk increases or the size of the yolk decreases, majority rule becomes more orderly -- in that a given point is beaten by a larger and larger fraction (approaching 100%) of nearby points in the direction of the yolk and by a smaller and smaller fraction (approaching 0%) of points in the direction away from the yolk. (As we have seen from Theorem 3, majority rule becomes perfectly orderly in this sense when the radius of the yolk shrinks to zero.)

As x moves closer to yolk (as d decreases), or the yolk expands (as r increases), so that the ratio r/d increases and approaches one, the critical angles θ* and θ** approach 0 and 180, respectively, so the dominating and dominated cones narrow and the chaotic region expands. Therefore, as distance from the yolk decreases or as the size of the yolk increases, majority rule becomes more chaotic -- in that a given point is beaten by a smaller and smaller fraction (approaching 50%) of nearby points in the direction of the yolk and by a larger and larger fraction (approaching 50%) of points in the direction away from the yolk.

As we have already seen, if x is within the yolk, all rays from x are contingent and, in this sense, majority rule within the yolk is totally chaotic -- a point within the yolk may be beaten by nearby points "on all sides."

Next, we should bear in mind that, while x beats every point on a dominated ray, x certainly is not beaten by every point on a dominating ray but only by "nearby" points. Put otherwise, while W(x) includes no points in the dominated cone, W(x) includes only all "nearby" points the dominating cone and some "nearby" points the chaotic region. The question naturally arises of how "nearby" these points must be. The answer to this question follows directly from previous considerations.

THEOREM 6

For any point x at a distance of d from the center of the yolk c, and for any ray from x specified by:

(1) x is beaten by all points on a dominating ray up to a distance of 2dcos - 2r from x; and

(2) x beats all points on an undominated ray beyond a distance of 2dcos + 2r from x.

Proof.

Consider any dominating ray from x, e.g., see Figure –Theorem 6a. By definition both T1 and T2 strictly intersect the ray. The median line perpendicular to the ray cannot be closer to x than T2. Thus all points on the ray between x and its reflection through T2, x*, must beat x. The distance from x to c' (the projection of c onto the ray) is, as we saw earlier, d cosq. The projection x' of x onto T2 is closer to x by the distance r, so the distance from x to x' is d cosq - r. The distance from x to its reflection x* through T2 is just twice this, i.e., 2(d cosq - r). (Notice that this expression is positive just so long as the ray is dominating, i.e., cosq > r/d.) Thus x must be beaten by all points on a dominating ray up to a distance of 2dcosq - 2r from x.

Figure – Theorem 6a

Now consider any undominated ray from x, e.g., see Figure – Theorem 6b. (Figure – Theorem 6b shows the contingent case; the other possibility is a dominating ray, already shown in Figure –Theorem 6a.) By definition, T1 strictly intersects the ray. The median line perpendicular to the ray cannot be further from x than T1. Thus x must beat all points on the ray beyond x and its reflection through T1. Calculating in the same manner as above, the distance from x to its reflection x* through T1 is 2(d cosq + r). (Notice that this expression is positive just so long as the ray is undominated, i.e., cosq > -r/d.) Thus x must beat points on an undominated ray beyond a distance of 2d cosq + 2r from x.

.

Figure – Theorem 6b

This is, in effect, the theorem due to Ferejohn, McKelvey, and Packel (1984). They state it in the following manner. Recall that the locus of points at a distance of 2d cosq from x is the circle centered on c and passing through x. From the analysis above, inner and outer bounds on W(x) are given by the locus of points at a distance of 2d cosq - 2r and at a distance of 2d cosq + 2r, respectively, from x. The first locus is the cardioid with center c, underlying radius d, its cusp at x, and (negative) eccentricity of -2r; the second locus is an otherwise similar cardioid with (positive) eccentricity of +2r. Such cardioids are shown in Figure – Theroem 6c.. Ferejohn, McKelvey, and Packel state the theorem this way: the region enclosed by the inner cardioid (with negative eccentricity) is contained in W(x) and W(x) in turn is contained in the outer cardioid (with positive eccentricity)

Figure – Theorem 6c

Given the preceding results, we can now readily prove McKelvey's "global cycling" theorem. We can also determine how long a cycle must be to include two arbitrary points, a consideration that has direct relevance also for the size of the uncovered set (since, if a point z beats an uncovered point x, there is some third point y such that x beats y and y beats z). Thus we can also derive McKelvey's circular bound on the uncovered set.

Consider a point x at distance d from the center of the yolk c. Let us construct two circles, both centered on c and with radii of d - 2r and d + 2r respectively. (The first circle will exist only if d > 2r.) It is apparent from Figure – Corollary 6.1, and from the discussion in the preceding section, that the region enclosed by the smaller circle is a subset of the region enclosed by the inner cardioid that is an inner bound on W(x), and the region enclosed by the larger circle is a superset of the region enclosed by the outer cardioid that is an outer bound on W(x). Thus these are circular (inner and outer) bounds on W(x); x beats every point in the smaller circle and is beaten by every point outside the larger circle.

Figure - Corollary 6.1

It is worth stating this formally, as a corollary to Theorem 6.

COROLLARY 6.1

If point y is more than 2r further from the center of the yolk than point x is, x beats y.

Note that this corollary subsumes Theorem 3, which pertains to the special case in which 2r = 0.

Given this corollary in conjunction with Theorem 4, we can prove McKelvey's (1976) "global cycling" theorem.

THEOREM 7

In the absence of an unbeaten point, for any pair of points x and y, we can find a majority preference cycle including both x and y.

Proof.

Suppose that x is beaten by y. By repeated application of Theorem 4, we can always construct trajectory of this form: y is beaten by z, z is beaten by w, and so forth, to a point at any finite distance from the center of the yolk. In particular, we can construct such a trajectory to some point v at a distance greater than d + 2r from the center of the yolk, where d is the distance from x to the center of the yolk. By Corollary 6.1, v is beaten by x. Thus we have the required cycle including both x and y. If y is beaten by x, we can construct a similar trajectory from x to y to get the required cycle. If x and y tie, we can construct similar trajectories from x to y and from y to x and put them together to get the required cycle. This establishes McKelvey's theorem.(20)

While Corollary 6.1, in conjunction with Theorem 4, establishes McKelvey's theorem, it also indicates a majority preference trajectory leading from point x to a point y considerably more distant from the center of the yolk may require many intermediate steps, especially if the yolk itself is small, since each step in the trajectory can lead at most 2r further out from the center of the yolk. We can state this formally.

COROLLARY 6.2

Given any two points x and y linked in a majority preference cycle including k points altogether, where d1 and d2 are the distances of x and y, respectively, from the center of the yolk and where d1 is less than d2, d2 - d1 cannot exceed 2r(k - 1).

We also have the following corollary.

COROLLARY 6.3

If point y is more than 4r away from the center of the yolk than point x is, x covers y.

Proof.

Let d1 and d2 be the distances of x and y, respectively, from the center of the yolk. Since d2 - d1 is greater than 4r, by Corollary 6.1 x beats y, and the circle centered on c with radius d2 - 2r encloses the circle centered on c with radius d1 + 2r. Any point z that y beats must be on or outside the larger circle (with radius d2 - 2r) but then z is outside the smaller circle as well, which means x beats z. So x beats everything y beats. Any point z that beats x must be on or inside the smaller circle (with radius d1 + 2r) but then z is inside the larger circle as well, which means z beats y. So z does not tie anything that beats x either. By definition, then, x covers y.

In Figure – Corollary 6.1, for example, every point inside the inner circle covers every point outside the outer circle.

We finally state the theorem giving McKelvey's (1986) bounds on the uncovered set.

THEOREM 8

The uncovered set of points is bounded by the circle centered on the center of the yolk with radius 4r.

Proof.

By Corollary 6.3, the point c at the center of the yolk covers all points outside the circle with center c and radius 4r. Thus the set of points not covered by c is within this circular bound. The uncovered set, i.e., the set of all points none of which is covered by any other point, is a subset of the set of points not covered by c. So, in any event, the uncovered set lies within the same circular bound.

Thus, any political choice process that produces outcomes in the uncovered set (such as those identified by Miller, 1980, and McKelvey, 1986), produce outcomes that are generally centrally located and, if the yolk is relatively small, confined to a relatively small portion of the issue space.