２次の効用関数に関する組合せオークションにおける最適配分問題のアルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2011-02-28
• タイトル: ２次の効用関数に関する組合せオークションにおける最適配分問題のアルゴリズム
• タイトル / 言語: en
• タイトル: Algorithms for Optimal Allocation Problem in Combinatorial Auction with Quadratic Utility Functions
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東北大学
• 著者所属: 東北大学
• 著者所属(英): en
• 著者所属(英): Tohoku University
• 著者所属(英): en
• 著者所属(英): Tohoku University
• 著者名: 塩浦, 昭義; 鈴木, 瞬也
• 著者名(英): Akiyoshi, Shioura; Shunya, Suzuki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では組合せオークションにおける最適配分問題について議論する．この問題では，オークション参加者に財を配分し，参加者の効用の合計値を最大にすることを目的とする．本稿では，効用関数が 2 次関数により与えられる場合を考える．2 次の効用関数は，簡潔な表現をもつにもかかわらず，十分に一般的な効用関数のクラスを与える．本稿は，2 次の効用関数に関する最適配分問題の計算複雑度を明らかにすることを目的とする．とくに，効用関数が劣モジュラおよび優モジュラの場合について考え，NP 困難性および多項式時間の厳密 （もしくは近似） アルゴリズムを示す．これらの結果は，最小 （最大） カット問題や多方面カット問題などのグラフカット問題との関係を利用して示される．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We discuss the optimal allocation problem in combinatorial auction, where the items are allocated to bidders so that the sum of the bidders' utilities is maximized. In this paper, we consider the case where utility functions are given by quadratic functions; the class of quadratic utility functions has a succinct representation but is sufficiently general. The main aim of this paper is to show the computational complexity of the optimal allocation problem with quadratic utility functions. We consider the cases where utility functions are submodular and supermodular, and show NP-hardness and/or polynomial-time exact/approximation algorithm. These results are given by using the relationship with graph cut problems such as the min/max cut problem and the multiway cut problem.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2011-AL-134, 号 3, p. 1-8, 発行日 2011-02-28
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会