プリズム

数理的アプローチ


シャープレイ値の自己双対性

投稿日時:

最終更新日時:

タグ:

$N=\{1, \ldots, n \},d = (d_1, \ldots, d_n), D=\sum_{j \in N}{d_j} – E$とおくと、$Sh(E;d)= d – Sh(D;d)$となること。ただし、$0 \lt E \le \sum_{j \in N}{d_j}$である。

(証明)

シャープレイ値の定義は、

$Sh_j (E;d) = \frac{1}{n!} \sum_{\pi \in \Pi}{f_j^{\pi}(E;d)}$
$f_j^{\pi}(E;d) = \min \left\{d_j, \max \left\{0, E- \sum_{i: \pi (i) < \pi (j)}{d_i} \right\} \right\}$

ただし、$\Pi$は$n!$通りの順列の集合であり、その要素$\pi$において$\pi(i)$はプレイヤー$i$が到着した順番を表す、であった。

$\pi’$で$\pi$の逆順を表すことにする、すなわち、$\pi'(i)=n+1-\pi(i)$とする。

$E- \sum_{i: \pi (i) < \pi (j)}{d_i} = d_j + \sum_{i: \pi (i) > \pi (j)}{d_i} – D = d_j + \sum_{i: \pi’ (i) < \pi' (j)}{d_i} - D$、すなわち、$\left(E- \sum_{i: \pi (i) < \pi (j)}{d_i} \right) + \left( D - \sum_{i: \pi' (i) < \pi' (j)}{d_i} \right) = d_j$である。左辺の2項が共に正で$d_j$より小さい場合と、一方が非正で他方が$d_j$以上の場合の2通りがある。どちらの場合も

$f_j^{\pi}(E;d) + f_j^{\pi’}(D;d)$ $= \min \left\{d_j, \max \left\{0, E- \sum_{i: \pi (i) < \pi (j)}{d_i} \right\} \right\}$ $+ \min \left\{d_j, \max \left\{0, D- \sum_{i: \pi' (i) < \pi' (j)}{d_i} \right\} \right\}$ $= d_j$

となる。$\pi$に$\pi’$を対応させる関係は1対1の関係であるので、

$\sum_{\pi \in \Pi}{f_j^{\pi}(E;d)} + \sum_{\pi’ \in \Pi}{f_j^{\pi’}(D;d)} = n! d_j$、すなわち、$Sh_j (E;d) + Sh_j (D;d) = d_j (j \in N)$となる。(証明終わり)