文献

J-GLOBAL ID：201102238167689082   整理番号：11A1226449

コア,カーネル,交渉集合の複雑性

On the complexity of core, kernel, and bargaining set

著者 (4件)： GRECO Gianluigi (Dipartimento di Matematica, Universita della Calabria, I-87036 Rende (CS), ITA) ,  MALIZIA Enrico (DEIS, Universita della Calabria, I-87036 Rende (CS), ITA) ,  PALOPOLI Luigi (DEIS, Universita della Calabria, I-87036 Rende (CS), ITA) ,  SCARCELLO Francesco (DEIS, Universita della Calabria, I-87036 Rende (CS), ITA)
資料名： Artificial Intelligence  (Artificial Intelligence)
巻： 175  号： 12-13  ページ： 1877-1910  発行年： 2011年08月 
JST資料番号： E0180C  ISSN： 0004-3702  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 提携型ゲームはプレイヤーが孤立して行動するよりも高い価値を得るために,提携を形成することによって協調できるシナリオをモデル化する。提携型ゲームの基本的な課題は価値の分配に関して,解概念と通常呼ばれる最も望ましい成果を選び出すことである。現実的なプレーヤーによってなされる決定は無限の資源を使えないので,最近のコンピュータサイエンス論文では解概念を得る計算量の評価の重要性を主張している。本論文では,これに関連してゲームの価値関数がいくつかの合理的なコンパクト表現で表されても,譲渡可能効用を持つ連携型ゲームに対する3つの優れた解概念であるコア,カーネル,交渉集合を用いることで生じる計算量問題の全体像を与えた。調査の出発点は連携の価値がゲームのコード化サイズに対する多項式時間で計算され,様々な未解決問題が論文において提示されているグラフゲームやMarginal contribution netsの設定である。本論文では,それらの問題に答えるのに加え,2つの設定の関連のある一般化や特殊化においてコア,カーネル,交渉集合の計算量を特徴づけることによって特定のゲームに関する新たな洞察を簡潔に与えた。本論文では,特徴づけに関係して,考察される特定のゲームの符号化は問わずに,任意の多項式時間で計算可能な価値関数の処理がグラフゲームやMarginal contribution netsと比べて計算量の付加的な出所を与えないことを示した。その代わりにコアに対してだけは価値関数がNP困難最適化問題をコード化するゲームの種類,組合せゲームの場合などで計算量にわずかな増加が示された。本論文では,特殊化に関しては有界木幅グラフゲームやMarginal contribution networksといった種類において,様々な取り扱いやすい成果を説明した。Copyright 2011 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.

シソーラス用語： *ゲーム ,  評価関数 ,  *計算量 ,  キャラクタリゼーション ,  アルゴリズム ,  *NP困難 ,  *最適化問題 ,  木【グラフ】 ,  ネットワーク構造 ,  幅
準シソーラス用語： 多項式時間アルゴリズム ,  木幅

分類 (3件)： ゲーム理論  (KA03060T) ,  計算理論  (JB02000A) ,  その他のオペレーションズリサーチの手法  (KA03070E)

タイトルに関連する用語 (5件)： コア ,  カーネル ,  交渉 ,  集合 ,  複雑性