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