【ITニュース解説】Tideman Voting Algorithm: A Graph-Based Approach to Elections

Tidemanアルゴリズムは、選挙の勝者を決定するための高度な投票システムである。これは「ランク付きペア」とも呼ばれ、単なる多数決方式では捉えきれない、有権者のより詳細な意図を、グラフ理論という数学の考え方を使って理解しようとするものだ。Tidemanアルゴリズムがどのようにグラフ理論を応用し、どのように動作するのか、その主要な仕組みを解説する。

Tidemanアルゴリズムの根本にあるのは、選挙を有向グラフとして表現する点である。ここで「有向グラフ」とは、点と、その点を矢印で結んだ線の集まりを指す。このグラフにおいて、各候補者は「ノード」（点）として表され、ある候補者が別の候補者よりも優先されるという関係は「エッジ」（矢印の線）として表現される。例えば、「候補者Aが候補者Bより優先される」という関係は、AからBへ向かう矢印として描かれる。 このアプローチは、候補者間の優先度が確定した際に「隣接行列」という表に記録される。隣接行列は、表の縦と横に候補者を並べ、ある候補者が別の候補者より優先される場合に「真」（true）を、そうでない場合に「偽」（false）を記入する形で、確定した優先度、つまりロックされたエッジを示すものだ。例えば、隣接行列で「候補者0が候補者1より優先される」、「候補者2が候補者0より優先される」、「候補者2が候補者1より優先される」といった情報が記録され、これら一つ一つのロックされた優先度が集まって、最終的な勝者を決定するグラフが形成されることになる。

有権者の投票データを扱うために、Tidemanアルゴリズムでは二つの重要なデータ構造を用いる。一つは「プリファレンス配列」で、これはどの候補者が他のどの候補者よりも多くの有権者から支持されたかを数値で記録するものだ。具体的には、preferences[i][j]という形式で、候補者iが候補者jよりも多くの有権者から優先された人数を示す。例えば、候補者が3人（0, 1, 2）いる場合、preferences[0][1]が5であれば、5人の有権者が候補者0を候補者1よりも優先した、という意味になる。自分自身と比較することはないため、配列の対角線上のセルは常に空となる。 もう一つは「ランク配列」で、これは個々の有権者がどのような順番で候補者を優先したかを詳細に記録する。この配列では、インデックスが優先順位（0が最も高い優先度）を表し、その値が候補者のIDを表す。例えば、ある有権者がボブ（候補者1）を最も好み、次にアリス（候補者0）、デイビッド（候補者3）、最後にチャーリー（候補者2）を選んだ場合、その有権者のランク配列はranks[0]=1, ranks[1]=0, ranks[2]=3, ranks[3]=2となる。これは、最も高い優先度（ランク0）で候補者1（ボブ）を選び、次に高い優先度（ランク1）で候補者0（アリス）を選んだことを意味する。

すべての投票データが収集され、プリファレンス配列やランク配列によって整理された後、アルゴリズムは「ペア」を作成する。このペアは、ある候補者が別の候補者よりも優先される関係を示すものだ。例えば、「(候補者A, 候補者B)」というペアは、候補者Aが候補者Bよりも優先されたことを意味する。 これらのペアは、単に存在するだけでなく、その「優位性の強さ」によってソートされる。優位性の強さとは、ある候補者が別の候補者に対してどれだけ多くの票差で勝ったか、つまりどれだけ多くの有権者がその優先関係を選んだかを示す数値だ。例えば、候補者Aが候補者Bに5票差で勝った場合と、候補者Cが候補者Dに10票差で勝った場合では、後者の方が優位性の強さが大きいと判断される。Tidemanアルゴリズムでは、このソートを効率的に行うために「マージソート」のようなアルゴリズムが使われる。これは、最も強い優位性を持つペアから順に最終的なグラフに組み込んでいくための重要なステップである。

Tidemanアルゴリズムの中心となるのは、「lock_pairs関数」である。この関数は、ソートされたペアの中から、実際に最終的なグラフに組み込む（ロックする）ペアを決定する役割を担う。ここで最も重要なのは、ロックするペアによってグラフ内に「サイクル」が生成されるのを防ぐことだ。「サイクル」とは、グラフの矢印をたどっていくと、出発点となった候補者に戻ってきてしまう状態を指す。例えば、「A → B → C → A」のような関係はサイクルである。このようなサイクルがあると、誰が最終的に勝者であるかを明確に特定できなくなってしまうため、アルゴリズムはサイクルを回避するように設計されている。 サイクルを検出する方法はいくつかあるが、最も一般的なのは、あるペアをロックしようとしたときに、それによって既存のグラフにサイクルが生まれるかどうかを調べるというものだ。もしサイクルが生成されるのであれば、そのペアはロックしない。 具体的な例で考えてみよう。候補者がA, B, C, Dの4人いて、優位性の強い順に並んだペアが[(D, A), (A, B), (B, C), (C, A), (D, B), (D, C)]だと仮定する。 まず、最も強いペア(D, A)をロックする。この時点では他にロックされたペアはないため、サイクルは発生しない。グラフは「D → A」となる。 次にペア(A, B)をロックする。これもサイクルを生成しないため、「D → A → B」となる。 さらにペア(B, C)をロックする。これもサイクルを生成しないため、「D → A → B → C」となる。 ここで、ペア(C, A)を考える。もしこのペアをロックすると、「C → A」というエッジが追加され、「A → B → C → A」というサイクルができてしまう。そのため、ペア(C, A)はロックしない。 次にペア(D, B)をロックする。これによりサイクルは生成されないので、「D → B」というエッジが追加される。 最後にペア(D, C)をロックする。これもサイクルを生成しないので、「D → C」というエッジが追加される。 このようにして、サイクルを避けるように注意深くペアをロックしていくことで、最終的に明確な勝者を導き出せるグラフが構築される。

すべての有効なペアがロックされ、サイクルを含まない最終的なグラフが完成した後、勝者を特定する。勝者は、この最終グラフにおいて「入ってくるエッジが一つもない候補者」である。つまり、他のどの候補者からも矢印が向かっていない候補者が勝者となる。この候補者は、ロックされた優先度に基づいて、どの候補者にも負けていないと判断されるため、「ソース」（源）と呼ばれることもある。 上記の例では、最終的に候補者Dには入ってくるエッジがない。候補者Dは候補者A, B, Cのすべてに優先されているが、他の候補者からDへ向かう優先関係は存在しない。したがって、候補者Dが選挙の勝者となる。

Tidemanアルゴリズムは、投票理論におけるいくつかの難しい課題を巧みに解決する。例えば、複数の候補者がいる中で「コンドルセ勝者」が存在する場合、Tidemanアルゴリズムはそのコンドルセ勝者を必ず見つけ出すことができる。コンドルセ勝者とは、他のすべての候補者と一対一で対決した場合に、必ず勝つことができる候補者のことである。コンドルセ勝者が存在しない場合でも、Tidemanアルゴリズムは合理的な近似解を提供する。 また、このアルゴリズムは「無関係な代替案からの独立性」（Independence of Irrelevant Alternatives）という基準を、他の多くの投票システムよりも良く満たす傾向がある。これは、ある候補者に対する有権者の評価が、無関係な第三の候補者が選挙に出るか出ないかによって変わるべきではない、という考え方である。 Tidemanアルゴリズムは、グラフ理論を用いて有権者の優先度を多角的に表現することで、単純な多数決方式よりも、選挙結果のより完全で複雑な全体像を描き出すことができる。このアルゴリズムの理論的基盤、すなわちプリファレンス配列やランク配列による情報の記録、サイクル検出、そして勝者の決定に至るまでの理解は、現代の投票システムがいかにして有権者の意図をより正確に捉え、公平な選挙結果を生み出すかを深く洞察させてくれるものだ。これは、複雑な情報を構造化し、論理的な手順で問題を解決するシステムエンジニアリングの考え方と深く結びついていると言えるだろう。