ゲーム理論の問題

手順 1：人数の組で費用を表す。 道路 $P,Q,R$ を選んだ台数をそれぞれ $a,b,c$（$0$ 以上の整数，$a+b+c=5$）とする。所要時間を $10$ 分単位で表すと，$P$ は $a$，$Q$ は $b+1$，$R$ は $2c$ である。

手順 2：「移っても短くならない」条件を不等式にする。 あるトラックが別の道路に移ると，移り先の台数が $1$ 増える。
- $P$ のトラック（$a\ge 1$ のとき）：$Q$ へ移ると $(b+1)+1$，$R$ へ移ると $2(c+1)$。条件は $a\le b+2,a\le 2c+2$。
- $Q$ のトラック（$b\ge 1$ のとき）：$P$ へ移ると $a+1$，$R$ へ移ると $2(c+1)$。条件は $b+1\le a+1$ すなわち $b\le a$，$b+1\le 2c+2$。
- $R$ のトラック（$c\ge 1$ のとき）：$P$ へ移ると $a+1$，$Q$ へ移ると $b+2$。条件は $2c\le a+1,2c\le b+2$。

手順 3：条件を満たす $(a,b,c)$ を探す。
- $c=0$ のとき $a+b=5$。$b\ge 1$ なら $b+1\le 2$ より $b=1$，$a=4$ となるが $a\le 2c+2=2$ に反する。$b=0$ なら $a=5\le 2$ に反する。解なし。
- $c=1$ のとき $a+b=4$。$R$ の条件 $2\le a+1$ より $a\ge 1$。
- $(4,0,1)$：$a\le b+2$ が $4\le 2$ で不成立。
- $(3,1,1)$：$3\le 3,3\le 4,1\le 3,2\le 4,2\le 4,2\le 3$ すべて成立。
- $(2,2,1)$：$2\le 4,2\le 4,2\le 2,3\le 4,2\le 3,2\le 4$ すべて成立。
- $(1,3,1)$：$b\le a$ が $3\le 1$ で不成立。
- $c=2$ のとき $R$ の条件 $4\le a+1,4\le b+2$ より $a\ge 3,b\ge 2$ となり $a+b=3$ と矛盾。$c\ge 3$ でも同様に $a\ge 2c-1\ge 5$ となり不可能。

よって均衡となる人数の組は $(3,1,1)$ と $(2,2,1)$ である。

手順 4：区別できるトラックの割り当てを数える。 人数の組 $(a,b,c)$ に対する割り当ては同じものを含む順列で $\frac{5!}{a!b!c!}$ 通り。
$$\frac{5!}{3!1!1!}=20,\frac{5!}{2!2!1!}=30$$
したがって純粋戦略ナッシュ均衡の個数は $20+30=50$ である。

道路 $P,Q,R$ を選ぶトラックの台数を $(a,b,c)$（$a+b+c=5$）とする。各トラックの所要時間は $P:10a$、$Q:10b+10$、$R:20c$ である。

1 台が移ると、移り先の道路の台数が 1 増える。そこで、各移動について「移っても真に短くならない」条件を書く。
- $P\to Q$: $10a\le 10(b+1)+10$ より $a\le b+2$
- $P\to R$: $10a\le 20(c+1)$ より $a\le 2c+2$
- $Q\to P$: $10b+10\le 10(a+1)$ より $b\le a$
- $Q\to R$: $10b+10\le 20(c+1)$ より $b\le 2c+1$
- $R\to P$: $20c\le 10(a+1)$ より $2c\le a+1$
- $R\to Q$: $20c\le 10(b+1)+10$ より $2c\le b+2$

各条件は、移る元の道路を選んでいるトラックが 1 台以上いるときだけ課す。

場合分けする。
- $c=0$: $a+b=5$ で、$b\ge 1$ なら $b\le 2c+1=1$ なので $a\ge 4$ となる。一方 $a\le 2c+2=2$ が必要で矛盾する。$b=0$ の場合は $a=5$ で $a\le 2$ に反する。よって解なし。
- $c=1$: $a+b=4$ で、$a\le b+2$、$b\le a$、$a\ge 1$ が必要。$(a,b)=(3,1),(2,2)$ が条件を満たす。$(4,0)$ は $a\le b+2$ に反し、$(1,3)$ と $(0,4)$ は $b\le a$ に反する。
- $c=2$: $a+b=3$ だが、$2c\le a+1$ より $a\ge 3$、$2c\le b+2$ より $b\ge 2$ が必要で、和が 3 にならず矛盾する。
- $c\ge 3$: $a+b\le 2$ だが、$6\le 2c\le a+1$ が必要で不可能。

したがって均衡の台数配分は $(3,1,1)$ と $(2,2,1)$ のみである。

検算:
- $(3,1,1)$ の所要時間は $P:30,Q:20,R:20$。$P$ のトラックが $Q$ に移ると $30$ 分、$R$ に移ると $40$ 分で、短くならない。$Q$ のトラックが $P$ に移ると $40$ 分、$R$ に移ると $40$ 分。$R$ のトラックが $P$ に移ると $40$ 分、$Q$ に移ると $30$ 分。よって均衡。
- $(2,2,1)$ の所要時間は $P:20,Q:30,R:20$。$P$ のトラックが $Q$ または $R$ に移ると $40$ 分。$Q$ のトラックが $P$ に移ると $30$ 分、$R$ に移ると $40$ 分。$R$ のトラックが $P$ に移ると $30$ 分、$Q$ に移ると $40$ 分。いずれも短くならず、均衡。

トラックは区別されるので、割り当ての数は次のとおり。
- $(3,1,1)$: $\frac{5!}{3!1!1!}=20$ 通り
- $(2,2,1)$: $\frac{5!}{2!2!1!}=30$ 通り

合計は $20+30=50$ である。