文献

J-GLOBAL ID：202002298231200923   整理番号：20A1504819

予算付加評価によるナッシュ社会福祉の近似【JST・京大機械翻訳】

Approximating the nash social welfare with budget-additive valuations

著者 (3件)： Garg Jugal (University of Illinois at Urbana-Champaign) ,  Hoefer Martin (Goethe University Frankfurt, Germany) ,  Mehlhorn Kurt (MPI fuer Informatik, Saarbruecken, Germany)
資料名： ACM Proceedings  (ACM Proceedings)
号： SODA ’18  ページ： 2326-2340  発行年： 2018年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 予算-加算評価関数を持つエージェントに不可視アイテムを割り当てるとき,Nash社会福祉を最大化するための最初の定数近似アルゴリズムを提示する。予算-加算評価は,サブモジュール機能の重要なクラスを表す。それらは,多くの興味深い応用により,近年,多くの研究の興味を引いている。あらゆるε>に対して,提案アルゴリズムは入力サイズと1/εの時間多項式で(2.404+ε)近似を得る。提案アルゴリズムは,売り手が収益限界を持つ線形Fisher市場における近似平衡を丸めることに依存する(金額を望む金額の上限)と買い手がユーティリティ限界を持つ(ユーティリティ量に関する上限は達成を望む)。収益またはユーティリティ限界を持つ市場とは対照的に,これらの市場は以前には研究されていない。それらは基本的に異なる性質を有することが判明した。平衡の存在は保証されないが,Nash社会福祉問題から生じる市場事例は常に平衡を持つことを示す。さらに,平衡のセットは凸ではなく,[17]の質問に答えることを示した。近似平衡を計算するためにFPTASを設計し,その結果,独立した興味の可能性がある。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】

分類 (2件)： 数値計算  (JE02000J) ,  計算理論  (JB02000A)

タイトルに関連する用語 (5件)： 予算 ,  評価 ,  社会 ,  福祉 ,  近似