臺灣博碩士論文加值系統

市場的運作機制由商品價格、供給需求，以及市場參與者彼此之間的競爭所組成，每個市場參與者分別為了自身利益最大化而展開一系列的市場競爭行為，而其中商品價格則牽動了整個市場的供需平衡，影響了競爭者之間的互動行為。因此市場均衡指的是如何在彼此對立的市場競爭關係中，找到最適合的商品價格使得供給與需求保持平衡。

在此篇論文中，我們將研究如何透過分散式更新的演算法找到線性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.