Metric Distortion of Social Welfare Functions

意思決定の世界において、新しい従業員の採用からグループでの映画選びに至るまで、私たちはしばしば人々に好みの順位付けを頼みます。「誰が一番好きですか？」や「あなたのトップの選択肢は何ですか？」と問いかけ、それらの答えを用いて集団的な決定を下します。数十年にわたり、研究者たちは、人々が各選択肢をどれほど正確に価値付けしているのかが分からない場合、これらのランキングがどれほど優れた結果に結びつくかを研究してきました。彼らは、個人の感情の正確な強さを知らなくても、単に好みの順序を知っているだけで、驚くほど公平な結果を導き出せることを発見しました。しかし、こうした研究の多くは、大統領や最良の候補者のような「一人の勝者」を選ぶことに焦点を当てていました。現実の世界はもっと複雑です。私たちは頻繁に、大学の合格待ちリストや製品の推奨フィードのように、全員を最初から最後までの完全なリストとして作成する必要があります。このようなシナリオでは、順位が重要になります。1位になることは極めて重要かもしれませんが、10位になることは最後になるのとほとんど変わらないかもしれません。ここで問題となるのは、もし人々が順序の好みは知っているものの、1位と2位の差をどれほど重視しているかを知らない場合、どのようにすれば全員を満足させる完全なリストを作成できるか、ということです。

研究チームは現在、この特定の課題に取り組み、投票者が異なる位置に対して異なる重要度を持つ場合に、完全なランキングを構築する方法を探求しています。彼らは、すべての人が隠れた価値の尺度を持っており、トップの枠とボトムの枠をどれほど重視するかを決定しているシナリオを想定しました。ある人は最初の推奨事項だけにこだわり、またある人は適切なものを見つけるために、いくつかの選択肢を閲覧することに抵抗がないかもしれません。研究者たちは、投票システムがこれらの隠れた尺度を見ることなく、公平で高品質なランキングを作成できるかどうかを知りたいと考えました。彼らは、その答えはシステムがどのような情報を使用することを許可されているかに完全に依存するということを発見しました。もしシステムが各ポジションの価値を正確に知っていれば、最適な歪み（distortion）である3を達成し、最高の品質のランキングを構築できます。もしシステムが価値を知らないものの、全員が同じ隠れた尺度を共有していることを知っていれば、結果の品質は共有された尺度がどの程度変化するかによって決まりますが、依然として非常に優れた成果を上げることができます。

最も困難な状況は、システムが重みについて何も知らず、すべての人が独自の隠れた尺度を持っている場合に発生します。この場合、研究者たちは、いかに巧妙な投票ルールであっても、候補者の数が増えるにつれて、ランキングの品質は必然的に低下することを証明しました。彼らは、結果のエラーがランキングされる候補者の数に対して線形に増大することを示しました。簡単に言えば、少数のグループをランク付けする場合、システムはまともなことができますが、多数の候補者をランク付けする場合、人々が特定のポジションをどれほど重視しているかという情報の欠如により、良い結果を保証することは不可能になります。この発見は、根本的な限界を浮き彫りにしています。投票者がリストの異なる位置をどのように重み付けしているかを知らなければ、完璧なランキングは手の届かないところにあるのです。

研究者たちは、これらのランキングを作成するためのステップバイステップの手法を構築することで、自分たちのアイデアをテストしました。リストを上から一つずつ埋めていくプロセスを想像してください。各ステップにおいて、システムは現在の好みに基づいて、その特定のポジションに最適な利用可能な候補者を選びます。彼らは、もしシステムが重みを知っていれば、この単純なステップバイステップのアプローチが最適に機能し、最適な歪みである3を達成することを発見しました。彼らは、各ステップで勝者を選ぶための特定の洗練された手法を用いており、これにより、最終的なリストが制約条件下での理論上のベストリストと同等であることを証明できました。これは、完全なリストを作成することは、システムが適切な情報を持っている限り、単一の勝者を選ぶ場合と比較して品質を犠牲にする必要がないことを示したため、重要な発見でした。

重みが隠されているものの全員で共有されている場合、研究者たちは、同じステップバイステップの手法が依然として機能するものの、結果の品質は共有された尺度の形状に基づいて変化することを発見しました。もし全員がすべてのポジションをほぼ同じように価値付けているなら、システムは歪み1、つまり結果が最適な社会的厚生（social welfare）と完全に一致する状態で機能します。もし全員がトップのポジションのみを重視する場合、システムは単一の勝者を選ぶ場合と全く同じように機能します。パフォーマンスはこれら2つの極端なケースの間を滑らかに移動します。これは、具体的な数値を知らなくても、グループがリストに対する考え方において均一であれば、システムは依然として非常に効果的なランキングを作成できることを意味します。研究者たちは、このパフォーマンスに関する正確な公式を提供し、グループの価値の変動が最終的な結果にどのように影響するかを正確に示しました。

しかし、重みが隠されており、かつ人ごとに異なる場合は、物語は完全に変わります。研究者たちは、この混沌とした環境において、システムは品質の大幅な損失を避けることができないことを実証しました。彼らは、重みを知らない投票ルールが生成できるものよりも、最高のランキングが遥かに優れている具体的な例を構築しました。彼らは、最適な結果と実際の結果との差が、候補者の数に直接比例して増大することを証明しました。10人の候補者のリストであればエラーは小さいですが、100人のリストであればエラーははるかに大きくなります。この結果は、より多くの情報なしに巧妙なアルゴリズムで問題を解決できるという期待を否定するものです。これは、大規模なグループに対して高品質なランキングを得るためには、人々がポジションをどのように重み付けしているかを知るか、あるいは結果が不完全であることを受け入れるかのどちらかが必要であるという、明確な境界線を設定しています。

研究はまた、人々が値を正規化する2つの異なる方法についても調査しました。一つのシナリオでは、全員が全リストに対して固定された総価値を分配します（例えば、1ドルをすべてのポジションに分割するように）。もう一つのシナリオでは、全員が他のポジションをどのように価値付けするかに関わらず、トップのポジションに固定された値「1」を与えます。研究者たちは、これら両方の現実的なシナリオにおいて、隠された異なる重みの問題が同じ線形なエラーの増加をもたらすことを発見しました。投票者が内部的な尺度をどのように構成しようとも、もしシステムがそれらを見ることができず、かつそれらが人によって異なるのであれば、ランキングの品質はリストが長くなるにつれて低下します。これは、レコメンデーションシステムの設計者や採用委員会に対して明確な警告を与えています。もし多様な優先順程を持つグループを扱っている場合、より具体的な好みのデータを収集することなしに、単純なランキング手法で完璧なリストを作成できるとは考えられないのです。

結局のところ、この研究は、限られた情報で達成できることの限界を明らかにしています。それは、良い集団的決定への道は、利用可能な情報の構造に大きく依存していることを示しています。重みを知っていれば、最適な歪み3を達成できます。重みが全員で共通していることを知っていれば、重みが均一であれば歪み1を、変動に応じて1と単一勝者バウンドの間を補間する結果を達成できます。しかし、重みが隠されており、かつ人ごとに異なる場合、私たちはグループの規模が結果の品質を決定するという壁に突き当たります。研究者たちは単に新しい投票方法を提案したのではなく、何が可能であるかの境界線をマッピングし、情報が欠落したときに公平性と効率性のルールがどこで崩壊するかを正確に示したのです。彼らの知見は、好みを完全なランキングへと集約しようとするあらゆる人に対し、扱う対象の多様性がタスクの複雑さを増大させるということを思い出させる実用的なガイドを提供しています。