A-002
パス上の確率ゲームに対する効率的なアルゴリズム

◎清藤駿成（東北大）・塩浦昭義（東工大）・徳山　豪（東北大）

Stochastic gamesは複数の戦略型ゲームを頂点としたグラフ上に定義される2人ゼロサム繰り返しゲームである. 頂点にトークンを1つ置き, 各ステップで両プレイヤーはトークンのある頂点に定義される利得表を用いたゲームを行なう. 両プレイヤーの行動の組に応じてそれぞれに利得が与えられ, トークンは遷移確率表に基づいて次の頂点に移動する. 本論文ではグラフ構造をパスに制限し, 各利得表の行動数を2つに限定した場合に, 解析的な手法によってO(n)時間で均衡解を求められることを示す. また, パス上の頂点に順に数値を定義し, 利得がその数値に対する関数であるという仮定を加えた場合に, さらに効率的に計算できることを示す.