Young Rule (COMSOC)

Definition

Young Rule ( COMSOC)

The Young rule is the voting rule selecting alternatives with the smallest Young score, using the lecture’s minimum-deletions convention. For a profile $R$ over alternatives $C$,

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

It selects the alternatives requiring the fewest voter deletions to become Condorcet winners. All alternatives attaining the minimum are Young winners. Rankings of retained voters remain unchanged; these deletions are hypothetical comparisons, not changes actually made to the election.

Condorcet Consistency

If $c$ is already the Condorcet winner, no deletions are needed. Every other alternative requires at least one deletion, if it can be made a Condorcet winner at all:

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

Thus $c$ is the unique Young winner, so the rule is Condorcet consistent.

Winner Determination

For a proposed retained electorate, checking all of a candidate’s pairwise contests is straightforward. Finding the best electorate requires choosing which voters to remove; different deletions affect different opponents simultaneously.

Determining whether a given alternative is a Young winner is NP-hard. Simply enumerating all $2^n$ voter subsets gives an exhaustive approach, not a polynomial-time algorithm. The hardness claim is a complexity result, not a consequence of enumeration alone being slow.

Example

The same five-voter profile

Each row groups voters with the same complete ranking. Deleting one voter from the first row removes only one of its two identical ballots.

For $A$, delete two voters: remove the ballots $B\succ C\succ D\succ A$ and $C\succ D\succ A\succ B$. Both remaining copies of $A\succ B\succ C\succ D$ rank $A$ first, so it defeats every opponent by at least $2:1$. One deletion cannot suffice: $A$ originally loses to $C$ by $2:3$, and removing one opponent only produces a tie. Hence ${\mathrm{Young}}_R(A)=2$.

For $B$, delete two voters: remove one copy of $A\succ B\succ C\succ D$ and the ballot $C\succ D\succ A\succ B$. The retained rankings are

$$A\succ B\succ C\succ D,B\succ C\succ D\succ A,D\succ B\succ C\succ A.$$

Now $B$ defeats $A$ by $2:1$, $C$ by $3:0$, and $D$ by $2:1$. One deletion cannot repair its original $2:3$ loss to $A$. Hence ${\mathrm{Young}}_R(B)=2$.

For $C$, delete four voters: only the voter with $C\succ D\succ A\succ B$ prefers $C$ to $B$. All four opposing voters must be removed for a strict victory over $B$. Retaining that single voter makes $C$ a Condorcet winner, so ${\mathrm{Young}}_R(C)=4$.

For $D$, delete four voters: only the voter with $D\succ B\succ C\succ A$ prefers $D$ to $C$. All four opponents must be removed. The retained voter ranks $D$ first, so ${\mathrm{Young}}_R(D)=4$.

Therefore

$$({\mathrm{Young}}_R(A),{\mathrm{Young}}_R(B),{\mathrm{Young}}_R(C),{\mathrm{Young}}_R(D))=(2,2,4,4),{\lambda }_{\mathrm{Young}}(R)=\{A,B\}.$$

Each score uses its own hypothetical deletions from the original profile; the deletions are not applied consecutively.