ゲーム理論

ゲーム情報学の数学的基礎はゲーム理論とコンピュータサイエンスである。コンピュータサイエンス部分の多くはグラフ理論を中心とした離散数学であり、主として、いわゆる探索の工学的な技術からなる。

ゲーム理論は、競争的環境にある複数の主体が何らかの交渉を行い（ゲーム）、その結果として互いに得る利得を最大化（最適応答）するときの様々な様相について数学的に検討する理論である。とくに、戦略とゲームの値、混合戦略、ゲーム木、NASH均衡と解、情報集合、協力ゲームなど、重要かつ有用な概念を提案している。

個々のゲームは、プレーヤーと戦略と利得関数によって定義されるプレーヤー間の交渉である。ゲーム理論の戦略とは、日常語のそれとはすこし意味がことなり、プレーヤーが取ることのできる選択肢である。利得関数は、各プレーヤーがそれぞれの戦略を選択したとき、その組み合わせに応じて各プレーヤーが得る利得を決定する。これらのプレーヤー、戦略、利得関数についてすべてのプレーヤーがすべての情報を知っている場合、これを完全情報（完備）ゲームという。その一部でも知ることのできないプレーヤーがあるとき、不完全情報（不完備）ゲームという。また、戦略や、利得に確率的な変動が加わり得るゲームを、不確定ゲームという。プレーヤー、戦略、利得関数の全てが有限のとき、有限ゲームという。

プレーヤーの人数によってゲームの数学的な特徴が変わる。チェスや囲碁将棋などは、有限完全情報２人ゲームであり、AI分野での研究が進んでいる。プレーヤーが3人以上のゲームを多人数ゲームという。2人ゲームと比較して、自身の最適な行動を持ってしても最適な結果が得られないことがある（他人任せになることがある）という特徴があり扱いが難しい。

ゲームの利得が得られるまでに、各プレーヤーの行動選択と、ゲーム盤面の状態の遷移があり、木を展開するようにゲームを描いたとき、これを展開型ゲームという。ゲーム情報学が主として扱うのはこの展開型のゲームである。あるゲームの状態を手番とよぶ。

ゲームが展開型で書かれたとき、そこでできた状態遷移の木をゲーム木とよぶ。チェスや囲碁将棋のような2人完全情報ゲームの木では、その末端（葉）でプレーヤの勝敗が決定し、この木を逆に溯る（back up/back track）ことで途中の手番（プレーヤーが行動選択をする場面）での最適な行動を決定していくことができる。ある手番で可能な行動を合法手といい、行動をすることで新たな手番（ゲームの状態）に遷移する。

2人ゲームでは、手番のそれぞれについて、勝ちか負けか（あるいは引き分けか）を決定することができる。こうした手番以降の末端までの部分木を部分ゲームと呼ぶ。

じゃんけんのような手番を持たないゲームでは、互いの戦略を同時に決定し、戦略が決定し次第利得も決定する。こうしたゲームを記述したものを、展開型ゲームに対して戦略型ゲームと呼ぶ。じゃんけんであれば、戦略は３つで、グー、チョキ、パーである。ゲームの利得関数は、グーとグー、グーとパーなどその組み合わせに対して勝ち負けを利得の値として記述する。たとえば勝ち=1、負け= -1 、あいこ=0のようになる。グリコ・パイナップル・チョコレートというじゃんけんの派生など、勝ちの値が1ではなく、グリコ勝ち=3、パー勝ち=5のように不均一なものもある。

戦略型ゲームと展開型ゲームは互いに変換可能であり、本質的には同じように扱うことができる。

混合戦略は複数の戦略のうち一つを単独で選択するのではなく、確率分布によって混合して用いる（確率的に決定する）選択方である。実際のゲームにおいて戦略は、グーチョキパーのように、いっときに一つの戦略しか選べない。これらを純戦略という。グーチョキパーは三すくみになっており、他の二つに優位な最強の手はない。いっぽうでグーだけを出す、と決めて繰り返すと相手はパーばかりを出して負けてしまう。すなわち適度な変更が必要である。N回ジャンケンをするとき、グーチョキパーを出す割合に偏りがありそれがバレていれば、相手は対策ができてしまう。そうした対策の全てに対してもっとも負けが少なくなるのは、グーチョキパーを出す割合が均一のときとなる。すなわち最適な方法は、3つの純戦略（グー, チョキ, パー）に対応して (1/3, 1/3, 1/3)の確率分布となり、このような決め方を混合戦略という。

例のように、混合戦略の範囲であれば必ず最適な手、すなわち失敗を最小にする出し方があり、これをNash均衡解という。

展開型ゲームについても、同様に純戦略と、その純戦略にもとづいた混合戦略が定義でき、混合戦略の上ではNash均衡解が存在する。