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

技術要約：p-順序付け（p-ORDERINGS）：スレーターからケメニー・ヤング、そしてランク・ペアまで

問題提起
選好選挙において、投票用紙は候補者間のペアワイズ（二者間）の多数派差分を誘発する。多くの社会厚生ルールは、完全なプロファイルそのものよりも、こうした重み付けされたペアワイズ情報に依存しているが、異なるランキング・ルールを連結する統一的な枠組みは欠けていた。具体的には、本論文は、3つの著名なマージン（差分）に基づくルール、すなわちスレーター（Slater）順序（ペアワイズの不一致数を最小化する）、ケメニー・ヤング（Kemeny-Young）ルール（不一致の大きさの総和を最小化する）、およびランク・ペア（Ranked Pairs）（大きなマージンをレキシコグラフィックに優先する）の関係性を扱う。中心となる問題は、これらのルールが、マージン・オブ・ビクトリー（m.o.v.）行列に基づく特定の最適化原理から導出される、単一の標準的なランキング・ルールの家族の一員と見なせるかどうかである。

手法
著者らは、与えられたランキングと不一致となるペアワイズ多数派マージンの$p$ノルムを最小化することによって定義される、**p-順序付け（p-orderings）**と呼ばれるランキング・ルールの家族を導入する。

1. m.o.v.行列におけるpノルムの定義： 与えられた候補者の順序に対し、著者らはm.o.v.行列の上三角部分のうち、負の値（順序との不一致を示す）を持つエントリーを抽出する。そして、順序$\pi$の$p$ノルムを以下のように定義する：
   $$\|\pi\|_p = \left( \sum_{i<j, m_{ij}<0} |m_{ij}|^p \right)^{1/p}$$
   p-順序付けとは、この量を最小化する候補者の置換である。

2. 標準的な正当化（定理1）： 関数 $f(x) = |x|^p$ の選択は恣意的なものではない。スケール不変性、マージンの大きさにのみ依存すること、およびマージンの大きさに対する単調性の3つの自然な仮定の下で、著者らは、この構成と互換性のある唯一の連続スコア関数は $c|x|^p$ の形式であることを証明している。これにより、pファミリーが、マージンに基づく構築における標準的な範疇であることが確立される。

3. Q-sumによる最適化： 分析を容易にするため、著者らは符号付きの大きさ $\sum \mu_{ij} |m_{ij}|^p$ を合計する「Q-sum」（系2）を定義する。この和を最大化することは、負のエントリーの$p$ノルムを最小化することと等価である。

主な結果
本論文は、$p > 0$ のスペクトルにおけるp-順序付けの挙動を確立している：

• $p \to 0^+$ の極限（命題1）： $p$ノルムの最小化は、ペアワイズの不一致の「数」を最小化することと等価になる。したがって、p-順序付けはスレーター順序に収束する。
• $p = 1$ の場合（命題2）： 1-ノルム順序は、絶対的な不一致マージンの総和を最小化するケメニー・ヤングルールと数学的に等価である。
• $p \to \infty$ の極限（定理2）： 任意の選挙において、一意かつ非ゼロのペアワイズ・マージンが存在する場合、すべての $p \geq p^*$ に対して、p-順序付けは正確にランク・ペアの順序と一致する。
  • メカニズム： この証明は「累積的支配特性（Cumulative Dominance Property）」（補題3）に基づいている。$p$が増加するにつれ、最大の勝利マージンに対応する項が、他のすべての小さな項の和に対して支配的になる。その結果、最適化手順はレキシコグラフィック（辞書式）になり、最大のマージンを最初に満たし、次に大きなものを満たすという、ランク・ペアのアルゴリズムと全く同じ挙動を示す。
• 安定化： p-順序付けの集合は、正の$p$軸上の有限個の区間において一定である（命題9）。十分に大きな$p$に対して、解は（一意なマージンを仮定した場合）一意なランク・ペアの順序へと安定する。

p-順序付けの性質
本論文は、p-順序付けの家族に関する公理的な性質を分析している：

• スミス整合性（Smith-consistency）： すべての $p > 0$ において、p-順序付けはスミス・セット内の候補者をそれより外側にいる候補者よりも上位にランクする（命題5）。
• コンドルセ適合性（Condorcet Compatibility）： コンドルセ勝者が存在する場合、その者が第1位となり、コンドルセ敗者が存在する場合、その者が最下位となる。
• 単調性： p-順序付けが一意である場合、それは単調性を満たす（命題7）。
• 最後尾敗者独立性（Last Place Loser Independence）： 逆転した投票における最下位の候補者を除去しても、元の選挙の勝者は変化しない（命題6）。
• クローン不変性： この家族は一般にクローン不変ではない。なぜなら、ケメニー・ヤング・ルール（$p=1$）がこの基準を満たさないからである（命題3）。

意義
本論文は、スレーター、ケメニー・ヤング、およびランク・ペアという3つの異なる投票ルールを、ペアワイズの多数派マージンに基づく単一のパラメータを持つ家族へと統合することを主張している。ランク・ペアが、連続的な最適化プロセスによる自然な極限としての存在であることを示すことで、本研究は、カウントベース、合計ベース、およびレキシコグラフィックなアプローチの間の理論的な架け橋を提供している。著者らは、ランク・ペアが孤立したヒューリスティックではなく、マージンの大きさに駆動される連続的な最適化プロセスの自然な極限であることを強調している。なお、結果は、タイブレーク（同順位の決定）の問題を避けるために、一意かつ非ゼロのマージンを仮定して証明されており、ランク・ペアへの収束は、十分に大きなすべての$p$に対して成立する。