ウェブ検索ランキングにおける投票モデルについての簡単な説明

数日前、「選挙のジレンマ」という本を読みました。ある章では、アメリカの選挙制度から始まり、アメリカの選挙制度の欠点を紹介し、その欠点に基づいてさまざまな改善を提案しています。しかし、それぞれの改善には独自の問題があり、その変化は非常に興味深いものです。

まず、米国の選挙制度についてお話ししましょう。米国大統領選挙は「勝者総取り」方式です。各州には、人口に応じて数十から数百の「州票」があります。州民が大統領候補者を選出します。州内で最も多くの票を獲得した候補者は、その州のすべての「州票」を獲得します。その後、すべての候補者の「州票」が集計され、「州票」が最も多い候補者が勝利します。

このようなシステムの問題は明らかです。たとえば、州が 2 つしかなく、州 A に 5 人の候補者、州 B に 4 人の候補者がいて、各州の投票がそれぞれ 5 と 4 だった場合、候補者 X が州 A で 3:2 のスコアで勝利し、候補者 Y が州 B で 4:0 のスコアで勝利した場合、候補者 Y が全国で 6 票を獲得し、候補者 X が州 A で獲得したのは 3 票だけであることは明らかです。しかし、「勝者総取り」システムのため、X は A 週に 5 つの「州票」すべてを獲得し、Y は B 週に 4 つの「州票」しか獲得しませんでした。全国の 1/3 の支持しか受けなかった X が、実際に選挙に勝利したことになります。

この状況は、2000年の米国大統領選挙で起こった。ブッシュ・ジュニアは州投票ではゴアを上回っていたが、全国的にゴアを支持する人の数はブッシュを上回っていた。もちろん、ゴアがブッシュ・ジュニアに負けた理由は他にもあるが、ここでは触れない。

これをアルゴリズムの分野に当てはめると、ここでの問題は、結果 R (最も適した大統領候補) を計算するために特徴 A (各国民の投票) が求められるものの、結果 R を決定するのは特徴 A ではなく、特徴 A から導出された特徴 B (各州の投票) であるということがわかります。特徴 B から特徴 A を導出する過程で、情報が失われます (各州の支持率は異なります)。

「勝者総取り」システムの具体的な歴史的理由については触れずに、興味のある友人は原作を読むことができます。この問題の最も直接的な解決策は、「勝者総取り」方式から「一人一票」の直接選挙方式に変更し、直接投票を数えることです。しかし、これにも一連の問題が生じます。

一連の問題について議論する前に、まず解決すべき問題を抽象化してみましょう。

候補者は n 人おり、各有権者はこれらの n 人の候補者に投票し、最終的に n 人の候補者の中から最も適切で、最も世論に沿っており、最も論理的な候補者を選択します。

オプション 1: 1 票制。各人が 1 票を持ち、好きな候補者を選びます。結果が集計され、最も多くの票を獲得した人が選出されます。

これを行うことの問題は、著者が「乱闘」と定義する状況につながることです。たとえば、ABC と BC の 3 人の候補者がいて、彼らの政治的見解が似ている場合、B を支持する人々は C も支持する傾向があり、その逆も同様です。人口全体の中で、大多数の人々は BC を好みますが、A の政治的見解は BC と反対であり、A を支持する人々は少数派です。その結果、BC が獲得した票はより分散され、A が獲得した票はより集中して勝利することになります。BC のいずれかが選挙に参加しない場合、票は B または C のみに集中し、その結果、有権者の過半数の支持者が当選することになります。上記で触れられていないゴア敗北のもう一つの理由は、ゴアと似た政治的見解を持つネッドが関与し、ゴアの票の一部を分割したと信じる人々がいたことだ。

この問題を改善できる解決策は「二選制」と呼ばれています。

オプション 2: 2 回の選挙制度、1 人 1 票。50% 以上の支持を得た候補者がいない場合は、最も得票数の多い 2 人の候補者が選出され、もう一度選挙が行われます。最も得票数の多い候補者が勝者となります。

フランス大統領選挙はこのような二選制であるが、この方式では「シギとアサリのジレンマ」を改善することはできても、完全に解決することはできない。2002年のフランス大統領選挙でも同様の事態が発生した。当時は左派政治を支持する人の方が多かった。しかし、二選制では最終的にトップ2は右派と極右派となった。この状況の原因は、その年の大統領候補が16人おり、そのほとんどが左翼的な考えを持っていたため、左翼への票が極端に分散したためである。

オプション 3: n 選挙システム、1 人 1 票。50% 以上の支持を得た候補者がいない場合は、最も支持の少ない候補者が排除され、別の投票ラウンドが行われます。それでも 50% 以上の支持を得た候補者がいない場合は、50% 以上の支持を得た候補者が現れるまで、最も票数の少ない候補者が再び排除されます。

2001年にIOCが2008年オリンピックの開催都市を北京に決めたときもこの方式が採用された。大阪は第1回投票で敗退し、第2回投票で北京が過半数の支持を得て選出された。

n 選挙制度の問題点は、実用的ではないことです。オリンピック委員会のように、数百人しか投票しないような状況では使用できます。しかし、候補者が 16 人いるフランス大統領選挙のような場合、国は最大で 15 回しか投票できない可能性があり、コストがかかりすぎます。

オプション 4: 即時複数選挙制度。各市民が候補者を順位付けします。候補者が第一候補の 50% 以上を獲得した場合、その候補者が直接当選します。そうでない場合、得票数が最も少ない候補者が排除され、得票数が最も少ない 2 番目の候補者が取り出されて、対応する候補者に分配されます。誰かが 50% 以上を獲得した場合、その候補者が当選します。そうでない場合、最下位の候補者が排除され、その候補者の票は排除されていない最高位の候補者に分配されます。

アイルランド大統領選やロンドン市長選でも同様の計画が採用されているが、これにも問題がある。次のようなシナリオを想像してみてほしい。有権者が10人いて、中道派の候補者が3人のうち第一候補、左翼と右翼の候補者がそれぞれ4人のうち第一候補だ。もちろん、左翼の有権者は右翼の候補者を最も嫌っており、右翼の有権者も左翼の候補者を最も嫌っているが、中道派の候補者は左翼と右翼の両方の人々から受け入れられる。多肢選択方式であろうとn択方式であろうと、中道派の候補者は第1ラウンドで脱落することになる。中道派の候補者は、すべての国民に受け入れられ、派閥間の対立を最もうまく調整し、最も調和のとれた人物である。

この計画の根本的な問題は、各有権者が候補者を順位付けできるにもかかわらず、第 1 ラウンドで考慮されるのは最初の選択肢のみであり、有権者の第 2 選択肢と第 3 選択肢は考慮されないことです。

オプション 5: 上向きの複数選挙制度。オプション 4 と同様ですが、第 1 ラウンドで、最も支持の少ない候補者ではなく、最も反対の候補者 (最終投票数が最も多い候補者) が排除されます。

上記の状況を見ると、中道派の候補者は誰にとっても最後の選択肢ではないため、左派や右派は第 1 回投票で脱落します。第 2 回投票では、中道派の候補者が勝利する可能性があります。

プラン 5 にも独自の問題があります。選挙に立候補している候補者が AB の 2 人だけで、有権者が 9 人いて、そのうち 6 人が A を好み B を嫌い、3 人が B を好み A を嫌っているという状況を考えてみましょう。前述のどの方法を使用しても、A が勝利します。しかし、今では候補者は C と D の 2 人しかいません。B を好む 3 人全員が A を最後の候補者として挙げており、A を好む 6 人の最終的な選択は、それぞれ 2 票の BCD です。このように、第 1 ラウンドの選挙では、最終投票数が最も多かったため A が排除され、注意深く構築された例により、最終的に B が選出されることになります。 CDが選挙に参加するか参加しないかというだけで、AとBの勝ち負けの関係が逆転してしまいます。

この計画が実際に使用された例は多くありません。紀元前 507 年のアテネでのみ、同様の計画がありましたが、この計画では、人々は賛成票ではなく反対票を投じることができ、最も反対した人々は投票で排除されました。

オプション 6: 複数ラウンド方式。一般の人が候補者をランク付けし、その後、候補者がペアになって互いに競います。各投票を数えて、候補者 A が候補者 B より上か、候補者 B が候補者 A より上かを確認します。このようにして、最も多くの勝利を得た候補者が選挙に勝利します。

このような問題は、勝ち負けのサイクルを引き起こす可能性があります。たとえば、3 人の候補者 ABC と 3 人の人がいます。投票はそれぞれ ABC、BCA、CAB です。AB の間では、A が 2 回勝利し、A>B であり、BC の間では、B が 2 回勝利し、B>C であり、AC の間では、C が 2 回勝利し、C>A であることがわかります。これは、A>B>C のサイクルを構成します。これはサッカーリーグの得点システムに少し似ていませんか? 得点が同じ場合、サッカーの試合ではゴール差、ゴール、勝敗記録などを見ることができます。ただし、著者はこの側面について詳しく述べず、別の方法、ボダシステムを紹介しました。

オプション 7: 一般の人が候補者をランク付けするブロード システム。候補者が n 人いる場合は、最初の候補者は n ポイント、2 番目の候補者は n-1 ポイントというように順位が付けられます。各候補者の合計得点が計算され、最も得点の高い候補者が勝者となります。

一部の有権者がこの方法を使って不正行為をする（「戦略的投票」をする）可能性があるという理由で、ブロード システムを批判する人もいます。B を最も支持する候補者は、当初は B>A>C という順位を念頭に置いていますが、それでも B を A より好むため、B を上げるには A を下げる必要があり、彼らの投票は B>C>A になります。ボルダ氏はこの批判に対し、「私のシステムは正直な有権者にのみ有効だ」と答えた。

しかし、この本の著者は、ブロードシステムにおける「戦略投票」の問題はそれほど深刻ではないと考えている。世論を正確に予測し、戦略投票の方法を正確に制御できない場合、過度の力によってAが引きずり下ろされるだけでなく、Cがより多くの票を獲得する可能性があります。このように、Bを最も支持する人々の「戦略投票」によって、彼らが最も嫌っているCが選出されることになります。その年、IMDBでも同様のシーンがありました。

映画「バットマン6」が公開された後、バットマンファンはこの映画がとてもクールだと思ったので、IMDBでバットマン6を1位に投票したかったので、バットマン6に必死に高いスコアを付け、同時に、当時IMDBで1位だった「ゴッドファーザー」に低いスコアも投票しました。結果は、彼らが頑張りすぎたため、「ゴッドファーザー」が3位になり、元の2位である「ショーシャンクの空に」（TSR）が2位になりました（元の2位は「ゴッドファーザー」の後ろで、新しい2位はバットマン6の後ろです）。その後、狂ったファンの熱狂が薄れるにつれて、合理的な意見が優勢になり、バットマン6のスコアは徐々に低下し、10位に落ちました。ゴッドファーザーはまだ『ショーシャンクの空に』の撮影中であり、長い間戻ってきませんでした。

Boda システムに他に問題はありますか?

上記は本書の第 14 章に関するメモに過ぎず、「単一ポジションに複数の候補者がいる」という問題についてのみ説明しています。本書では、「複数のポジションに複数の候補者がいる」という状況、つまり各人の候補者の順位付けに基づいて最終的な候補者の順位を決定するという状況について引き続き検討します。

検索エンジンの分野に戻ると、上記の戦略的な変更は私たちにインスピレーションを与えてくれるでしょう。まず、先ほど抽象化した問題を見てみましょう。

候補者は n 人おり、各有権者はこれらの n 人の候補者に投票し、最終的に n 人の候補者の中から最も適切で、最も世論に沿っており、最も論理的な候補者を選択します。

これは、検索エンジンが解決する問題とよく似ています。

システムには n 個の Web ページがあり、m 個の機能 (ページの品質、ページ コンテンツの豊富さ、ページのハイパーリンク、テキストの関連性など) によって n 個の Web ページに異なるスコアが与えられます。これらの機能の「投票」に基づいて、最初に配置される最も適切な Web ページを選択するにはどうすればよいでしょうか。

選挙の例から、いくつかの教訓を引き出すことができます。

1. アルゴリズムを設計するときは、「勝者総取り」戦略によって引き起こされる情報損失の問題を回避します。

2. いくつかの優れた機能があるという理由で Web ページをトップにランク付けしたり、いくつかの悪い機能があるという理由で Web ページを破棄したりしないでください。

3. 最初に配置するのに最も適した Web ページは、必ずしもすべての機能において最高である必要はなく、すべての機能を考慮し、全体的なパフォーマンスが最も優れている Web ページである必要があります。

4. 検索エンジンの利用者の検索結果に対するクリック行動は、検索結果に対する「投票」とみなすことができます。このような「投票」情報を利用する場合、選挙プロセスにおいてさまざまな不合理な事態を招かないかどうかも考慮する必要があります。

上で述べたさまざまな選挙制度は、「1 つのポジションに複数の候補者がいる」という状況についてのみ議論していますが、検索エンジンが直面している問題は、「複数の候補者のランキング」という状況に似ています。

システムには n 個の Web ページがあり、m 個の機能 (ページの品質、ページ コンテンツの豊富さ、ページのハイパーリンク、テキストの関連性など) によって n 個の Web ページに異なるスコアが与えられます。これらの機能の「投票」に基づいて n 個の Web ページの順序を決定するにはどうすればよいでしょうか。

この「複数候補者の順位付け」問題に対して、「不可能な民主主義」という理論があります。この理論では、「合理的な」民主主義は、次の 3 つの条件を満たす必要があるとされています。

1. 投票者全員が A が B より優れていると考える場合、最終結果も A が B より優れているということになります。

2. 「**er」は存在しない、つまり、そのような人は存在せず、他の人がどのような順位をつけても、最終結果はこの人の順位と同じになる

3. 無関係な要因の独立性、つまり、最初の投票の後、A は B より上位にランクされます。次に、2 回目の投票が行われます。誰も投票で A と B の相対的な順序を変更しない場合、最終結果も A が B より上位になるはずです。

数学的証明により、ある選挙方法が条件 1 と 3 を満たす場合、条件 2 は満たされてはならない、つまり「**ers」が存在するはずであると結論付けることができます。この問題の証明については、こちらのブログを参照してください: http://roba.rushcj.com/?p=509

「不可能な民主主義」理論によれば、検索エンジンと組み合わせると、検索エンジンがウェブページに合理的なランキングを与えることは困難であると思われます。しかし、検索エンジンと投票は違うようです。それを打破するには2つの角度があります。

1. 条件 3 は強すぎるため、弱める必要があると考えます。

2. ウェブページのランキングの問題には、本当にそのような「**機能」があるのか​​もしれません。現在の視点から見ると、最も適切な「**機能」は「ユーザー満足度」であるはずです。ユーザー満足度に従ってウェブページを並べ替えることが、最も合理的なウェブページのランキングです。 「ユーザー満足度」をどうやって測定するか？これが私たちが取り組んでいることです。

liangailiによる

原題: ウェブ検索ランキングにおける投票モデルに関する簡単な説明

キーワード: 簡単な議論、ウェブページ、検索ランキング、順番、投票、モデル、数日前、本、選挙の難しさ、ウェブマスター、ウェブサイト、ウェブサイトの宣伝、金儲け