Neutral Voting Rule (COMSOC)

Definition

Neutral Voting Rule ( COMSOC)

A voting rule is neutral if renaming the alternatives only renames its outcome. Let $R=({\succ }_1,\dots ,{\succ }_n)$ be a profile over $C$, and let $\pi :C\to C$ be a permutation. Apply the same renaming to every ballot:

$$\pi (R):=(\pi ({\succ }_1),\dots ,\pi ({\succ }_n)),x{\succ }_{i}y⟺\pi (x)\pi ({\succ }_i)\pi (y).$$

For every profile $R$ and every permutation $\pi :C\to C$, the following condition must hold for the rule’s output type. One renaming that changes the outcome beyond merely renaming it disproves neutrality.

Single-winner output

$$f(\pi (R))=\pi (f(R)).$$

If $x$ wins before renaming, $\pi (x)$ wins afterwards.

Set-valued output

$$\lambda (\pi (R))=\pi (\lambda (R)),\pi (S):=\{\pi (x):x\in S\}.$$

The whole winner set is renamed; alternative names do not favour particular winners.

Ranking-valued output

For a rule $F$ returning a set of collective rankings,

$$F(\pi (R))=\{\pi (\succ ):\succ \in F(R)\}.$$

This is the lecture’s condition for the set of Kemeny consensuses: rename every alternative in every optimal ranking, without changing its positions.

Intuition

Start with a renaming of alternatives: $\pi (a)=b$, $\pi (b)=a$, $\pi (c)=c$. It exchanges the names $a,b$, not their positions on a ballot:

$$\underset{\text{original ranking}}{\underbrace{a\succ c\succ b}}⟼\underset{\text{renamed ranking}}{\underbrace{b\succ c\succ a}}.$$

The same symbol $\pi$ is then used for renaming larger objects, entry by entry:

$$\begin{array}{rl}\text{alternative:}& \pi (a)=b,\\ \text{winner set:}& \pi (\{a,c\})=\{b,c\},\\ \text{profile:}& \pi (({\succ }_1,{\succ }_2))=(\pi ({\succ }_1),\pi ({\succ }_2)).\end{array}$$

These are different operations induced by the same renaming. Strictly, the ranking operation has type ${\pi }_{\ast }:\mathcal{L}(C)\to \mathcal{L}(C)$; writing it as $\pi$ is a shorthand, not a claim that rankings belong to $C$.

Now suppose $\lambda (R)=\{a,c\}$. Neutrality compares two computations:

$$\begin{array}{rlrl}\pi (\lambda (R))& =\pi (\{a,c\})=\{b,c\}& & \text{compute winners, then rename},\\ \lambda (\pi (R))& =\{b,c\}& & \text{rename every ballot, then compute winners}.\end{array}$$

The first equality follows from the renaming. The second is what neutrality requires of the voting rule. Both computations must agree: changing names must not change which positions and preferences lead to victory.