ゲーム理論の問題

経路 $A,B,C$ を選んだ人数をそれぞれ $a,b,c$（$0$ 以上の整数、$a+b+c=6$）とする。各ドライバーの所要時間は人数だけで決まるので、戦略の組がナッシュ均衡かどうかは $(a,b,c)$ だけで決まる。

ある経路を使っている人が別の経路に移ると、移った先の人数は $1$ 増える。よってナッシュ均衡の条件は次のとおりである。

• $a\ge 1$ のとき：$3a\le c_B(b+1)=2b+4$ かつ $3a\le c_C(c+1)=c+7$
• $b\ge 1$ のとき：$2b+2\le c_A(a+1)=3a+3$ かつ $2b+2\le c+7$
• $c\ge 1$ のとき：$c+6\le 3a+3$ かつ $c+6\le 2b+4$

$c=0$ のとき（$a+b=6$）：$a\ge 1$ なら $3a\le 7$ より $a\le 2$。$b\ge 1$ なら $2b+2\le 7$ より $b\le 2$。また $a=0$ なら $b=6$ で $B$ の所要時間 $14$ は $C$ に移ったときの $7$ より大きく不適、$b=0$ なら $a=6$ で $18>7$ より不適。よって $a+b\le 4$ となり $a+b=6$ に反する。均衡なし。

$c=1$ のとき（$a+b=5$）：$C$ の条件 $7\le 3a+3,7\le 2b+4$ より $a\ge 2,b\ge 2$。$A$ の条件 $3a\le 8$ より $a\le 2$。よって $a=2,b=3$。確認すると
$A$：$6\le 10,6\le 8$、$B$：$8\le 9,8\le 8$、$C$：$7\le 9,7\le 10$ でいずれも成り立つ。$(a,b,c)=(2,3,1)$ は均衡。

$c=2$ のとき（$a+b=4$）：$C$ の条件 $8\le 3a+3,8\le 2b+4$ より $a\ge 2,b\ge 2$。よって $a=b=2$。確認すると
$A$：$6\le 8,6\le 9$、$B$：$6\le 9,6\le 9$、$C$：$8\le 9,8\le 8$ でいずれも成り立つ。$(2,2,2)$ は均衡。

$c\ge 3$ のとき：$C$ の条件 $c+6\le 2b+4$ より $b\ge \frac{c+2}{2}$、$c+6\le 3a+3$ より $a\ge \frac{c+3}{3}$。$c=3$ なら $b\ge 3,a\ge 2$ で $a+b\ge 5>3$。$c\ge 4$ ではさらに $a+b=6-c$ が小さくなり、同様に不可能。均衡なし。

以上より、均衡となる人数の組は $(2,3,1)$ と $(2,2,2)$ だけである。ドライバーは区別できるので、割り当ての数は
$$\frac{6!}{2!3!1!}=60,\frac{6!}{2!2!2!}=90.$$
したがって純粋戦略のナッシュ均衡の個数は $60+90=150$ である。

各経路の人数を $(n_A,n_B,n_C)$ とする。ドライバーは区別できるので、人数の組がナッシュ均衡なら、その割り当て方の数は多項係数 $6!/(n_A!n_B!n_C!)$ 通りある。したがって、均衡となる人数の組を調べる。

自分だけ別の経路に移ると、その経路の人数は 1 人増える。移った先の所要時間は、A なら $3(n_A+1)$、B なら $2n_B+4$、C なら $n_C+7$ である。

均衡の条件は、使われている各経路 $r$ について、現在の所要時間が他のどの経路へ移った場合の所要時間以下になることである。
- $n_A>0$ のとき: $3n_A\le 2n_B+4$ かつ $3n_A\le n_C+7$
- $n_B>0$ のとき: $2n_B+2\le 3n_A+3$ かつ $2n_B+2\le n_C+7$
- $n_C>0$ のとき: $n_C+6\le 3n_A+3$ かつ $n_C+6\le 2n_B+4$

$n_A$ の値で場合分けする。
- $n_A=0$: $n_B>0$ なら $2n_B+2\le 3$ より $n_B=0$ となり、$n_C=6$ だが $12\le 3$ が成り立たない。不適。
- $n_A=1$: $n_C>0$ なら $n_C+6\le 6$ が成り立たないので $n_C=0$、よって $n_B=5$。しかし $n_B\le 2$ が必要で不適。
- $n_A=2$: $n_B\ge 1$、$n_B\le 3$、$n_C\le 2n_B-2$ が必要。$(n_B,n_C)=(1,3)$ は $n_C\le 0$ に反して不適。$(2,2)$ と $(3,1)$ は条件を満たす。
- $(2,2,2)$: 所要時間は A が 6、B が 6、C が 8。移った場合は、A の人が B へ 8・C へ 9、B の人が A へ 9・C へ 9、C の人が A へ 9・B へ 8。どれも現在以上なので均衡。
- $(2,3,1)$: 所要時間は A が 6、B が 8、C が 7。移った場合は、A の人が B へ 10・C へ 8、B の人が A へ 9・C へ 8、C の人が A へ 9・B へ 10。どれも現在以上なので均衡。
- $n_A\ge 3$: $3n_A\le 2n_B+4$ と $3n_A\le n_C+7$ から $n_B,n_C$ の下限が決まる。$n_A=3$ なら $n_B\ge 3,n_C\ge 2$ で合計が 3 を超える。$n_A\ge 4$ でも同様に人数の合計が 6 を超える。不適。

均衡となる人数の組は $(2,2,2)$ と $(2,3,1)$ のみである。割り当ての数は次のとおり。
- $(2,2,2)$: $6!/(2!2!2!)=90$
- $(2,3,1)$: $6!/(2!3!1!)=60$

よって均衡の個数は $90+60=150$。