講演抄録/キーワード |
講演名 |
2008-03-10 14:50
関税モデルへのオークションアルゴリズムの拡張とその実装 宮沢 徹・○武井由智(長岡技科大) COMP2007-62 |
抄録 |
(和) |
市場均衡価格を予測することは有限資源の効率活用につながるという点で,消費者及び供給者の両者に対して有用であるといえる。市場モデルの一種の「生産者モデル」とそれに対して均衡価格近似解を効率的に導出するオークションアルゴリズムが提案されている [Kapoor, Mehta, Vazirani; WINE2005].
本稿では生産者モデルに関税という概念を加え,よりモデルを現実に近づける。さらに,オークションアルゴリズムを拡張して,関税モデルに対し,近似解を高々消費者総数の2乗,商品の種類数の2乗,生産者総数の2乗,消費者の総予算,均衡価格の誤差の上界の$-2$乗(関税が商品に対して一律で生産者にのみに依存する場合$-1$乗)
に比例するステップ時間で導出するアルゴリズムを提案する。さらにアルゴリズムの実装を行う. |
(英) |
The ability of forecasting the equilibrium price in a market is valuable for both consumers and suppliers because it would lead to an efficient use of limited resources. The producer model, a kind of market model, and an auction algorithm for it which derives an approximate solution of the equilibrium price efficiently were proposed in [Kapoor, Mehta, Vazirani; WINE2005].
In this report, we extend the producer model by introducing the notion of duty so that the resulting model is more realistic. Moreover, we extend the auction algorithm of Kapoor etal. to one which works under the duty model, calculating the approximate equilibrium price within the step time proportional to the square of the number of consumers, to the square of the number of species of goods, to the square of the number of producers, to the total budget of the consumers, and to the square of the reciprocal (to the resiprocal; if the duty is uniform with respect to the goods and depends only on the producers) of the error bound of the approximate equilibrium price. We also present an implementation of the proposed algorithm. |
キーワード |
(和) |
オークションアルゴリズム / 近似アルゴリズム / 均衡価格 / / / / / |
(英) |
auction algorithms / approximation algorithms / the equilibrium price / / / / / |
文献情報 |
信学技報, vol. 107, no. 537, COMP2007-62, pp. 47-54, 2008年3月. |
資料番号 |
COMP2007-62 |
発行日 |
2008-03-03 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2007-62 |