文献

J-GLOBAL ID：201702283900485630   整理番号：17A1497785

匿名ゲームにおける近似平衡の質問複雑性【Powered by NICT】

Query complexity of approximate equilibria in anonymous games

著者 (2件)： Goldberg Paul W. (Wolfson Building, Parks Road, University of Oxford, United Kingdom) ,  Turchetta Stefano (KPMG, Italy)
資料名： Journal of Computer and System Sciences  (Journal of Computer and System Sciences)
巻： 90  ページ： 80-98  発行年： 2017年 
JST資料番号： B0861A  ISSN： 0022-0000  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 匿名ゲームのNash平衡,ゲームの支払い関数に対する適応質問を用いたアルゴリズムを介しての計算を研究した。厳密な平衡は,質問の効率的なアルゴリズムを介して見出すことができないことを示し,厳密な平衡は無理数を必要とする二戦略,3選手匿名ゲームを示した。匿名ゲームの既知のサブクラスに陽性の結果を得た。著者らの主要な結果は,以前のアルゴリズムの実行時間を改善する二つの戦略の匿名ゲームの近似平衡のための新しいランダム化質問効率的なアルゴリズムである。多項式時間における逆多項式近似を得るために最初のものであり,効率的な多項式時間近似スキームをもたらす。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *近似法 ,  多項式近似 ,  *ゲーム ,  アルゴリズム ,  計算量
準シソーラス用語： 多項式時間 ,  実行時間 ,  *匿名 , 【Automatic Indexing@JST】

著者キーワード (3件)： Algorithms ,  計算の複雑さ ,  ゲーム理論

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (5件)： 匿名 ,  ゲーム ,  近似 ,  平衡 ,  質問複雑性