確率ゲームにおけるコミットメントのための最適戦略の計算

AIとゲーム理論の交差点における以下の2つの研究分野で最近重要な進展がありました：(1) コミットメントするための最適戦略の計算（スタッケルバーグ戦略）、および (2) 確率ゲームの相関均衡の計算。本論文では、確率ゲームにおけるスタッケルバーグ戦略の計算を研究することによって、これら2つの研究ラインを統合します。コミットメントの価値および相関の価値についての理論的結果と、確率ゲームにおけるスタッケルバーグ戦略の計算に関する計算の複雑性結果を提供します。その後、QPACEアルゴリズム（MacDermed et al. 2011）を修正してスタッケルバーグ戦略を計算し、実験結果を提供します。