文献

J-GLOBAL ID：201802270863512611   整理番号：18A1802356

制約付き近似Nash均衡に対する近似不可能性結果【JST・京大機械翻訳】

Inapproximability results for constrained approximate Nash equilibria

著者 (3件)： Deligkas Argyrios (Faculty of Industrial Engineering and Management, Technion-Israel Institute of Technology, Israel) ,  Fearnley John (Department of Computer Science, University of Liverpool, L69 3BX, UK) ,  Savani Rahul (Department of Computer Science, University of Liverpool, L69 3BX, UK)
資料名： Information and Computation  (Information and Computation)
巻： 262  号： P1  ページ： 40-56  発行年： 2018年 
JST資料番号： D0449A  ISSN： 0890-5401  CODEN： INFCEC  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 著者らは,良好な社会福祉を提供するような特定の条件を満たす近似Nash均衡を見出す問題を研究した。特に,ε-NEδ-SWの問題を研究した。ε-NEにより達成可能な最良の社会福祉のδ内にあるε-近似Nash均衡(ε-NE)を見出した。著者らの主な結果は,指数-時間仮説(ETH)が真であるならば,n×nバイトリックスゲームに対する(18-O(δ))-NE O(δ)-SWの解はnΩ(logn)時間を必要とする。この結果に基づいて,ε-NEに対する多くの他の決定問題に対する類似条件付き実行時間下限を示した。例えば,プレイヤの支払いまたはサポートは制約される。ETHを仮定したこれらの問題に対する準多項式下限を示し,これらの下限はすべてのε<18に対してε-Nash平衡に適用した。これらの他の決定問題の硬度は,厳密な平衡の文脈でのみ研究されてきた。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 硬度 ,  多項式 ,  *近似法 ,  バイト ,  *Nash均衡 ,  決定問題 ,  ゲーム ,  社会福祉
準シソーラス用語： プレイヤ ,  実行時間 , 【Automatic Indexing@JST】

著者キーワード (5件)： 近似Nash平衡 ,  拘束平衡 ,  準多項式時間 ,  下界 ,  指数時間仮説

分類 (2件)： ゲーム理論  (KA03060T) ,  計算理論  (JB02000A)

タイトルに関連する用語 (3件)： 制約 ,  近似 ,  Nash均衡