区間選挙におけるTieleルールの計算とその一般化
要約
この論文は、承認投票に基づく委員会選択システムのTieleルール（特に比例承認投票PAV）の計算複雑性問題を扱っている。Tieleルールは比例代表制、パレート最適性、サポート単調性といった望ましい性質を持つが、一般的にはNP困難な計算問題である。候補者区間（CI）ドメインでは線形プログラムにより多項式時間で解けることが知られていたが、関連する有権者区間（VI）ドメインでの計算複雑性は長年の未解決問題だった。本研究では、VIドメインにおいて標準的な線形プログラムが少なくとも1つの最適整数解を持つことを証明し、それを高速で見つけるアルゴリズムを提供した。さらに、この手法を有権者-候補者区間（VCI）ドメインと線形一貫性（LC）ドメインに拡張し、グラフ理論を用いてLCがVCIを厳密に含むことを示した。最後に、VCIの樹ベース一般化を検討し、この場合にはTieleルールの計算が再びNP困難になることを明らかにした。
洞察・気づき
この研究は投票理論における重要な理論的進歩を示している。民主的な意思決定システム、特に比例代表制を実現する投票方式の設計において、計算効率は実用性の観点で極めて重要である。本研究により、特定の構造を持つ選好プロファイル（有権者区間ドメイン）において、理想的な投票結果を効率的に計算できることが明らかになった。これは電子投票システムや大規模な委員会選出、オンライン意思決定プラットフォームなどの実装において重要な意味を持つ。また、異なるドメイン間の関係性の解明は、投票理論の体系的理解を深めるとともに、実際の選挙制度設計において適用可能な範囲を明確にしている。