<p>This example comes from <a href="https://www.jstor.org/stable/2110925" rel="nofollow noreferrer">Miller (1980)</a> (the paper that introduced the uncovered set definition).</p>

<p>Suppose that the majority's preference is defined by:</p>

<p><span class="math-container">\begin{aligned}
x \succ y \\
x \succ z \\
y \succ v \\
y \succ z \\
v \succ x \\
z \succ v
\end{aligned}</span></p>

<p>In this example, we have the top cycle set <span class="math-container">$L_1 = \{x, y, z, v \}$</span> (you can check this).</p>

<p>But notice that <span class="math-container">$y$</span> is preferred to <span class="math-container">$z$</span> and all policies that are preferred to <span class="math-container">$y$</span> (namely <span class="math-container">$x$</span>), are preferred to <span class="math-container">$z$</span>. So, <span class="math-container">$y$</span> covers <span class="math-container">$z$</span> and the uncovered set <span class="math-container">$U$</span> is such that <span class="math-container">$U = \{x, y, v\}$</span> and <span class="math-container">$U \subset L_1$</span>.</p>

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

<ol>
<li>if there is a Condorcet winner, <span class="math-container">$L_1 = U$</span>;</li>
<li>if <span class="math-container">$L_1$</span> has three elements, then <span class="math-container">$L_1 = U$</span>;</li>
<li><span class="math-container">$U \subseteq L_1$</span>.</li>
</ol>

CC BY-SA 4.0
2019-04-07T20:48:13.267Z
2019-04-07T21:45:13.613Z
2019-04-07T21:45:13.613Z
Marcelo Gelati
<p>I am struggling to see when, given a policy set  <span class="math-container">$X = {x_{1}, … , x_{m}} $</span> , with <span class="math-container">$m &gt; 1$</span>, 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).</p>

<p>The <strong>uncovered set</strong> is defined as follows. Policy <span class="math-container">$x$</span> covers <span class="math-container">$y$</span> if (1) it is majority-preferred to <span class="math-container">$y$</span>, and (2) all policies that are majority-preferred to <span class="math-container">$x$</span> are likewise preferred to <span class="math-container">$y$</span>. If there is no <span class="math-container">$x$</span> that satisfies criteria (1) and (2), then we say that <span class="math-container">$y$</span> is uncovered. </p>

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

<p>We call these subsets of <span class="math-container">$X$</span> levels to suggest a mental picture: one can see the electoral environment as a series of levels or plateaus (if <span class="math-container">$k &gt; 1$</span>). 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 <span class="math-container">$X$</span>’s uncovered set is a subset of <span class="math-container">$L_{1}$</span>, the uncovered set of <span class="math-container">$X / L_{1}$</span> is a subset of <span class="math-container">$L_{2}$</span>, and so forth. </p>

<p>Defined constructively in this setting, a policy is in the top cycle set (<span class="math-container">$L_{1}$</span>)  if and only if it is reachable from every other policy by a chain of straight majority preference. </p>

<p>Specifically, given the above definition I cannot understand why the above definition of the top cycle set <em>implies that <span class="math-container">$X$</span>’s uncovered set is a subset of <span class="math-container">$L_{1}$</span></em>. </p>

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

<voting>
Uncovered set versus top cycle set (voting theory)
Ali
# Uncovered set versus top cycle set (voting theory)

(Asked by: username_0 on 2019-04-07)

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!

**Tags:** voting


---

## 1 answers

### Answer by username_1 on 2019-04-07. Score: 3 | Accepted answer

This example comes from [Miller (1980)](https://www.jstor.org/stable/2110925) (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$.


---

