技術要約：順位集計における比例代表制

問題定義

本論文は、重み付きの入力順位のプロファイルから単一の出力順位を組み合わせることを目的とする、**順位集計（rank aggregation）**の問題に取り組んでいる。この設定において、プロファイル $R$ は候補集合 $C$ と、あらゆる可能な順位 $\succ$ を重み $R(\succ) \in [0, 1]$ にマッピングする関数から構成され、すべての重みの合計は1となる。これらの重みは、異なる基準（例：ホテルの予約における価格対評価）の重要性や、特定の順位を支持する投票者のシェアを表している。

特定された中心的な課題は、ケメニー・ルール（Kemeny rule）、ボルダ・カウント（Borda count）、コンドルセ型ルール（Condorcet-type rules）といった古典的な社会厚生関数（SWF）は、本質的に**多数決主義的（majoritarian）**であるという点である。これらは、最も重みの高い入力順位との距離を最小化する出力順位を選択する傾向があり、結果として少数派の好意を無視してしまう。例えば、2つの逆順位の重みがそれぞれ51%と49%である場合、標準的なSWFはしばなしばしば51%の順位を返し、49%のグループを代表することに失敗する。本論文は、すべての入力順位がその重みに比例して出力に影響を与えることを保証する、比例代表制を満たすSWFを設計することを目指している。

方法論およびフレームワーク

著者らは、入力順位 $\succ$ の出力順位 $\triangleright$ に対する**効用（utility）**を、それらの間のペアワイズな一致（pairwise agreement）の数として定式化することで、比例性を定義している：
$$u(\succ, \triangleright) = |\{(x, y) \in C^2 : x \succ y \text{ and } x \triangleright y\}|$$
$m$ 個の候補がある場合、総ペア比較数は $\binom{m}{2}$ であるため、重み $\alpha$ を持つ入力順位は、理想的には少なくとも $\lfloor \alpha \binom{m}{2} \rfloor$ の効用を得るべきである。

本論文は、**承認ベースの委員会投票（approval-based committee voting）および参加型予算編成（participatory budgeting）**に着想を得た、比例性の階層的な公理を導入している：

1. 一様正当代表性 (uJR): 最も弱い要件であり、重みが $\ge 1/\binom{m}{2}$ である入力順位が、少なくとも1つのペアワイズな一致を得ることを要求する。
2. 一様比例正当代表性 (uPJR): コアとなる公理であり、重み $\alpha$ を持つ入力順位が、少なくとも $\lfloor \alpha \binom{m}{2} \rfloor$ の効用を得ることを要求する。
3. 強一様比例正当代表性 (sPJR): グループへの保証を拡張した強化版である。サブプロファイル $S$ が総重み $\alpha$ を持つ場合、出力は $S$ に含まれる順位の連合と、少なくとも $\lfloor \alpha \binom{m}{2} \rfloor$ のペアワイズな比較で一致しなければならない。

これらの公理を実現するために、著者らは参加型予算編成における**価格設定可能性（priceability）**の概念を応用している。彼らは、出力順位の構築を、入力順位の予算を使用して候補（または候補のペア）を「購入」していく逐次的な購入プロセスとしてモデル化している。

主要な貢献と結果

1. 既存手法の限界

本論文はまず、比例的ランキングのために提案された二乗ケメニー・ルール（Squared Kemeny rule）（Lederer et al. [2024]）を分析している。著者らは、$m \ge 5$ の場合、二乗ケメニー・ルールが最も弱い公理である uJR さえも満たさないことを証明している。具体的には、かなりの重みを持つ入力順位が、二乗ケメニー・ルールの出力からゼロの効用しか得られないプロファイルを構築し、新しいメカニズムの必要性を実証している。

2. 比例的逐次ボルダ・ルール (PSB)

uPJR を満たすために、著者らは比例的逐次ボルダ・ルール (Proportional Sequential Borda rule: PSB) を提案している。

• メカニズム: PSB は逐次的に動作する。各ラウンドにおいて、現在の予算に基づいた加重ボルダ・スコアを最大化する候補を選択する。その後、選択された候補の配置に対する貢献度に応じて、入力順位の予算を比例的に更新し、実質的にその候補の配置に対して「支払い」を行う。
• 理論的保証: 著者らは、参加型予算編成における価格設定可能性を反映した、**ランク価格設定可能性（rank-priceability）**という構造化された公理を導入している。彼らは、ランク価格設定可能性が uPJ R を含意することを証明している。
• 結果: 定理 4.5 は、PSB がランク価格設定可能性を満たし、その結果 uPJR を満たすことを確立している。
• 定量的保証: 公理の充足を超えて、定理 4.6 は PSB がすべてのサブプロファイル $S$ に対して、少なくとも $\frac{|S|}{4}\binom{m}{2} - \frac{3}{16}$ の平均効用を保証することを証明している。これは、グループの重みに対する効用の線形下限を提供している。

3. フロー調整ボルダ・ルール (FB)

著者らは、PSB の支払いスキームが、連携して行動する順位のグループを十分に保護できないため、PSB が sPJR に失敗することを示している。これを解決するために、彼らは、単なるランクではなく特定の候補のペアに対して支払いを行う、より洗練された公理である**ペア価格設定可能性（pair-priceability）**を導入している。

• メカニズム: フロー調整ボルダ・ルール (Flow-adjusting Borda rule: FB) は、PSB の改良版である。PSB と同様に、FB も逐次的にボルダ勝者を決定する。しかし、単純な比例支払いではなく、FB は構築されたネットワークにおける**最大流問題（maximum flow problem）**を解くことによって支払額を決定する。このネットワークは、予算制約とペアワイズの制約を遵守しながら、効用あたりのコスト比が最小化されるように設計されている。
• 結果: 定理 5.5 は、FB がペア価格設定可能性を満たすことを証明しており、これは sPJR（定理 5.3）を含意する。
• 定量的保証: 定理 5.6 は、FB が PSB と同様の線形平均効量保証（$\frac{|S|}{4}\binom{m}{2} - \frac{3}{16}$）を提供し、個人とグループの両方に対して強力な公平性を確保することを示している。

4. その他のバリアント

付録では、著者らは参加型予算編成の等分法（Method of Equal Shares: MES）に着想を得たバリアントである、ランク等分法 (Ranked Method of Equal Shares: RMES) について論じている。彼らは、RMES がランク価格設定可能性を満たし（したがって uPJR を満たし）、初期のボルダ・スコアに基づいて最初の $\lfloor m/4 \rfloor$ 個の候補を純粋に選択するという、わずかに異なる功利主義的プロファイルを提供することを示している。

意義と主張

本論文は、順位集計における真に比例的な社会厚生関数を提示したと主張している。その主な意義は以下の通りである：

• 分野の架け橋: 承認ベースの委員会投票および参加型予算編成（特に PJR と価格設定可能性）の深い成果を、順位集計の領域へと見事に転移させたこと。
• 未解決問題の解決: 二乗ケメニーのような従来の試みが達成できなかった、uPJR および sPJR を満たす SWF の設計という未解決問題を解決したこと。
• 公理的および定量的な強固さ: 提案されたルール（PSB および FB）は、強力な公理的公平条件を満たすだけでなく、いかなる投票者グループに対しても平均効用の堅牢な定量的保証を提供し、少数派の好意が体系的に無視されないことを保証している。

著者らは、自身の研究がペアワイズの一致を効力の指標としているが、これは文献における標準的なアプローチであると述べている。また、今後の展望として、より強い公平性の概念（EJR やコア安定性など）や、異なるランキング位置の価値を考慮した、より一般的な効用関数を探求できる可能性を示唆している。