On the uniqueness of the yolk

Abstract

The yolk, an important concept of spatial majority voting theory, is assumed to be unique when the number of individuals is odd. We prove that this claim is true in ${\mathbb {R}} ^{2}$ but false in ${\mathbb {R}} ^{3}$, and discuss the differing implications of non-uniqueness from the normative and predictive perspectives.

In spatial (Euclidean) voting theory, individual voters are represented by their ideal points in a space of dimension k. The number of voters, n, is ordinarily assumed to be odd. A hyperplane in ${\mathbb {R}} ^{k}$ is non-strict median if both of the two closed half-spaces it defines contain at least $\lceil \frac{n}{2}\rceil$ ideal points. The yolk¹, an important concept in spatial voting theory introduced by McKelvey (1986), is a smallest ball that intersects every non-strict median hyperplane. Tovey (1992, footnote 1, p 270) claims that the yolk is unique if n is odd, which is not the case if n is even. Others have implicitly assumed uniqueness by defining the yolk as the smallest ball intersecting every median hyperplane (see, e.g., Grofman et al. 1988). Here we prove that for odd n the yolk is always unique in 2 dimensions, but not in 3 dimensions.

In what follows, Co(S) denotes the convex hull of the ideal points for the members of S (any subset of individuals) and |E| is the cardinality of any finite set E. We do not restrict n to be odd. Hence we define the set of minimal blocking² coalitions as ${\mathcal {W}}=\left\{ S:\frac{n}{2}\le |S|<\frac{n}{2}+1\right\}$. Define the ball B(c, r) to be the set of points at (Euclidean) distance at most r from its center c. The infinitude of non-strict median hyperplanes makes it impossible to check explicitly whether a ball intersects all of them. We begin with a finite characterization of the property of intersecting all non-strict median hyperplanes.

FormalPara Proposition 1

A ball B intersects every non-strict median hyperplane if and only if it intersects every Co(S),  $S\in {\mathcal {W}}$. Hence B is a yolk iff it is a smallest ball that intersects every Co(S),  $S\in {\mathcal {W}}$.

FormalPara Proof

$\Rightarrow )$ Assume that there exists S such that $S\in {\mathcal {W}}$ and $B\cap Co(S)=\varnothing$. The ball B and the polytope Co(S) are convex, compact and disjoint. Applying the strict separation theorem, there is a hyperplane ${\mathbf {H}}$ which strictly separates B and Co(S). Since Co(S) contains the ideal points of at least $\lceil \frac{n}{2}\rceil$ voters, there exists a non-strict median hyperplane parallel to ${\mathbf {H}}$ in the half-space containing Co(S), which thus does not intersect B, a contradiction.

$\Leftarrow )$ Conversely, assume that the ball B intersects every Co(S),  $S\in {\mathcal {W}}.$ Let ${\mathbf {H}}$ be a non-strict median hyperplane, and let ${\mathbf {H}}_{t}$, $t\in \{1,2\}$ denote the two closed half-spaces it defines. Let $S_{t}=S\cap {\mathbf {H}}_{t}$, the set of individuals whose ideal points are in the half-space ${\mathbf {H}}_{t}$, $t\in \{1,2\}$. Since ${\mathbf {H}}$ is non-strict median, $|S_{t}|\ge \lceil \frac{n}{2}\rceil$. Hence $S_{t}$ contains at least one member of ${\mathcal {W}}$ and so by assumption ${\mathbf {B}}\cap Co(S_{t})\ne \varnothing$, $t\in \{1,2\}$. By convexity of ${\mathbf {B}}$ this implies ${\mathbf {B}}\cap {\mathbf {H}}\ne \varnothing$. $\square$

As Nicholas Miller has pointed out, Proposition 1 is of intrinsic interest because it provides the first finite characterization of the yolk in the literature, to the best of our knowledge. There is a fine distinction to be made here. Tovey’s polynomial time yolk-finding algorithm for any fixed dimension kTovey (1992) finds a polynomially-bounded size set of non-strict median hyperplanes that must contain the farthest non-strict median hyperplane from a given point. Therefore, any ball can be tested against a polynomially small finite set to determine whether or not it intersects all non-strict median hyperplanes. However, each point in ${\mathbb {R}} ^{k}$ has its own set. The union of all these sets can be uncountably infinite. In contrast, Proposition 1 gives a single finite (though exponentially large ) test to determine if a ball intersects all non-strict median hyperplanes.

FormalPara Proposition 2

In ${\mathbb {R}} ^{2}$, the yolk is unique if the number of voters is odd.

FormalPara Proof

Let the ball $\zeta =B(c,r)$ be a yolk. By Proposition 1 $\zeta$ intersects every Co(S),  $S\in {\mathcal {W}}$. By compactness of polytopes let $d(c,Co(S))=\min _{x\in Co(S)}||x-c||$ denote the distance from c to the polytope Co(S) and let ${\mathcal {T}}$ denote the set of $T\in {\mathcal {W}}$ such that $d(c,Co(T))=r$. By convexity of Co(T), $|Co(T)\cap \zeta |=1\ \forall T\in {\mathcal {T}}$. For ease of notation let $\zeta (T)=Co(T)\cap \zeta$ for $T\in {\mathcal {T}}$.

We claim that $c\in Co(\{\zeta (T):T\in {\mathcal {T}}\})$. For proof, suppose not. Then there exists a strictly separating hyperplane ${\mathcal {H}}$ between c and the convex hull of $\{\zeta (T):T\in {\mathcal {T}}\}$. Let $c^{*}$ be the projection of c onto ${\mathcal {H}}$, see Fig. 1a. Then for all $0<\lambda \le 1$ the convex combination $\lambda c^{*}+(1-\lambda )c$ is strictly closer to all $\zeta (T):T\in {\mathcal {T}}$ than is c. Therefore $d(\lambda c^{*}+(1-\lambda )c,Co(T))\le d(\lambda c^{*}+(1-\lambda )c,\zeta (T))<r$ for all $0<\lambda \le 1$.

Since ${\mathcal {W}}$ is finite,

$$\begin{aligned} \max _{T\in {\mathcal {W}}\setminus {\mathcal {T}}}d(c,Co(T))<r. \end{aligned}$$

Therefore, for sufficiently small $\lambda >0$,

$$\begin{aligned} \max _{T\in {\mathcal {W}}}d(\lambda c^{*}+(1-\lambda )c,Co(T))<r. \end{aligned}$$

This contradicts the minimality of r and proves the claim.

The proof so far has not relied on the dimension $k=2$. We have written it for general $k\ge 2$ in case it is of use in future research. From here on the proof depends on $\zeta$ being a circle. Since n is odd, no two median lines are parallel. Therefore no two points in $\{\zeta (T):T\in {\mathcal {T}}\}$ are diametrically opposite on the circle $\zeta$. Hence there must exist three distinct points $t_{1},t_{2},t_{3}\in \{\zeta (T):T\in {\mathcal {T}}\}$ such that c is in the strict interior of the triangle with vertices $t_{j}:j=1,2,3$, see Fig. 1b.

Fig. 1

Uniqueness of the yolk in 2-dimension with an odd number of voters

Let ${\mathcal {H}}_{j}$ be the median line tangent to $\zeta$ at $t_{j} :j=1,2,3$. (The median line must be tangent to $\zeta$ because $|Co(T)\cap \zeta |=1\ \forall T\in {\mathcal {T}}$.) Then $\zeta$ is the inscribed circle of the triangle formed by the lines ${\mathcal {H}}_{j}:j=1,2,3$. By elementary geometry, c is the unique point whose maximum distance from the three lines is less than or equal to r. Therefore $\zeta$ is the unique yolk.$\square$

As mentioned by Tovey (1992), if the number of individuals is even, then the yolk is not always unique, as illustrated in Fig. 2.

Fig. 2

Non-uniqueness of the yolk in 2-dimension with an even number of voters

Indeed, we can determine the yolk based on the limiting median lines³. For this purpose, it is clear that the dashed and the solid circles are two possible yolks. This phenomenon can be avoided by using a different definition of yolk. For odd or even numbers of individuals, we define a strict median hyperplane as a hyperplane that partitions the n ideals points so that at least a strict majority (winning coalition) of ideal points lies each closed half-hyperplane. In the same spirit, a strict yolk is a smallest ball which intersects every strict median hyperplane. Thus, with n even, there are two distinct yolks possibly with different centers and radii: an “inner yolk” defined with respect to strict median lines and an “outer yolk” defined with respect to non-strict median lines. In Fig. 2, the inner yolk is reduced to the single point c (with a zero radius) unlike the outer yolk, which is not unique (with a non-zero radius).

Two strict median lines have a common point in ${\mathbb {R}} ^{2},$ hence they cannot be parallel. It follows from the proof of Proposition 2 that the strict yolk is also unique in ${\mathbb {R}} ^{2}$.

FormalPara Proposition 3

In ${\mathbb {R}} ^{3}$, the yolk is not always unique even if the number of individuals is odd.

FormalPara Proof

Consider Fig. 3a with seven ideal points, six placed at the vertices of two congruent opposing equilateral triangles, and the seventh placed at their center of mass.

Fig. 3

Non-uniqueness of the yolk in 3-dimension or more with an odd number of voters

Assume that $Q^{0}=(5,5\sqrt{3}/3,1)$, $Q^{1}=(0,0,0),$ $Q^{2}=(5,5\sqrt{3},0)$, $Q^{3}=(10,0,0)$, $Q^{4}=(0,0,2)$, $Q^{5}=(5,5\sqrt{3},2)$ and $Q^{6}=(10,0,2)$.

According to Proposition 1, the yolk intersects all Co(S),  $S\in {\mathcal {W}}$, thus it intersects the three vertical sides represented by the rectangles $(Q^{1}Q^{2}Q^{4}Q^{5})$, $(Q^{1}Q^{3}Q^{4}Q^{6})$ and $(Q^{2}Q^{3}Q^{5}Q^{6})$. Therefore, the radius of the yolk is at least $5/\sqrt{3}$, that is to say the radius of the inscribed circle of the equilateral triangle of side length 10. It is obvious that the sphere centered at $Q^{0}$ with radius $5/\sqrt{3}$ strictly intersects Co(S),  $S\in {\mathcal {W}}$, except for S included in a vertical side tangent to the sphere. Thus, the sphere can be moved in the vertical sense while continuing to intersect every Co(S),  $S\in {\mathcal {W}}$. Specifically, we can move the sphere vertically from 1 around the point $Q^{0}$, consequently, the set of the centers of the yolk is a segment $\left[ A,B\right] ,$ ($A=(5,5\sqrt{3}/3,0)$ and $B=(5,5\sqrt{3}/3,2)$) with length 2. More generally, suppose that for this example, the coordinates of the points are chosen such that the radius of the yolk is r and the height of the solid is h. If $h\ge 2r,$ then the set of the centers of the yolk is a vertical segment (centered at $Q^{0}$) with length 2r, otherwise, it is a vertical segment with length h. The yolk is not unique. $\square$

FormalPara Remark 1

In this example, the important criterion relates to the configuration of the three side faces ($(Q^{1}Q^{2}Q^{4}Q^{5})$, $(Q^{1}Q^{3}Q^{4}Q^{6})$ and $(Q^{2}Q^{3}Q^{5}Q^{6})$). By keeping the vertical position, we can consider several modifications to the figure which always lead to multiple yolks. For example, independently we can move the ideal points on an edge (in Fig. 3b, the point $Q^{2}$ has been moved upwards and the point $Q^{6}$ down). We can move (regardless of the direction), a vertical edge leaving it vertical (see edge $\left( Q^{1}Q^{4}\right)$ in Fig. 3b). These two modifications show that there are no particular constraints on the triangles which form the base, the vertical edges ($\left[ Q^{1},Q^{4}\right] ,$ $\left[ Q^{2},Q^{5}\right]$ and $\left[ Q^{3},Q^{6}\right]$) can have different lengths and therefore, the side faces may be different trapezoids. Finally, the point $Q^{0}$ can be moved regardless of the direction (within reasonable limits).

The non-uniqueness of the yolk has quite different implications for normative than for predictive purposes. From the normative point of view, multiplicity weakens the yolk concept because the yolk center fails to prescribe a single solution. A planner who intends to select the yolk center as the societal solution would be stymied without introducing a secondary tie-breaking criterion. We would therefore characterize non-uniqueness as a negative feature in the normative sense. Several other solution concepts based on minimization might be problematic in the same way. Owen and Shapley (1989) proved the existence and uniqueness of the strong point⁴, or Copeland winner, in 2 dimensions, but uniqueness has remained an open question in 3 or more dimensions. Likewise, it is an open question whether or not the Finagle point (Wuffle et al. 1989) is unique in 2 or more dimensions (Tovey 2011). Uniqueness of the $\epsilon ^{*}-core$ (Eban and Stephen 1990; Tovey 2010) is also unproved, and indeed the nonconvexity of the associated $\epsilon$-radius function (Tovey 2010) suggests non-uniqueness. Ironically, the core solution concept is well-known to be problematic for the opposite reason: a core exists with zero probability in 2 or more dimensions for n odd (Plott 1967), with zero probability in 3 or more dimensions for n even (Rubinstein 1979; Schofield 1983), and with positive but very small probability in 2 dimensions for n even (Tovey 2010).

In contrast, from the predictive point of view, multiplicity functions as a neutral or positive feature. The two main results about the yolk as a predictor of the outcome of majority-rule voting are McKelvey’s bound on Miller’s uncovered set and the Ferejohn-McKelvey-Packel bounds on the stationary distribution of Markovian voting processes. We now show that yolk multiplicity improves the former and has no effect upon the latter.

The uncovered set, proposed by Miller (1980, (1983), contains all possible outcomes of strategic voting under many sequential majority-rule voting protocols, because if x is uncovered and y is any other point in ${\mathbb {R}} ^{k}$, either x defeats y or x defeats some other point z that in turn defeats y. However, as reported by Joseph Godfrey (see Miller 2007), only brute-force methods to compute it are known. One of McKelvey’s motivations for inventing the yolk was to get a computational handle on the uncovered set. In McKelvey (1986) he proves that a ball centered at the yolk center, with radius 4 times the yolk radius, contains the uncovered set. Scott et al. (1987) improved the factor 4 to 3.7 for the case of $k=2$ dimensions.) A reading of McKelvey’s proof shows that it does not assume uniqueness of the yolk. Indeed, any ball that intersects all median hyperplanes, if its radius is increased by a factor of 4, must contain the uncovered set. Suppose now that U is the uncovered set, C is the set of yolk centers and r is the yolk radius. Then

$$\begin{aligned} U\subset \Omega =\bigcap _{c\in C}B(c,4r). \end{aligned}$$

That is, the intersection of all the expanded yolks contains the uncovered set. Therefore, whenever the yolk is not unique, it provides a strictly smaller containment $\Omega$ of the uncovered set. For the configuration of ideal points adopted in the proof of Proposition 3, $\Omega$ consists of two spherical caps with $b=3r$ height (the darkest central region on the Fig. 4). Indeed, C is the segment $\left[ c,c^{\prime }\right]$ with length 2r.

Fig. 4

Implication of the non-uniqueness of the yolk on the uncovered set

With basic geometry, we obtain $V\left( \Omega \right) = 54\pi r^{3}$ which represents $63.28~\%$ of the volume of a sphere with radius 4r.

Ferejohn et al. (1984) prove that a Markov process that at each step replaces the incumbent point in ${\mathbb {R}} ^{k}$ by a uniform random choice from the set of points that defeat the incumbent by majority vote has a limiting stationary distribution. They compute lower bounds on the stationary probability within balls of radius mr. In 2 dimensions, the probability exceeds $70\,\%$ at $m=4$; for both 2 and 3 dimensions, the probability exceeds $90\,\%$ for $m=7$. A reading of their proofs shows that the ball center is assumed to be a yolk center, but uniqueness is not assumed⁵. Therefore, yolk multiplicity does not invalidate their bounds. On the other hand, it does not tighten the bounds. Let $\bar{B}_{6}$ and $\bar{B}_{6}^{^{\prime }}$ be balls of equal radius, centered at distinct yolk centers in ${\mathbb {R}} ^{3}$. According to Table 1 in Ferejohn et al. (1984), the probability is at least 0.917 that the Markov process resides in $\bar{B}_{6}$, and is at least 0.917 that it resides in $\bar{B}_{6}^{^{\prime }}$, but that does not imply that the probability of residing in $\bar{B}_{6}\cap \bar{B}_{6}^{^{\prime }}$ is at least 0.917.

Several open questions remain: (1) it should be interesting to know whether or not the example of Proposition 3 is pathological. Is the set of ideal point configurations within a unit ball for which the yolk is not unique a set of measure zero? (2) It is easy to show that the set of yolk centers cannot contain an open k-dimensional ball. However, in our $k=3$ dimensional example, the set of yolk centers is only 1-dimensional. Is the set of yolk centers at most $k-2$ dimensional for n odd? We suspect that the answers to both questions are affirmative.