呂學一臺灣大學:資訊工程學研究所曾文良Tseng, Wen-LiangWen-LiangTseng2010-06-022018-07-052010-06-022018-07-052008U0001-2507200809502400http://ntur.lib.ntu.edu.tw//handle/246246/184891我們研究計算市場均衡的問題並且在功能函數(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 Yeeneralized 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 affirmativelynswering the problem mentioned by Deng, Papadimitriou, and Safra.Acknowledgements ihinese Abstract iinglish Abstract iiiontents iv Introduction 1 A Production Economy of Fisher’s model 7 Framework of Computation and the Property of Fisher’s Setting 10.1 Framework of Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.2 The Property of Fisher’s Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Computation of Market Equilibrium 16.1 A Separation Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16.2 Proof of Theorem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19.3 Proof of Theorem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Concluding Remarks 21ibliography 21application/pdf382798 bytesapplication/pdfen-US市場均衡近似演算法market equilibriumapproximation algorithmthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/184891/1/ntu-97-R92943139-1.pdf