$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)$の行和である
ただし、$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} \](証明終わり)