# Uncovered set versus top cycle set (voting theory)

I am struggling to see when, given a policy set $$X = {x_{1}, … , x_{m}}$$ , with $$m > 1$$, its uncovered set and top cycle set may not coincide (i.e. when the top cycle set has policies that are not in the uncovered set).

The uncovered set is defined as follows. Policy $$x$$ covers $$y$$ if (1) it is majority-preferred to $$y$$, and (2) all policies that are majority-preferred to $$x$$ are likewise preferred to $$y$$. If there is no $$x$$ that satisfies criteria (1) and (2), then we say that $$y$$ is uncovered.

Next to this, the top cycle set is defined by partitioning the policy set into k disjoint subsets, $${L_{1}, … , L_{k}}, \text{where} \; 1 \leq k \leq m$$ by iteratively applying the idea of the top cycle set, where $$(L_{1} = {x ∈ X | \; ∄ \; y ∈ X / L_{1} \; s.t. \; y \succ x})$$

We call these subsets of $$X$$ levels to suggest a mental picture: one can see the electoral environment as a series of levels or plateaus (if $$k > 1$$). Each plateau electorally dominates those below it: each policy at a given level is majority-preferred to all policies at lower levels. Further, every policy at a level covers all policies at lower elevations. This implies that $$X$$’s uncovered set is a subset of $$L_{1}$$, the uncovered set of $$X / L_{1}$$ is a subset of $$L_{2}$$, and so forth.

Defined constructively in this setting, a policy is in the top cycle set ($$L_{1}$$) if and only if it is reachable from every other policy by a chain of straight majority preference.

Specifically, given the above definition I cannot understand why the above definition of the top cycle set implies that $$X$$’s uncovered set is a subset of $$L_{1}$$.

If anyone could think of an example or some other explanation/input for this I would greatly appreciate it. Thanks in advance!

This example comes from Miller (1980) (the paper that introduced the uncovered set definition).

Suppose that the majority's preference is defined by:

\begin{aligned} x \succ y \\ x \succ z \\ y \succ v \\ y \succ z \\ v \succ x \\ z \succ v \end{aligned}

In this example, we have the top cycle set $$L_1 = \{x, y, z, v \}$$ (you can check this).

But notice that $$y$$ is preferred to $$z$$ and all policies that are preferred to $$y$$ (namely $$x$$), are preferred to $$z$$. So, $$y$$ covers $$z$$ and the uncovered set $$U$$ is such that $$U = \{x, y, v\}$$ and $$U \subset L_1$$.

Among other stuff that Miller proves in his paper, we have the following three:

1. if there is a Condorcet winner, $$L_1 = U$$;
2. if $$L_1$$ has three elements, then $$L_1 = U$$;
3. $$U \subseteq L_1$$.