文献

J-GLOBAL ID：201402231565688964   整理番号：14A0638830

複数の分化アイテムのある反復競売の時間複雑性解析

Time Complexity Analysis of Iterative Auctions with Multiple Differentiated Items

著者 (3件)： MUROTA Kazuo (Univ. Tokyo, Tokyo, JPN) ,  SHIOURA Akiyoshi (Tohoku Univ., Sendai, JPN) ,  YANG Zaifu (Univ. York, York, GBR)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 114  号： 19(COMP2014 1-7)  ページ： 45-51  発行年： 2014年04月17日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 総代替品査定のある上行競売におけるWalrasian平衡価格の計算問題を考えた。特に,競売市場は複数の分化アイテムがあり,その各アイテムは複数ユニットを持つような場所で考えた。上昇競売は有限時間に平衡価格ベクトルを見出すのに知られているが,その時間複雑性については知られていない。本論文の主目的は,離散凸解析理論を使用して,上昇競売の複雑性をグローバル的且つローカル的に解析することであり,反復数の正確な範囲を,初期価格ベクトルと平衡との間のl_x距離により与え,価格ベクトルを更新する効率的アルゴリズムを,サブモジュラー関数最小化のための最小最大定理を基本として設計した。(翻訳著者抄録)

シソーラス用語： *分化 ,  *取引 ,  運動 ,  *時間分析 ,  性質 ,  利用 ,  評価 ,  平衡 ,  離散系 ,  数学 ,  アルゴリズム ,  Walrasian平衡 ,  *複雑性
準シソーラス用語： *競売 ,  効率的アルゴリズム ,  代替 ,  凸解析 ,  *反復運動

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

引用文献 (21件)：

• L. M. Ausubel. An efficient dynamic auction for heterogeneous commodities. American Economic Review, 96 (2006) 602-629.
• L. M. Ausubel and P. Milgrom. Ascending auctions with package bidding. Front. Theor. Econ., 1 (2002) Article 1.
• M. Bichler, P. Shabalin, and A. Pikovsky. A computational analysis of linear price iterative combinatorial auction formats. Inform. Syst. Res. 20 (2009), 33-59.
• M. Bing, D. Lehmann, and P. Milgrom. Presentation and structure of substitutes valuations. Proc. EC 2004,238-239.
• L. Blumrosen and N. Nisan. Combinatorial auction. in: N. Nisan, et al. (eds.) Algorithmic Game Theory, pp. 267-299. Cambridge Univ. Press, 2007.

タイトルに関連する用語 (5件)： 分化 ,  反復 ,  競売 ,  複雑性 ,  解析