文献

J-GLOBAL ID：202002235734927433   整理番号：20A2094170

有限状態機械は広範な形式ゲームを演じる【JST・京大機械翻訳】

Finite State Machines Play Extensive-Form Games

著者 (3件)： Cerny Jakub (Nanyang Technological University, Singapore, Singapore) ,  Bosansky Branislav (Czech Technical University in Prague, Prague, Czech Rep) ,  An Bo (Nanyang Technological University, Singapore, Singapore)
資料名： ACM Proceedings  (ACM Proceedings)
号： EC ’20  ページ： 509-533  発行年： 2020年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 有限状態機械は,(in)無限反復または確率的ゲームにおける戦略のよく知られた表現である。プレーヤーは機械における状態に対応し,機械状態間の遷移はゲームにおける観測によって引き起こされる。拡張型ゲーム(EFG)では,マシンは,大きなEFGを解くのに使用される抽象化手法のための形式的な接地として,また十分にコンパクトな抽象を生成するための領域独立アプローチとして動作できる。EFGにおける制限サイズの機械を用いることは,(i)強いStackelberg平衡(SSE),(ii)を含むいくつかの解概念の計算の理論的複雑性を低減でき,また,戦略空間の一部だけを考慮した近最適平衡を計算する新しい実用的アルゴリズムをもたらすことを示す。著者らの貢献は,(1)EFGにおける機械戦略の形式的定義と理論的キャラクタリゼーション,(2)解概念のための形式的定義と複雑性解析,およびマシンの小さいクラスに制約されたときのそれらの計算,(3),マシンの概念を直接使用するゼロサムゲームにおけるSSEを計算するための新しいアルゴリズム,である。2つの異なるドメインに関する実験結果は,アルゴリズムが近最適戦略を計算して,以前の最先端アルゴリズムと比較して有意により良いスケーラビリティを達成することを示した。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  *ゲーム ,  *有限状態機械 ,  計算理論 ,  釣合 ,  キャラクタリゼーション
準シソーラス用語： 複雑性 ,  プレイヤ ,  最適戦略 , 【Automatic Indexing@JST】

著者キーワード (7件)： NASH均衡 ,  抽象化 ,  オートマトン ,  相関平衡 ,  広範な形式ゲーム ,  Stackelberg平衡 ,  戦略的複雑性

分類 (2件)： ゲーム理論  (KA03060T) ,  人工知能  (JE08000Z)

タイトルに関連する用語 (3件)： 有限状態機械 ,  形式 ,  ゲーム