Young's Rule (COMSOC)

comsoc

Definition

Young's Rule

In COMSOC, Young’s Rule is a voting rule that selects the alternatives that can be made Condorcet winners by deleting as few voters as possible.

Let

$$R:=({\succ }_1,\dots ,{\succ }_n)$$

be a preference profile over alternatives $C$. For an alternative $x\in C$, its Young score is

$${\mathrm{Young}}_R(x):=\min \{|V\setminus V^{\prime }|:x\text{ is a Condorcet winner in }R{|}_{V^{\prime }}\},$$

where $V^{\prime }\subseteq V$ is a non-empty subset of voters and $R{|}_{V^{\prime }}$ is the profile restricted to those voters.

Young’s Rule returns the alternatives with minimum Young score:

$${\lambda }_{\mathrm{Young}}(R):=\arg \underset{x\in C}{\min }{\mathrm{Young}}_R(x).$$

Each alternative in this set is a Young winner.

Mechanism

Repairing the electorate

Dodgson’s Rule changes rankings by adjacent swaps. Young’s Rule instead keeps rankings unchanged and deletes voters. The Young score of $x$ counts the smallest number of voters whose removal makes $x$ defeat every other alternative by pairwise majority.

Properties

Condorcet winners have score zero

If $x$ is already a Condorcet winner, then

$${\mathrm{Young}}_R(x)=0.$$

Conversely, if ${\mathrm{Young}}_R(x)=0$, then $x$ is already a Condorcet winner.

Condorcet consistency

Young’s Rule is a Condorcet consistent voting rule.

Computational hardness

The lecture notes state that determining a Young winner is NP-hard.

Example

Lecture profile

Consider the profile from the lecture notes:

voters	ranking
$2$	$A\succ B\succ C\succ D$
$1$	$B\succ C\succ D\succ A$
$1$	$C\succ D\succ A\succ B$
$1$	$D\succ B\succ C\succ A$

In the full profile, there is no Condorcet winner. However, deleting the voters with rankings

$$C\succ D\succ A\succ B\text{and}D\succ B\succ C\succ A$$

leaves a three-voter subprofile where $A$ is a Condorcet winner. Thus

$${\mathrm{Young}}_R(A)\le 2.$$

In fact, the minimum is $2$ for both $A$ and $B$ in this profile, so $A$ and $B$ are Young co-winners.