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 over alternatives ,

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 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:

Thus 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 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 , delete two voters: remove the ballots and . Both remaining copies of rank first, so it defeats every opponent by at least . One deletion cannot suffice: originally loses to by , and removing one opponent only produces a tie. Hence .

For , delete two voters: remove one copy of and the ballot . The retained rankings are

Now defeats by , by , and by . One deletion cannot repair its original loss to . Hence .

For , delete four voters: only the voter with prefers to . All four opposing voters must be removed for a strict victory over . Retaining that single voter makes a Condorcet winner, so .

For , delete four voters: only the voter with prefers to . All four opponents must be removed. The retained voter ranks first, so .

Therefore

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