📈 economics

$p$ -orderings: From Slater to Kemeny-Young to Ranked Pairs

This paper introduces a unified family of ranking rules called $p$ -orderings, which minimize the $p$ -norm of pairwise majority disagreements and encompass Slater orderings, Kemeny-Young, and Ranked Pairs as specific limits or cases, while demonstrating that these rules are uniquely characterized by natural axioms of scale invariance and monotonicity.

Original authors: Amir Babak Aazami, Hubert Lewis Bray

Published 2026-06-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Amir Babak Aazami, Hubert Lewis Bray

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to settle a debate among a group of friends about the best movie of the year. Everyone has voted, but the results are messy. Some people love Movie A over B, others love B over C, but surprisingly, a third group thinks C is better than A. This creates a loop (A > B > C > A), making it impossible to declare a single, perfect winner just by looking at who beat whom.

This paper introduces a new, flexible family of rules called p-orderings to solve this messy problem. Think of this family as a "dial" or a "slider" that you can turn to change how much you care about the size of the disagreement between voters.

Here is how the dial works, moving from one end to the other:

1. The "Counting" End (Slater Orderings)

The Dial is set to almost zero ( $p \to 0$ ).
Imagine you are a strict accountant who only cares about how many times people disagree with your ranking, not how strongly they feel about it.

The Analogy: You have a pile of red cards. Every time your ranking contradicts the majority vote (e.g., you say A is better than B, but the crowd says B is better), you get a red card.
The Goal: You want the ranking with the fewest red cards.
The Result: This is called the Slater ordering. It treats a tiny 1-vote difference the same as a massive 1,000-vote difference. It just counts the mistakes.

2. The "Middle" End (Kemeny-Young Rule)

The Dial is set to 1 ( $p = 1$ ).
Now, you start caring about the size of the disagreement. A 10-vote margin feels ten times worse than a 1-vote margin.

The Analogy: Instead of just counting red cards, you are now measuring the "distance" of the disagreement. If the crowd disagrees with you by a lot, it hurts your score more.
The Goal: You want to minimize the total sum of these disagreement sizes.
The Result: This is the famous Kemeny-Young rule. It's like trying to find the path that requires the least total "effort" to explain the voters' preferences.

3. The "Biggest Problem" End (Ranked Pairs)

The Dial is turned all the way up (Large $p$ ).
Now, you become obsessed with the biggest disagreements. You don't care about the small stuff anymore; you only care about the one massive, glaring contradiction.

The Analogy: Imagine you are a judge looking at a list of crimes. You don't care about the 50 minor parking tickets; you only care about the one murder. If you can fix the murder, you don't care if you accidentally create 10 new parking tickets. You prioritize the "heaviest" violation above all else.
The Goal: You look at the biggest margin of victory (e.g., "A beats B by 50 votes"). You lock that in. Then you look at the next biggest. If it fits with the first one, you lock it in. If it creates a loop (a contradiction), you throw it away because it's the "weakest link" in that specific chain of logic.
The Result: This is the Ranked Pairs method. The paper proves that if you turn the dial high enough, your "p-ordering" becomes exactly Ranked Pairs.

The "Magic" of the Dial

The authors discovered something fascinating: This dial isn't random.

They asked, "Is there a mathematical reason why we should use this specific formula ( $|x|^p$ )?"
They proved that if you want a rule that:

Works the same way whether everyone votes once or ten times (Scale Invariance).
Only cares about how big the margin is, not the direction (Magnitude dependence).
Treats bigger margins as more important (Monotonicity).

...then the only possible formula you can use is this $|x|^p$ dial. It is the "canonical" (standard) way to measure these disagreements.

The "Freeze" Effect

The paper also explains what happens as you keep turning the dial higher and higher.

At first, as you increase $p$ , the ranking might jump around a bit as different combinations of votes become more or less important.
However, once you pass a certain "tipping point" (a specific number $p^*$ ), the ranking freezes.
No matter how much higher you turn the dial after that point, the result never changes again. It has locked onto the Ranked Pairs solution.

Summary

Think of the p-ordering as a single, universal machine for ranking candidates.

Turn the knob to 0, and it counts mistakes (Slater).
Turn the knob to 1, and it sums up the pain of mistakes (Kemeny-Young).
Turn the knob to infinity, and it prioritizes the biggest mistakes above all else (Ranked Pairs).

The paper shows that these three famous, seemingly different methods are actually just different settings on the same machine, and that this machine is mathematically the only one that fits the basic rules of fairness regarding vote margins.

Technical Summary: p-ORDERINGS: FROM SLATER TO KEMENY-YOUNG TO RANKED PAIRS

Problem Statement
In preferential elections, ballots induce pairwise majority margins between candidates. While many social welfare rules rely on this weighted pairwise information rather than the full profile, a unified framework connecting distinct ranking rules has been lacking. Specifically, the paper addresses the relationship between three prominent margin-based rules: Slater orderings (minimizing the number of pairwise disagreements), the Kemeny-Young rule (minimizing the sum of disagreement magnitudes), and Ranked Pairs (prioritizing larger margins lexicographically). The central problem is to determine if these rules can be viewed as members of a single, canonical family of ranking rules derived from a specific optimization principle on the margin-of-victory (m.o.v.) matrix.

Methodology
The authors introduce a family of ranking rules termed p-orderings, defined by minimizing the $p$ -norm of the pairwise majority margins that disagree with a given ranking.

Definition of the p-norm on m.o.v. matrices: For a given candidate ordering, the authors isolate the entries in the upper-triangular part of the m.o.v. matrix that are negative (indicating a disagreement with the ordering). They define the $p$ -norm of an ordering $\pi$ as:
$\|\pi\|_p = \left( \sum_{i<j, m_{ij}<0} |m_{ij}|^p \right)^{1/p}$
The p-ordering is the permutation of candidates that minimizes this quantity.
Canonical Justification (Theorem 1): The paper argues that the choice of the function $f(x) = |x|^p$ is not arbitrary. Under three natural assumptions—scale invariance, dependence only on margin magnitude, and monotonicity with respect to margin size—the authors prove that the only continuous score function compatible with this construction is of the form $c|x|^p$ . This establishes the p-family as canonical among margin-based constructions.
Optimization via Q-sum: To facilitate analysis, the authors define a "Q-sum" (Corollary 2), which sums signed magnitudes $\sum \mu_{ij} |m_{ij}|^p$ . Maximizing this sum is equivalent to minimizing the $p$ -norm of the negative entries.

Key Results
The paper establishes the behavior of p-orderings across the spectrum of $p > 0$ :

Limit as $p \to 0^+$ (Proposition 1): Minimizing the $p$ -norm becomes equivalent to minimizing the count of pairwise disagreements. Thus, the p-ordering converges to the Slater ordering.
Case $p = 1$ (Proposition 2): The 1-norm ordering is mathematically equivalent to the Kemeny-Young rule, which minimizes the sum of absolute disagreement margins.
Limit as $p \to \infty$ (Theorem 2): For any election with distinct, non-zero pairwise margins, there exists a threshold $p^*$ $p^{*}$ such that for all $p \geq p^*$ $p \geq p^{*}$ , the p-ordering coincides exactly with the Ranked Pairs ordering.
- Mechanism: The proof relies on a "Cumulative Dominance Property" (Lemma 3). As $p$ increases, the term corresponding to the largest margin of victory dominates the sum of all smaller terms. Consequently, the optimization procedure becomes lexicographic: it prioritizes satisfying the largest margins first, then the next largest, exactly mirroring the Ranked Pairs algorithm.
Stabilization: The set of p-orderings is constant over finitely many intervals on the positive $p$ -axis (Proposition 9). For sufficiently large $p$ , the solution stabilizes to the unique Ranked Pairs ordering (assuming distinct margins).

Properties of p-Orderings
The paper analyzes several axiomatic properties of the p-ordering family:

Smith-consistency: For all $p > 0$ , p-orderings rank candidates in the Smith set above those outside it (Proposition 5).
Condorcet Compatibility: If a Condorcet winner exists, they are ranked first; if a Condorcet loser exists, they are ranked last.
Monotonicity: If the p-ordering is unique, it satisfies the monotonicity property (Proposition 7).
Last Place Loser Independence: Removing the candidate ranked last in the reversed-ballot election does not alter the winner of the original election (Proposition 6).
Clone Invariance: The family is not generally clone invariant, as the Kemeny-Young rule ( $p=1$ ) fails this criterion (Proposition 3).

Significance
The paper claims to unify three distinct voting rules—Slater, Kemeny-Young, and Ranked Pairs—into a single one-parameter family of rules based on pairwise majority margins. By demonstrating that Ranked Pairs arises as the eventual large- $p$ member of this canonical family, the work provides a theoretical bridge between counting-based, sum-based, and lexicographic approaches to social choice. The authors emphasize that Ranked Pairs is not an isolated heuristic but the natural limit of a continuous optimization process driven by margin magnitudes. The results are proven under the assumption of distinct, non-zero margins to avoid tie-breaking complications, with the convergence to Ranked Pairs holding for all sufficiently large $p$ .