Young Score (COMSOC)

Definition

Young Score ( COMSOC)

The Young score is the minimum number of voters whose removal makes an alternative $x$ a Condorcet winner. For a profile $R=({\succ }_i{)}_{i\in V}$ of complete, strict rankings,

$${\mathrm{Young}}_R(x):=\underset{S\subseteq V:x\text{ is a Condorcet winner in }R{|}_S}{\min }|V\setminus S|.$$

Here $R{|}_S$ retains only the voters in $S$. Delete whole ballots; do not change their rankings or remove alternatives. The majority threshold is recomputed using $|S|$, the number of retained voters. Every candidate is evaluated separately from the original profile.

If no retained electorate makes $x$ a Condorcet winner, set its score to $+\infty$. A score of zero means $x$ already wins every pairwise contest.

Intuition

Unlike Dodgson, Young deletes whole ballots. Each deletion changes both support counts and the majority threshold; a tie still does not suffice. Use the same three-voter profile below, starting afresh for each candidate.

Candidate A: no deletions

Voters 1 and 2 give $A$ a $2:1$ majority against both opponents. Delete nobody.

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

Candidate C: delete one opponent, then the other

$C$ loses to $A$ by $1:2$. Keep its sole supporter, voter 3; delete voter 1, who opposes $C$ against both alternatives.

The remaining $1:1$ tie against $A$ is insufficient. Delete voter 2, the remaining supporter of $A$ over $C$.

Both contests are now won. One deletion could only tie the original $1:2$ loss, so ${\mathrm{Young}}_R(C)=2$.

Candidate B: the necessary deletions still fail

$B$ loses both contests by $1:2$. Only voter 3 supports it against $A$. Keep voter 3 and first delete voter 2, who opposes $B$ in both contests.

To break the tie against $A$, delete voter 1—even though this removes $B$‘s only supporter against $C$.

Only this electorate lets $B$ beat $A$, but it loses to $C$. Deleting everyone gives no strict majority either. Hence ${\mathrm{Young}}_R(B)=+\infty$.

The Young winner is $A$:

$${\mathrm{Young}}_R(A)=0<{\mathrm{Young}}_R(C)=2<{\mathrm{Young}}_R(B)=+\infty .$$

Deleting ballots cannot create new preferences; this is why swaps can repair $B$ here but deletions cannot.

Score Convention

Young scores are also commonly expressed as the maximum number of voters retained, which is maximised rather than minimised. When a successful retained electorate exists, the two objectives satisfy

$$\underset{\text{lecture convention}}{\underbrace{\text{minimum deleted}}}=|V|-\underset{\text{retention convention}}{\underbrace{\text{maximum retained}}}.$$

Keep the convention explicit when comparing sources.