跳到主要內容

臺灣博碩士論文加值系統

(44.201.72.250) 您好!臺灣時間:2023/09/27 10:32
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:黃靖
研究生(外文):Huang, Jing
論文名稱:尋找線性Arrow-Debreu市場均衡的分散式演算法
論文名稱(外文):Distributed Algorithms for Finding Linear Arrow-Debreu Market Equilibria
指導教授:陳柏安陳柏安引用關係
指導教授(外文):Chen, Po-An
口試委員:孔令傑林莊傑張經略陳柏安
口試委員(外文):Kung, Ling-ChiehLin, Chuang-ChiehChang, Ching-LuehChen, Po-An
口試日期:2022-07-26
學位類別:碩士
校院名稱:國立陽明交通大學
系所名稱:資訊管理研究所
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2022
畢業學年度:110
語文別:英文
論文頁數:35
中文關鍵詞:Arrow-Debreu市場均衡凸最佳化問題極小化極大問題分散式演算法樂觀式梯度下降與上升演算法
外文關鍵詞:Arrow-Debreu market equilibriaConvex programMinimax programDistributed algorithmOptimistic gradient descent ascent
相關次數:
  • 被引用被引用:0
  • 點閱點閱:84
  • 評分評分:
  • 下載下載:2
  • 收藏至我的研究室書目清單書目收藏:0
市場的運作機制由商品價格、供給需求,以及市場參與者彼此之間的競爭所組成,每個市場參與者分別為了自身利益最大化而展開一系列的市場競爭行為,而其中商品價格則牽動了整個市場的供需平衡,影響了競爭者之間的互動行為。因此市場均衡指的是如何在彼此對立的市場競爭關係中,找到最適合的商品價格使得供給與需求保持平衡。

在此篇論文中,我們將研究如何透過分散式更新的演算法找到線性Arrow-Debreu市場均衡。我們根據Devanur學者們所提出的凸最佳化函數定義進行改寫設計出新的目標問題,並透過不同的分散式更新演算法進行最佳化求解。在我們的其中一個設計中,我們透過拉格朗日乘數法將原本帶有限制的凸最佳化問題轉換成一個沒有限制式的極小化極大問題,從而使用樂觀式的梯度下降與上升演算法求解至市場均衡,我們同時透過理論分析與數值實驗模擬,證明了我們提出的方法最終會收斂到市場均衡,並且達到至少線性以上的收斂速率。
The operating mechanism of the market includes price, supply and demand, and competition among market participants. Among them, item prices play an important role in affecting the balance of supply and demand throughout the market, and they also influence the interaction between competitors. Each agent then performs a series of competition behaviors to maximize her own utility in the market. Therefore, ``Market Equilibria'' refers to the most suitable price of items that can maintain a balance between supply and demand in a highly competitive market.

In this work, we study how to find a linear Arrow-Debreu market equilibrium using distributed update algorithms. We propose various programs based on the convex program formulated by Devanur et al. and solve them with different distributed algorithms. In one of our designs, we transformed the original constrained convex optimization problem into an unconstrained minimax problem using Lagrange multipliers. We then solve it with the optimistic gradient descent ascent algorithm, and demonstrate through theoretical analysis and numerical experimental simulations that our proposed solution will eventually converge to a market equilibrium with at least a linear convergence rate.
摘要. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Acknowledgement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 Computations of Market Equilibria . . . . . . . . . . . . . . . . . . . 2
1.1.2 Distributed Algorithms in Linear Bijective Arrow-Debreu Markets . . . 3
2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1 Bijective Arrow-Debreu Markets . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Convex Program for Linear Bijective Arrow-Debreu Markets . . . . . . . . . . 5
2.3 Block Coordinate Gradient Projection Method . . . . . . . . . . . . . . . . . . 6
2.4 Optimistic Gradient Descent Ascent Method . . . . . . . . . . . . . . . . . . . 6
3 Distributed Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.1 BCGP-based Algorithm for Linear Bijective Arrow-Debreu Market Program . 8
3.2 BCGP-based and GD-min Algorithms for Linear Bijective Arrow-Debreu Market
Program with the KL Divergence Term . . . . . . . . . . . . . . . . . . . . 9
3.3 GDA and OGDA Algorithms for Unconstrained Minimax Linear Bijective Arrow-
Debreu Market Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3.1 Transforming to an Unconstrained Minimax Problem using Lagrange
Multipliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3.2 GDA and OGDA Algorithms . . . . . . . . . . . . . . . . . . . . . . 13
4 Convergence Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.1 Convergence of BCGP-based and GD-min to Equilibria . . . . . . . . . . . . . 15
4.1.1 Convergence Analysis Idea of BCGP-based and GD-min . . . . . . . . 15
4.2 Convergence of OGDA to Minimax Equilibria . . . . . . . . . . . . . . . . . . 16
4.2.1 Average-Iterate Convergence . . . . . . . . . . . . . . . . . . . . . . . 16
4.2.2 Last-Iterate Convergence . . . . . . . . . . . . . . . . . . . . . . . . . 18
5 Simulations and Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.1 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.2 BCGP-based and GD-min Algorithms . . . . . . . . . . . . . . . . . . . . . . 23
5.2.1 Experiments for BCGP-based and GD-min Algorithms . . . . . . . . . 23
5.2.2 Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.3 GDA and OGDA Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5.3.1 Experiments for GDA and OGDA Algorithms . . . . . . . . . . . . . 27
5.3.2 Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.4 Experiments Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
6 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
[1] K. J. Arrow and G. Debreu, “Existence of an equilibrium for a competitive economy,” Econometrica, pp. 265–290, 1954.
[2] K. Jain, “A polynomial time algorithm for computing an arrow–debreu market equilibrium for linear utilities,” SIAM Journal on Computing, pp. 303–318, 2007.
[3] N. R. Devanur, J. Garg, and L. A. Végh, “A rational convex program for linear arrowdebreu markets,” ACM Trans. Econ. Comput., oct 2016.
[4] A. Beck and L. Tetruashvili, “On the convergence of block coordinate descent type methods,” SIAM Journal on Optimization, pp. 2037–2060, 2013.
[5] P.-A. Chen, C.-J. Lu, and Y.-S. Lu, “An alternating algorithm for finding linear arrowdebreu market equilibria,” Theory of Computing Systems, 2022.
[6] N. R. Devanur, C. H. Papadimitriou, A. Saberi, and V. V. Vazirani, “Market equilibrium via a primal–dual algorithm for a convex program,” J. ACM, nov 2008.
[7] B. Birnbaum, N. R. Devanur, and L. Xiao, “Distributed algorithms via gradient descent for fisher markets,” in Proceedings of the 12th ACM Conference on Electronic Commerce, 2011.
[8] F. Wu and L. Zhang, “Proportional response dynamics leads to market equilibrium,” in Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, 2007.
[9] R. Duan, J. Garg, and K. Mehlhorn, “An improved combinatorial polynomial algorithm for the linear arrow-debreu market,” in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016.
[10] S. Brânzei, N. Devanur, and Y. Rabani, “Proportional dynamics in exchange economies,” in Proceedings of the 22nd ACM Conference on Economics and Computation, 2021.
[11] C.-Y. Wei, C.-W. Lee, M. Zhang, and H. Luo, “Linear last-iterate convergence in constrained saddle-point optimization,” 2021.
[12] J. Abernethy, P. L. Bartlett, and E. Hazan, “Blackwell approachability and no-regret learning are equivalent,” in Proceedings of the 24th Annual Conference on Learning Theory, 2011.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top