請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41012
標題: | 市場均衡之可近似性之拓展 Extending the Approximability Frontier of Market Equilibrium |
作者: | Wen-Liang Tseng 曾文良 |
指導教授: | 呂學一 |
關鍵字: | 市場均衡,近似演算法, market equilibrium,approximation algorithm, |
出版年 : | 2008 |
學位: | 碩士 |
摘要: | 我們研究計算市場均衡的問題並且在功能函數(utility function)與物品種類數目方面做出拓展。在本論文中,我們考慮關於具有生產單元的Fisher市場模型。在這個市場模型下,Eisenberg 和Gale 提供一個可以對線性功能函數計算市場均衡的凸規劃(convex program) 。Eisenberg拓展至一次齊次(homogeneous of degree one)凹函數(concave function)。Jain、Vazirani與Ye拓展至齊序(homothetic)似凹性(quasi-concave)功能函數。我們應用由Codenotti、McCune與Varadarajan提出的方法將功能函數更拓展至隱含單調需求(monotone demand)的函數,其中包含不屬於齊序函數與通貨替代(gross substitutes)函數的例子。我們更將其拓展至當物品種類數目是無界(unbounded)時的情形。當功能函數是線性、可選擇的物品數量為實數、物品種類數目是有界(bounded)時,Deng、Papadimitriou和Safra提供一個可以計算市場均衡的多項式時間演算法。他們提及當物品種類數目是無界時不知是否有可計算市場均衡的多項式時間近似演算法。經由仔細分析我們在拓展功能函數的結果,我們證明在一些合理條件下,當物品種類數目是無界時,我們所使用的市場模型存在可計算市場均衡的多項式時間近似演算法。 We consider the computation of market equilibrium and make progress along directions of utility function sets and unbounded unmber of goods for a production economy of Fisher’s model. Eisenberg and Gale gave a convex program for computing market equilibrium for linear utility functions, and Eisenberg generalized this to concave homogeneous functions of degree one. Jain, Vazirani and Ye generalized to homothetic, quasi-concave functions. We apply the method developed by Codenotti, McCune, and Varadarajan to further extend the frontier of approximability to the utility functions that imply monotone demand, which include the cases beyond homothetic and gross substitutes. In addition, by a careful analysis in the applied method, we show that our results can be extended to the case where the number of goods is unbounded. Thus we make progress towards affirmatively answering the problem mentioned by Deng, Papadimitriou, and Safra. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41012 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-97-1.pdf 目前未授權公開取用 | 373.83 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。