Characterizations of voting rules based on majority margins

This paper characterizes margin-based voting rules by proving they are equivalent to rules satisfying the "Preferential Equality" axiom, which ensures that voters' identical pairwise preferences are treated with equal normative weight regardless of the voter's identity.

The Gist

Imagine you are organizing a massive, chaotic election where thousands of people are voting for their favorite candidates. The voters submit ranked lists: "I like Alice best, then Bob, then Charlie."

Now, imagine you are a detective trying to figure out the rules of the game. You notice that some voting systems (like Instant Runoff Voting, used in some real-world elections) seem to care about exactly who voted for whom. Other systems (like Borda Count or Schulze method) seem to only care about the final score of the head-to-head battles.

This paper asks a big question: Why should we care about the head-to-head scores? Is there a deep moral or logical reason why a voting rule should only look at "who beat whom and by how much," ignoring everything else?

The authors, Yifeng Ding, Wesley Holliday, and Eric Pacuit, say: Yes, there is a reason. They prove that if a voting rule follows two simple, fair principles, it must be a rule that only looks at head-to-head margins.

Here is the breakdown of their discovery, using simple analogies.

1. The "Scoreboard" vs. The "Play-by-Play"

Think of an election like a series of one-on-one boxing matches.

• The Play-by-Play (Full Profile): Who voted for whom? Did Alice get 10 votes from people who also liked Bob? Did she get 5 votes from people who hated Bob?
• The Scoreboard (Margins): In the match between Alice and Bob, did Alice win by 10 points? In the match between Bob and Charlie, did Bob win by 2 points?

A Margin-Based Rule is like a referee who only looks at the final scoreboard. If two different elections result in the exact same point differences between every pair of candidates, the referee declares the exact same winner, even if the individual voters were totally different people.

Many popular rules (like Plurality or Instant Runoff) are not like this. They look at the play-by-play. The authors want to know: Is it fair to ignore the play-by-play?

2. The Two Golden Rules of Fairness

The authors found that if a voting system follows two specific "Golden Rules," it is forced to become a "Scoreboard Only" system.

Rule #1: The "Swap Swap" (Preferential Equality)

Imagine two voters, Alice and Bob.

• Both Alice and Bob currently rank Candidate X immediately above Candidate Y.
• Now, imagine Alice changes her mind and swaps them (putting Y above X).
• Imagine instead that Bob changes his mind and swaps them.

The Rule: The election outcome should be exactly the same in both scenarios. It shouldn't matter who made the change, only that someone made the change.

The Analogy: Think of a tug-of-war. If two teams are pulling with equal strength, it doesn't matter which specific person on the team lets go of the rope; the result is the same. If a voting rule treats Alice's "swap" differently than Bob's "swap," it's like saying Alice's voice counts more than Bob's just because of her name. That's unfair.

• Real-world example: In Instant Runoff Voting (IRV), sometimes a small group of voters swapping their preferences can change the winner, while an identical group swapping the exact same way does not change the winner. The authors show this happens often in real data, proving IRV violates this fairness rule.

Rule #2: The "Perfect Opposites" (Neutral Reversal)

Imagine two voters, Charlie and Diana.

• Charlie ranks the candidates: A > B > C.
• Diana ranks them perfectly opposite: C > B > A.

The Rule: If you add these two voters to an election, the winner shouldn't change. Their preferences cancel each other out perfectly, like adding +5 and -5 to a bank account.

The Analogy: Imagine a seesaw. If a heavy kid sits on the left and an equally heavy kid sits on the right, the seesaw stays balanced. Adding them doesn't tip the scale. If a voting rule says, "Oh, adding these two opposites actually changes the winner because of how the math works," then the rule is broken.

3. The Big Discovery

The authors proved a mathematical magic trick:

If a voting rule follows the "Swap Swap" rule AND the "Perfect Opposites" rule, it MUST be a Margin-Based rule.

It's like saying: "If you follow these two laws of physics, you are forced to live in a universe where gravity works this specific way." You can't follow the laws of fairness and not end up with a system that only cares about head-to-head margins.

4. What About Ties and "Empty" Votes?

The paper also tackles messy real-world scenarios where voters might leave some candidates blank or tie two candidates together (e.g., "I like A and B equally").

• They introduced a third rule called Tiebreaking Compensation: If two people are tied between A and B, and one breaks the tie for A while the other breaks it for B, the result should be the same.
• They also introduced Neutral Indifference: Adding a voter who doesn't care about anyone (an "empty ballot") shouldn't change the winner.

When you add these rules to the mix, the same logic holds: Fairness forces you to rely on margins.

5. Why Does This Matter?

You might ask, "So what? Why do we need to prove this?"

The authors show that many real-world voting systems (like Minimax, a popular method for resolving complex elections) have two different versions:

1. The Margin Version: Looks at the point difference.
2. The "Winning Votes" Version: Looks at how many people voted for the winner, regardless of the margin.

In real elections, these two versions often pick different winners.

• In a 2007 Glasgow election, the Margin version picked Candidate Dornan, while the Winning Votes version picked Flanagan.
• In a 2021 Minneapolis election, the Margin version picked Arab, while the Winning Votes version picked Worlobach.

The paper argues that if you believe in the "Golden Rules" of fairness (Swap Swap and Perfect Opposites), you must choose the Margin Version. The "Winning Votes" version violates the principle that every voter's preference should be treated equally.

Summary

This paper is a defense of simplicity and fairness.

• It argues that if you want a voting system where every voter is treated equally and where opposing views cancel each other out, you are logically forced to use a system that only looks at who beat whom and by how much.
• Any system that looks deeper into the "play-by-play" (like Instant Runoff) inevitably creates situations where some voters have more power than others, simply by virtue of when or how they voted.

The authors have provided the "normative" (moral) proof that the "Scoreboard" approach is the only truly fair way to run an election.

Technical Summary

Here is a detailed technical summary of the paper "Characterizations of voting rules based on majority margins" by Yifeng Ding, Wesley H. Holliday, and Eric Pacuit.

1. Problem Statement

In voting theory, a margin-based rule (or pairwise rule) is defined by the property that the election outcome depends only on the head-to-head margins of victory between candidates. Formally, if two profiles $P$ and $Q$ yield the same margin matrix $M_P = M_Q$ (where $M_P(x,y)$ is the number of voters ranking $x$ above $y$ minus those ranking $y$ above $x$), the rule must produce the same outcome.

While mathematically natural, it is unclear whether this invariance property constitutes a desirable normative axiom. Many standard rules (e.g., Plurality, Instant Runoff Voting) are not margin-based, while others (e.g., Borda Count, Condorcet methods) are. Furthermore, there exists a broader class of head-to-head rules (related to Fishburn's $C_2$ rules) that depend on the raw vote counts ($\#_P$) and total voter count, not just the margins.

The paper addresses two core questions:

1. Can margin-based rules be characterized by a set of axioms with clear normative content (fairness, equality, balance) rather than just mathematical invariance?
2. How do margin-based rules relate to the broader classes of head-to-head and $C_2$ rules, and what specific axioms distinguish them?

2. Methodology

The authors employ an axiomatic approach to social choice theory. They define specific domains of profiles and propose new or existing axioms to characterize the class of margin-based rules.

• Domains:
  • Linear Profiles: Voters submit strict linear orders (no ties).
  • LOBI (Linear Orders with Bottom Indifference): Voters submit linear orders but may leave candidates unranked (treated as a tie at the bottom). This models real-world elections where voters do not rank all candidates.
  • All Profiles: Voters submit strict weak orders (allowing ties anywhere).
• Key Axioms Introduced/Utilized:
  • Preferential Equality: If two voters both rank $x$ immediately above $y$, swapping them to rank $y$ above $x$ should have the same effect on the outcome regardless of which voter makes the switch. This ensures equal treatment of voters with identical local preferences.
  • Neutral Reversal: Adding a pair of voters with fully reversed rankings (one $L$, one $L^{-1}$) does not change the outcome. This captures the idea that opposing views cancel out.
  • Block Invariance: Adding exactly one copy of every possible linear order (a "block") does not change the outcome.
  • Tiebreaking Compensation: If two voters have a tie over a set of candidates $Y$, and they break the tie in opposite ways (one linearizes $Y$ as $L$, the other as $L^{-1}$), the outcome remains unchanged.
  • Neutral Indifference: Adding a voter with a fully indifferent ranking (empty ballot) does not change the outcome.
  • Nonlinear Neutral Reversal: A strengthening of Neutral Reversal applicable to strict weak orders (allowing ties in the reversed pair).
• Homogeneity: A standard assumption (often required) stating that replicating the electorate $n$ times does not change the outcome.

3. Key Contributions and Results

The paper provides a series of characterization theorems across different domains and assumptions.

A. Characterization on Linear Profiles

Theorem 2.9: On the domain of linear profiles, a voting rule is margin-based if and only if it satisfies:

1. Preferential Equality
2. Neutral Reversal

Significance: This establishes that the mathematical property of being margin-based is equivalent to two intuitive normative principles: equal treatment of voters with similar local preferences and the cancellation of perfectly opposing voters.

Theorem 2.21: If the rule satisfies Homogeneity, Neutral Reversal can be weakened to Block Invariance.
Significance: Block Invariance is less controversial (satisfied by Plurality and IRV) than Neutral Reversal. This result shows that under homogeneity, margin-based rules are those that treat a "block" of all possible preferences neutrally.

B. Characterization on All Profiles (with Homogeneity)

When allowing ties (strict weak orders), the authors introduce axioms to handle indifference.

Theorem 3.8:

1. LOBI Domain: A homogeneous rule is margin-based iff it satisfies Preferential Equality, Tiebreaking Compensation, and Neutral Indifference.
2. All Profiles Domain: A homogeneous rule is margin-based iff it satisfies Tiebreaking Compensation and Neutral Indifference.
   • Note: On the domain of all profiles, Tiebreaking Compensation implies Preferential Equality (Lemma 3.3).

Significance: Tiebreaking Compensation is crucial here. It ensures that when voters break ties, their opposing choices cancel out, preventing the rule from depending on how ties are broken rather than just the margins. Neutral Indifference ensures the rule ignores voters who express no preference, distinguishing margin-based rules from general head-to-head rules (which might depend on the total number of voters).

C. Characterization Relative to Head-to-Head Rules

The paper distinguishes margin-based rules from the larger class of head-to-head rules (which depend on $\#_P$ and $|V|$) and $C_2$ rules (which depend only on $\#_P$).

Theorem 4.4: For a head-to-head voting rule on all profiles, it is margin-based if and only if it satisfies:

1. Nonlinear Neutral Reversal
2. Neutral Indifference

Proposition 3.7 & 4.5:

• A head-to-head rule is $C_2$ iff it satisfies Neutral Indifference.
• A $C_2$ rule is margin-based iff it satisfies Nonlinear Neutral Reversal.

Significance: This creates a hierarchy:

• Head-to-Head $\xrightarrow{\text{Neutral Indifference}}$ $C_2$ $\xrightarrow{\text{Nonlinear Neutral Reversal}}$ Margin-Based.
  This clarifies exactly what extra information (beyond vote counts) margin-based rules discard: the specific way ties are broken and the absolute number of voters (beyond what is needed for margins).

4. Empirical and Practical Significance

The authors demonstrate that these distinctions are not merely theoretical but affect real-world election outcomes.

• Minimax Variants: The paper contrasts the standard Minimax rule (based on margins) with the "Winning Votes" version (based on raw counts, a $C_2$ rule).
  • In many real-world datasets (e.g., Glasgow City Council, Minneapolis City Council), these two rules select different winners.
  • The "Winning Votes" version violates Preferential Equality and Positive Involvement (adding a voter who ranks the winner first can cause them to lose), whereas the margin-based version satisfies these.
• IRV Violations: The paper provides empirical evidence (Table 3) that Instant Runoff Voting (IRV) frequently violates Preferential Equality in real elections. In IRV, a coalition of voters changing a local preference (flipping $x$ and $y$) can have a different impact than an equally sized coalition making the same change, depending on the global structure of the profile. This highlights a normative flaw in non-margin-based rules regarding voter equality.

5. Conclusion

The paper successfully argues that margin-based voting rules are not just a mathematical convenience but are normatively grounded in principles of equality (Preferential Equality/Tiebreaking Compensation) and balance (Neutral Reversal/Block Invariance).

• Main Takeaway: If a voting system is designed to treat voters equally regardless of their position in the ranking (Preferential Equality) and to cancel out perfectly opposing views (Neutral Reversal), it must be a margin-based rule.
• Implication: Rules like Plurality and IRV, which fail these axioms, inherently treat voters unequally or rely on information (like the total number of voters or specific tie-breaking mechanisms) that should arguably be irrelevant to the determination of a majority winner.
• Future Work: The authors suggest exploring whether other invariance properties (like ordinal margin invariance or $C_1$ rules) can be similarly characterized by normative axioms, though they suspect stronger invariance properties may lack compelling normative justifications.