ゲーム理論の問題

シャープレイ値は、$4$ 社が到着する順番 $4!=24$ 通りが同様に確からしいとしたときの、各社の限界費用 $C(S\cup \{i\})-C(S)$（$S$ は $i$ より先に到着した会社の集合）の期待値に等しい。

滑走路を区間に分けて考える。 滑走路を次の $4$ つの区間に分ける。
- 区間 I（長さ $0\to 8$ に相当、費用 $8$）：会社 $1,2,3,4$ がすべて使う
- 区間 II（$8\to 20$、費用 $12$）：会社 $2,3,4$ が使う
- 区間 III（$20\to 32$、費用 $12$）：会社 $3,4$ が使う
- 区間 IV（$32\to 50$、費用 $18$）：会社 $4$ だけが使う

すると $C=C_{\mathrm{I}}+C_{\mathrm{II}}+C_{\mathrm{III}}+C_{\mathrm{IV}}$ と分解できる。ここで、たとえば $C_{\mathrm{II}}(S)$ は「$S$ が会社 $2,3,4$ のどれかを含めば $12$、含まなければ $0$」である。

このようなゲームでは、その区間を使う会社の中で最初に到着した会社だけが限界費用としてその区間の費用を負担する。使う会社の中でどの会社が最初に到着するかは同様に確からしいので、区間の費用は使う会社で等分される。シャープレイ値は加法的（ゲームの和のシャープレイ値は各ゲームのシャープレイ値の和）なので、次のように計算できる。

• ${\phi }_1=\frac{8}{4}=2$
• ${\phi }_2=\frac{8}{4}+\frac{12}{3}=2+4=6$
• ${\phi }_3=\frac{8}{4}+\frac{12}{3}+\frac{12}{2}=2+4+6=12$
• ${\phi }_4=2+4+6+\frac{18}{1}=30$

検算（会社 $4$ を直接計算する）。 会社 $4$ の限界費用は $50-(\text{先に来た会社の }{c}_i\text{ の最大値})$ である（先に誰もいなければ最大値を $0$ とする）。会社 $4$ の到着順位は $1$ 位から $4$ 位まで各確率 $\frac{1}{4}$ で、先に来た会社の集合はその人数の部分集合の中で一様に現れる。
- $1$ 位のとき：最大値は $0$
- $2$ 位のとき：最大値の平均は $\frac{8+20+32}{3}=20$
- $3$ 位のとき：$\{1,2\},\{1,3\},\{2,3\}$ の最大値はそれぞれ $20,32,32$ なので、平均は $\frac{20+32+32}{3}=28$
- $4$ 位のとき：最大値は $32$

よって最大値の期待値は $\frac{0+20+28+32}{4}=20$ となり、${\phi }_4=50-20=30$ で一致する。

また $2+6+12+30=50=C(N)$ となり、全体の費用がちょうど配分されている（全体合理性）ことも確認できる。

答えは $({\phi }_1,{\phi }_2,{\phi }_3,{\phi }_4)=(2,6,12,30)$ である。

滑走路問題（空港ゲーム）なので、費用を区間ごとに分けて考える。

• 長さ $0\sim 8$ の区間（費用 $8$）は会社 $1,2,3,4$ の全員が必要とする。
• 長さ $8\sim 20$ の区間（費用 $12$）は会社 $2,3,4$ が必要とする。
• 長さ $20\sim 32$ の区間（費用 $12$）は会社 $3,4$ が必要とする。
• 長さ $32\sim 50$ の区間（費用 $18$）は会社 $4$ だけが必要とする。

各区間の費用は、その区間を必要とする会社が等分して負担する。この分け方がシャープレイ値と一致する。理由は、各区間を $C_k(S)=($区間の費用$)\cdot [S\cap T_k\ne \varnothing ]$ というゲームとみなすと、そのシャープレイ値は $T_k$ の会社に等分されるからである。そして $C$ はこれらのゲームの和になり、シャープレイ値は加法的である。

• ${\phi }_1=8/4=2$
• ${\phi }_2=2+12/3=6$
• ${\phi }_3=6+12/2=12$
• ${\phi }_4=12+18=30$

検算：合計は $2+6+12+30=50=C(N)$ であり、全体の費用と一致する（効率性）。