プリズム

数理的アプローチ


ボルダルールの勝者(敗者)を投票行列から求める

投稿日時:

最終更新日時:

カテゴリー:

,

$n$人の投票者、$N= \left\{ 1,\ldots, n \right\}$、の各々が$p$人の候補者、$A= \left\{ 1, \ldots, p \right\}$に一番好きなものから一番嫌いなものまで順位(選好)を付けている時、投票者の意見をまとめて、どの候補者を望ましい候補者(勝者)、または、どの候補者を望ましくない候補者(敗者)、として選ぶか?

に対して、点数式投票ルールの1つとして、ボルダルールが知られている。各投票者は一番好きな候補者に$p-1$点、その次に好きな候補者に$p-2$点、・・・、一番嫌いな候補者に$0$点、という点数を与える。各候補者はすべての投票者から与えられた点数を合計する。最大の合計点数を得た候補者がボルダルールの勝者、最小の合計点数を得た候補者がボルダルールの敗者である。すなわち、次の$\mathrm{BordaScore}$を最大にする候補者$x \in A$が勝者、最小にする候補者$x \in A$が敗者である。

\[ \mathrm{BordaScore} \left( u;x \right) = \sum_{k \in A}{\mathrm{rank}_k(u;x)s_k} \]

ただし、$s_k=p-k$、$\mathrm{rank}_k(u;x)$は$x \in A$を第$k$番目に好む投票者の人数を意味する。また、$u=\left( u_1,\ldots, u_n \right)$は投票者の選好を表し、$u_j(x) \gt u_j(y)$は投票者$j \in N$が$y \in A$より$x \in A$を好んでいることを意味する。

結論を先に述べる。

$\mathrm{BordaScore}$は投票行列$v=\left( v_{xy}(u) \right)$の行和である

\[ \mathrm{BordaScore} \left( u;x \right) = \sum_{y: y \in A, y \not= x}{v_{xy}(u)} \]

ただし、$v_{xy}(u)= \left| \left\{ j \in N \left| u_j(x) \gt u_j(y) \right. \right\} \right|$、$\left| S \right|$は集合$S$の要素の個数、すなわち、$v_{xy}(u)$は$y$より$x$を好む投票者の人数である。

この結論は以下に述べる「補題3」から得られる。まず、新たに次の記号を導入する。

\[ \begin{eqnarray} \mathrm{rank}_k \left( j,u;x \right) &=& \left\{ \begin{array}{cc} 1 & 投票者jがxを第k番目に好む時 \\ 0 & {\rm otherwise} \end{array} \right. \\ I_j(x,y) &=& \left\{ \begin{array}{cc} 1 & u_j(x) \gt u_j(y) \\ 0 & {\rm otherwise} \end{array} \right. \end{eqnarray} \]

補題1

\[ \begin{eqnarray} \mathrm{rank}_k \left(u;x \right) &=& \sum_{j \in N}{\mathrm{rank}_k \left( j,u;x \right)} \\ v_{xy}(u) &=& \sum_{j \in N}{I_j(x,y)} \end{eqnarray} \]

証明

$\mathrm{rank}_k(u;x)$は$x \in A$を第$k$番目に好む投票者の人数であり、各投票者$j \in N$に$x$を第$k$番目に好むかを問い、答えが「はい」のプレイヤーだけを数えればよい。同様に、$v_{xy}(u)$は$y \in A$より$x \in A$を好んでいる投票者の人数であり、各投票者$j \in N$に$y$より$x$を好むかを問い、答えが「はい」のプレイヤーだけを数えればよい。(証明終わり)

補題2

\[ \sum_{y: y \in A, y \not= x}{I_j(x,y)} = \sum_{k \in A}{\mathrm{rank}_k \left( j,u;x \right)} \left( p – k \right) \\ \]

証明

左辺は投票者$j$が$x$よりも好まない候補者の人数である。投票者$j$が$x$を第$k$番目に好んでいれば、$x$よりも好まない候補者の人数は$p-k$となる。(証明終わり)

補題3

\[ \sum_{y: y \in A, y \not= x}{v_{xy}(u)} = \sum_{k \in A}{\mathrm{rank}_k(u;x) (p-k)} \]

証明

補題1と2より

\[ \begin{eqnarray} \sum_{y: y \in A, y \not= x}{v_{xy}(u)} &=& \sum_{y: y \in A, y \not= x} \left( {\sum_{j \in N}{I_j(x,y)}} \right) \\ &=& \sum_{j \in N} \left( {\sum_{y: y \in A, y \not= x}{I_j(x,y)}} \right) \\ &=& \sum_{j \in N} \left( {\sum_{k \in A}{\mathrm{rank}_k(j,u;x)(p-k)}} \right) \\ &=& \sum_{k \in A} \left( {\sum_{j \in N}{\mathrm{rank}_k(j,u;x)}} \right) (p-k) \\ &=& \sum_{k \in A}{\mathrm{rank}_k(u;x)(p-k)} \end{eqnarray} \]

(証明終わり)