社会選択理論と投票アルゴリズム

社会選択理論（Social Choice Theory）

社会選択理論が扱うのは、集団の中の一人ひとりの好みをどうまとめれば、全体の意志を代表する集団的決定になるのか、という問題です。

数学の言葉で言うと、ある制度やアルゴリズム（関数 $F(X, P)$ ）を見つけることです。

入力は選択肢 $X = \{A, B, C, D, \dots\}$ と各個人の好み $P = (P_1, P_2, \dots, P_n)$ で、

\begin{aligned} P_1 &= \{(A \succ B), (C \succ D), \dots\} \\ P_2 &= \{(C \succ A), (D \succ B), \dots\} \\ &\;\;\vdots \end{aligned}

出力が「全体の意志を代表する」ようにします。

F^* = \arg\max_{F \in \mathcal{F}} G(F)

ここで $\mathcal{F}$ はあり得るすべての制度、 $G$ はある制度が「どれだけ全体の意志を代表しているか」を測るものです。

もうお気づきかもしれませんが、全体の意志を代表するとはどういうこと??

定義は何なのか、そもそもそんなものは存在するのか。誰もがよく知っているつもりのこの概念は、実際にはかなり扱いにくいものです。

汎用的で明確な定義は示せませんが、先に結論を挙げてから、一つずつ説明していきます。

全体の意志は存在するのか	理論	現実
選択肢が 2 つ	存在する	存在しない
選択肢が 3 つ以上	存在は保証されない	存在しない

先に進む前に補足すると、社会選択理論は主に数学と経済学の言葉を使いますが、複数人の意思決定が関わるほぼすべての問題に応用できます。たとえば：

何人かで食事に行く：どの店にするか、何を頼むか
民主主義：人権保障、権力分立、立憲主義を踏まえた集団的意思決定の制度
社会の発展（厚生経済学）：法律の制定、インフラ整備、社会福祉政策、産業の方向性
株主総会：複数人で会社の方針を決め、持ち株数によって重みが異なる
推薦システム：ユーザーの好みと評価から人気動画ランキングを算出する

選択肢が 2 つのとき：May's Theorem

選択肢が 2 つだけなら、想像どおり、理論上の全体の意志は**多数決（Majority rule）**です。

多数決は次の条件を満たします（May's Theorem）：

Anonymity：一票の価値は等しい
Neutrality：制度はどの選択肢にも偏らない
Positive responsiveness：投票の結果が同数のとき、一人でも心変わりして $A$ を支持すれば、結果は $A$ の勝ちにならなければならない

この 3 つの条件は多数決の核心です。「公平」を完全に表しているわけではありませんが、人々が思いつく公平の解釈としては最も一般的なものです。

しかし多数決で決定を下したとしても、その決定は現実の世界で「全体の意志」を代表できるでしょうか。明らかにできません。少数派の意見が無視されてしまうからです。だからこそ、選択肢が 2 つなら理論上は多数決で集団的決定を作れるものの、現実には多数派の専制を避けるためにルールに制限を加えなければならない場面のほうが多いのです。

選択肢が 3 つのとき：全体の意志は幻想

台湾や民主主義の国で育った人なら、「みんなが投票すれば、集団の意志、人民の知恵が見つかる」と思っているかもしれません。しかし、2 つの定理がこの幻想を否定しています。

アローの不可能性定理は、選択肢が 3 つ以上あれば、基本的な公平性の条件を満たす順位付け投票制度は存在しないことを証明しました
ギバード＝サタースウェイトの定理は、選択肢が 3 つ以上あれば、どんな制度も人々の嘘を防げないことを証明しました

この 2 つの定理は民主政治への美しい幻想を打ち破り、唯一の正しい「全体の意志」は存在せず、あらゆる集団的決定は投票ルールの違いがもたらした結果にすぎないことを教えてくれます。

Source: https://whogovernstw.org/2014/05/20/fangyuchen1/

どんな関数なら全体の意志を代表できるのか

先ほど、全体の意志を代表する $G$ を見つけたいと言いました。では $G$ はどんな形をしているのでしょうか。それぞれの $G$ は「全体の意志」の一つの定義（基準）であり、基準ごとにそれを実現する異なる制度 $F$ があります。たとえば：

効用最大化（Utility Maximization）→ ボルダ得点法（Borda Count）
過半数基準（Majority）→ 相対多数決、二回投票制
コンドルセ基準（Condorcet Criterion）→ Copeland、Schulze、Dodgson

このうち過半数基準とコンドルセ基準を $G$ で書くと、満たせば 1 点、満たさなければ 0 点になります。

選択肢が 4 つ、投票者が 3 人いるとしましょう。

	1 位	2 位	3 位	4 位
太郎	A	B	C	D
花子	B	C	D	A
美咲	A	B	C	D

1. 効用最大化

各人はそれぞれの選択肢に「効用」（好きの度合い）を持っています。ある制度が選んだ結果がみんなにもたらす効用の合計が大きいほど、全体の意志をよく代表していることになります。

G(F) = \sum_{i=1}^{n} u_i\big(F(X, P)\big)

F(X, P) = \arg\max_{x \in X} \sum_{i=1}^{n} u_i(x)

ボルダ得点法：1 位に 3 点、2 位に 2 点、3 位に 1 点、4 位に 0 点を与えます。

	A	B	C	D
太郎	3	2	1	0
花子	0	3	2	1
美咲	3	2	1	0
合計	6	7	4	1

勝つのは B です。A を一番好きな人が 2 人いますが、B は誰からも下位に置かれていない一方、A は花子の最下位です。B のほうが「みんなが受け入れられる」選択肢だと言えます。

2. 過半数基準

**相対多数決（Plurality）**では、各人が一票だけ投じ、最も票の多い選択肢が勝ちます。ほとんどの選挙で使われている方式です。

F(X, P) = \arg\max_{x \in X} \left|\{\, i : x \text{ が } P_i \text{ の 1 位} \,\}\right|

上の例では A が 2 票、B が 1 票で、A が勝ちます。

相対多数決で最もよくある問題は票割れです。

**二回投票制（Two-round system）**では、1 回目で誰も過半数に届かなければ、上位 2 人が 2 回目に進みます。

相対多数決も二回投票制も過半数基準を満たしますが、2 つの制度が異なる結果を選ぶことがあります。過半数基準だけでは全体の意志を決めるのに足りないことがわかります。

3. 拒否権制

誰か一人でも拒否すれば、その選択肢は外されます。この例では A は花子に拒否されるので選ばれません。Neutrality と効率を損なうやり方で、現状維持に傾きます。

最も有名なのは国連安全保障理事会の常任理事国の拒否権でしょう。

4. コンドルセ基準

コンドルセはすべての選択肢を一対一で対決させることを提案しました。ほかのどの選択肢にも一対一で勝てる選択肢（コンドルセ勝者）があれば、それが全体の意志であり、制度はそれを選ばなければなりません。

対決	結果
A vs B	A が 2:1 で勝ち
A vs C	A が 2:1 で勝ち
A vs D	A が 2:1 で勝ち

A がコンドルセ勝者です。相対多数決の結果とは同じですが、ボルダとは異なるので、ボルダはコンドルセ基準を満たしません。

ただ、もう気づいた人もいるでしょう。みんなの好みがじゃんけんのように、チョキがパーに勝ち、パーがグーに勝ち、グーがチョキに勝つ、という関係だったら、コンドルセ基準は使えません。これをコンドルセのパラドックスと呼びます。個人の好みが循環していなくても、集団の好みは循環し得るのです。

5. Dodgson's method

Dodgson には Lewis Carroll というもっと有名な名前があります。『不思議の国のアリス』を書いたあの人です。

彼が提案したのは、コンドルセのパラドックスが起きたら、各選択肢について「隣り合う順位を何回入れ替えれば自分がコンドルセ勝者になれるか」を数え、回数が最も少ない選択肢を勝ちとする方法です。最小の回数と勝者を求めるのは NP 困難な問題です。

ルール	仕組み	長所	短所
ボルダ得点法	順位に応じて点を与え、合計点が最も高い者が勝ち	みんなが受け入れられる妥協案を選べる	無関係な選択肢の影響を受ける。戦略投票で操作されやすい
相対多数決	一人一票、最多得票者が勝ち	シンプルでわかりやすい	票割れ。多数派が最も嫌う人を選ぶことがある
二回投票制	誰も過半数に届かなければ、上位 2 人で再投票	票割れを減らせる	コストが高い。妥協案が先に脱落することがある
拒否権制	拒否されたら外す。すべて拒否されたら現状維持	少数派を守れる	現状維持に偏り、行き詰まりやすい
コンドルセ方式	一対一で対決し、全勝した者が勝ち	勝者はどの一対一でも過半数の支持がある	循環が起き、勝者がいないことがある
Dodgson	順位の入れ替え回数が最も少なくコンドルセ勝者になれる者が勝ち	コンドルセのパラドックスに対処できる	NP 困難で計算が難しい

アローの不可能性定理

アロー（Kenneth Arrow）は、候補者が 3 人以上いるとき、次の 4 つの条件を同時に満たす投票制度は存在しないことを証明しました。

Non-Dictatorship：誰か一人の好みが最終結果を直接決めてはならない
Pareto Efficiency：全員が $A > B$ だと考えるなら、集団の結果も $A > B$ でなければならない
Independence of Irrelevant Alternatives： $A$ と $B$ の相対的な順位は、投票者の $A$ と $B$ に対する好みだけで決まり、第三者 $C$ の参入や撤退に左右されてはならない
Unrestricted Domain：投票者は自分の好みを自由に並べてよく、制度はそのすべてに対応しなければならない

May's Theorem の 3 つの条件と同じく、この 4 つの条件は、選択肢が複数あるときに人々が思いつく公平の解釈として最も一般的なものです。

アローの定理は、完璧な公平が論理的に存在しないことを示しています。集団が下すどんな選択も、個人の好みが変わらなくても、ルールが違えば結果が変わり、必ず何らかのトレードオフを伴います。

Manipulation、Strategyproof と 2000 年台湾総統選挙

Strategyproof（SP）とは、投票者が不誠実な（自分の好みに反する）投票をしても、より良い結果を得られないことを意味します。制度設計を研究する学者にとって、SP な制度を設計することは夢です。しかしギバード＝サタースウェイトの定理は、「候補者が 3 人以上いるとき、独裁的でなく、かつ SP を満たす投票システムはこの世に存在しない」ことを証明しました。

相対多数決では戦略投票が起こりますし、ボルダは言うまでもありません。表明できる選択が多いほど、嘘をつける余地も大きくなります。

実際、Dodgson 本人もボルダ法と相対多数決を嫌っていましたし、ボルダ自身も「My scheme is intended only for honest men（私の方式は正直な人のためだけのものだ）」と言っています。

ケースを一つ見てみましょう。2000 年の台湾総統選挙は、中国国民党の連戦、民主進歩党の陳水扁、無所属の宋楚瑜による三つ巴の戦いでした。最終得票率は陳水扁 39.3%、宋楚瑜 36.84%、連戦 23.1% で、陳水扁が当選しました。

宋楚瑜は台湾省長として、もともと当選の呼び声が非常に高い人物でした。しかし李登輝と決別した後に離党して出馬し、国民党は連戦を擁立しました。宋と連はどちらも汎藍陣営に属し、合わせて 60% 近い票を得ていましたが、この分裂によって二人が票を食い合い、陳水扁が漁夫の利を得る結果になりました。

宋楚瑜はこの選挙でコンドルセ勝者だった可能性が高い（宋 vs 陳では宋の勝ち、宋 vs 連でも宋の勝ち）のに、相対多数決のせいで負けてしまいました。相対多数決ではコンドルセ勝者を選べないのに、なぜ使い続けるのでしょうか。理由はおおよそ次のとおりです。

この選挙には実は 5 人の候補者がいた（李敖と許信良も出馬していた）。コンドルセ方式だと 5 人全員に順位を付けなければならず、手間がかかる
手間に加えて、ルールが複雑でひと目でわからないため、悪意のある人が陰謀論を広めれば、社会秩序と信頼が傷つく
候補者が 3 組しかいなくても、コンドルセのパラドックスが起きないとは限らない

3 について、「まずコンドルセ方式で投票して、パラドックスが起きたら相対多数決かボルダに切り替えればいいのでは？」と思う人もいるでしょう。

この考え方には Black's Method という名前があります。しかしこれでもうまくいきません。汎緑陣営が不誠実な投票で 1 段階目にわざとコンドルセのパラドックスを起こし、2 段階目に持ち込めば、やはりコンドルセ勝者は選ばれないからです。

2000 年に Black's Method を採用していたら：陳水扁陣営が最も戦略投票をする動機を持つ（誠実に投票すれば必ず負けるため）
緑陣営の戦略が成功し、相対多数決に切り替わった場合 $\implies$ 陳水扁の勝ち
緑陣営の戦略が成功し、ボルダ得点法に切り替わった場合 $\implies$ 連戦が勝つ可能性が高いが、ボルダも操作されるリスクがある
有権者全員が誠実に投票した場合 $\implies$ 宋楚瑜の当選

いくつかの方式を組み合わせて生まれた新しい投票方式も、アローの不可能性定理とギバード＝サタースウェイトの定理からは逃れられません。

選択肢が 3 つ以上でも全体の意志が存在する場合：Single-Peaked Preference

選択肢の間に位置、大きさ、高低、政治的スペクトルのような特定の空間的構造があり、投票者の好みが「単峰型選好（Single-Peaked Preference）」、つまり各人に最も好きな選択肢が一つあり、そこから離れるほど好みが下がっていく形になっているなら、理論上の全体の意志は存在します。

たとえば 3 人で旅行の予算を決めるとします。A は 10 万元、B は 20 万元、C は 30 万元がいいと考えていて、自分の希望額から離れるほど満足度が下がる。これが Single-Peaked Preference です。

Single-Peaked Preference の下ではコンドルセのパラドックスが起きないことが保証され、しかも中位投票者（Median Voter）の好みが自動的にコンドルセ勝者になります。これを中位投票者定理（Median Voter Theorem）と呼びます。

現実への応用：投票者が好む候補者や政策を一次元のスペクトル上に並べられるとすると、単峰型選好の前提の下では、選挙に勝ちたい候補者や政党はスペクトルの真ん中にいる「中位投票者」にどんどん近づいていきます（二大政党制や多党制の民主国家で、政党の政策が似通い、中道に寄りがちなのはこのためです）。

まとめ

社会選択理論は、完璧な投票制度は存在せず、集団で意思決定するのは難しいことだと教えてくれます。理論上の完璧な公平が難しいだけでなく、現実には考慮しなければならない要素がほかにもたくさんあります。だからこそ私たちは、相対多数決を乱用して少数派の権利を犠牲にすることも、コンドルセ勝者を最適解だと固執することもしません。投票制度は完璧な解を見つけるためのものではなく、調整と妥協に満ちたシステムです。アルゴリズムの限界を理解し、ゲームの損得を見極め、効率と正義の間でその時々のバランスを見つけることこそ、社会で生きる私たちが考えるべきことです。

Reference

Appendix：ハンター協会会長選挙

冨樫義博の作品『HUNTER×HUNTER』で、ネテロ会長は死後に遺言を残し、次期会長は全ハンターの投票で選ぶこと、投票率が 95% に届かなければその投票は無効としてやり直すことを定めました。十二支んはくじ引きで細則を決め、選ばれたのはジンが書いた 4 つのルールでした。

661 人のハンター全員が投票者であり、全員が候補者でもある
1 回目で誰も過半数に届かなければ、上位 16 人が次の回に進み、以降は回ごとに半分に絞る（16 → 8 → 4 → 2）。誰かが過半数を取るまで続ける
投票率が 95% に届かなければ、その回は無効としてやり直す
記名投票とする

棄権も匿名も許されない多回投票制で、終わるまでに 9 回もかかりました。

ジン：ルールを見抜き、 $F$ を決めた者

95% の基準：5% を超える人が投票しなければその回は丸ごと無効になり、選挙はいつでも膠着し得るので、勝負は、投票したくない人をどれだけ投票所に引っ張り出せるかになる
記名投票：秘密投票を事実上なくすもので、全員の立場がさらけ出され、戦略投票、圧力、派閥による票の囲い込みがすべて見えるようになる
注意をそらす：最後に突拍子もないルールを入れて十二支んの注意を引きつけ、自分がルールを操作した事実を隠した

この選挙の結果は、全体の意志が存在しないことを改めて示しています。ルールを決めたのはジンで、結果も彼の予想とほぼ同じだったのですから。

パリストン：強大な力を持つかき回し役の候補者

パリストンには彼に忠実な協専ハンターが大勢いて、1 回目から 4 割近い票を獲得し、その後もずっと首位を走りました。

彼はよく自分に不利なことをしました。たとえば投票しなかったハンターのライセンスを一時的に没収しようと提案し、かえって棄権する人を増やしました。投票率はなかなか 95% を超えず、選挙はずるずると長引き、反対派（チードル、ミザイストムら）の体力を削っていきました。それも彼にとってはただ楽しむためでした。

レオリオ：感情で票を集めた、しがらみのないダークホース

レオリオは全ハンターの前でジンを殴りました。重傷を負った息子のゴンを見舞いに行かないジンに腹を立てたのです。その映像が広まると、彼の票数は一気に上位へ跳ね上がり、第 8 回の勝者となって、一時はパリストンを脅かすほどになりました。

政策も組織もなく、ただゴンを救いたいだけ。彼が体現していたのは純粋な感情投票で、有権者は彼に票を入れることで、ある出来事への怒りや共感を表していました。こうした票は集まるのも早ければ、離れるのも早いものです。ゴンが回復して会場に戻ると、レオリオは選挙から退き、パリストンが再び主導権を握りました。

チードル：生き残る余地のない中道派

堅実な統治を重んじ、あまり腹黒さのない十二支んのメンバーです。ずっと上位にいましたが、票数は常にパリストンのごく一部にすぎませんでした。パリストンのような組織票も、レオリオのような感情に訴える力もない。伝統的な中道派が極端な陣営に押しつぶされる悲劇です。

最も嫌いな相手を止めるため、彼女は戦略投票に踏み切り、レオリオの当選を後押ししました。

結末：勝ち負けを気にしない者

当選したパリストンは、その場でチードルを副会長に任命し、直後に辞任しました。こうしてチードルが第 14 代会長になりました。

チードルと十二支んが気にしていたのは選挙の勝敗と協会の権力で、パリストンが気にしていたのはゲームそのものだけでした。みんなが票数や戦略投票を計算している間、彼は自分がこのシステムを掌握できることを証明し、協会を治める面倒をチードルに押し返そうとしていました。

あらゆる投票アルゴリズムには暗黙の前提があります。候補者は勝ちたいと思っている、という前提です。結果を気にしないプレイヤーに出会えば、アルゴリズムは誰が最多票を得るかは決められても、その後に何が起きるかまでは決められません。