08/08/23 21:54:56
最強戦略が存在することの(不完全な)証明
π1,...,πnを全ての戦略をとし、V(πi,πj) を 戦略πjが戦略πiに勝つ確率とする
ゲーム開始時に確率Piで戦略πiを選択し、以後その戦略を突き通すという戦略を新たにπ(P1,...,Pn)とする
この戦略はP1,...,Pnのパラメータを適当に調整することでどんな戦略もエミュレートできる
自分が戦略π(P1,...,Pn)を用い、相手が戦略π(Q1,...,Qn)で挑んでくるとする。Qiのパラメータの選び方によらず勝率50%を達成するPjの存在を示す
行列V を i,j成分が V(πi,πj) である行列と定義する
P,Qをそれぞれ、P1,...,Pn、Q1,...,Qnを並べた縦ベクトルとする
P = V^(-1) [1/2,...,1/2]' と、すべての要素が1/2の縦ベクトルにVの逆行列をかけたものを選ぶ
(Vの正則性、Pi>0,sum[i]Pi=1が成り立つ事の証明は…まだしていない、多分 "V+V'=1を並べた行列" 等の性質を使う)
このときの自分の勝率は
V(π(Q1,...,Qn),π(P1,...,Pn)) = sum[i,j] Qi V(πi,πj)Pj = Q'VP= Q' [1/2,...,1/2] = sum[i] Qi (1/2) = 1/2
とQjの値に依存することなく常に50%になる。つまりπ(P1,...,Pn)は最強の戦略になる。