《市場均衡中的算法與計算複雜度》是黃立沙編寫的論文。
基本介紹
- 中文名：市場均衡中的算法與計算複雜度
- 作者：黃立沙
- 導師：張鈸,鄧小鐵
- 學位級別：博士論文
- 學位授予單位：清華大學
- 學位授予時間：2007
- 館藏號：F019.1
- 館藏目錄：2009\F019.1\1
- 關鍵字：平衡論 市場經濟 個體經濟學
- 學科專業：計算機科學與技術
中文摘要
做為個體經濟學中的重要概念，市場均衡近年來吸引了計算機科學界的注意。本文從算法設計和計算複雜度角度研究了市場均衡的計算問題。 1.通過所謂財富調整過程在Arrow-Debreu市場模型和它的特例Fisher市場模型之間建立了聯繫，證明了對許多需求函式，財富調整過程的每一步都是Lipschitz連續函式，而且這個函式的近似殘值不動點恰好是Arrow-Debreu市場模型的近似均衡。從而任何求解Fisher模型中均衡的算法都可以與不動點算法結合去逼近Arrow-Debreu模型中的均衡。 2.研究了具有對數一線性收益函式的市場中的均衡，分別對Fisher模型和Arrow-Debreu模型給出了算法。 3.研究了具有Leontief收益函式的市場的均衡求解問題的計算複雜度，證明了尋找能最大化社會收益或者最大化個人收益的均衡都是NP-難的，而計算均衡點的數量則是#P-難的；證明了除非PPAD⊆P，否則計算這種市場中的均衡不可能有多項式時間的逼近算法；證明了除非PPAD⊆RP，否則計算這種市場中的均衡不可能有光滑複雜度為多項式時間的算法。 4.引入了一種兩層的收益函式，將簡單的線性收益函式和複雜的Leontief收益函式結合起來；給出了多項式時間的算法來求解具有這種收益函式的Fisher模型中的均衡，然後討論了對Arrow-Debreu模型中的均衡的逼近算法。 5.研究了離散變數市場模型中Walrasian均衡的計算複雜度及其逼近，推廣了已有的均衡存在性判定定理，並對任務調度問題證明了判定均衡存在的NP-困難性；提出了離散模型中弱Walrasian均衡的概念，並討論了計算弱Walrasian均衡的複雜度以及近似算法。
