Fast and Interpretable Dynamics for Fisher Markets via Block-Coordinate Updates
Tianlong Nan, Yuan Gao, Christian Kroer
Abstract
We consider the problem of large-scale Fisher market equilibrium computation through scalable first-order optimization methods. It is well-known that market equilibria can be captured using structured convex programs such as the Eisenberg-Gale and Shmyrev convex programs. Highly performant deterministic full-gradient first-order methods have been developed for these programs. In this paper, we develop new block-coordinate first-order methods for computing Fisher market equilibria, and show that these methods have interpretations as tâtonnement-style or proportional response-style dynamics where either buyers or items show up one at a time. We reformulate these convex programs and solve them using proximal block coordinate descent methods, a class of methods that update only a small number of coordinates of the decision variable in each iteration. Leveraging recent advances in the convergence analysis of these methods and structures of the equilibrium-capturing convex programs, we establish fast convergence rates of these methods.
BibTeX
@article{Nan_Gao_Kroer_2023, title={Fast and Interpretable Dynamics for Fisher Markets via Block-Coordinate Updates}, volume={37}, url={https://ojs.aaai.org/index.php/AAAI/article/view/25723}, DOI={10.1609/aaai.v37i5.25723}, abstractNote={We consider the problem of large-scale Fisher market equilibrium computation through scalable first-order optimization methods. It is well-known that market equilibria can be captured using structured convex programs such as the Eisenberg-Gale and Shmyrev convex programs. Highly performant deterministic full-gradient first-order methods have been developed for these programs. In this paper, we develop new block-coordinate first-order methods for computing Fisher market equilibria, and show that these methods have interpretations as tâtonnement-style or proportional response-style dynamics where either buyers or items show up one at a time. We reformulate these convex programs and solve them using proximal block coordinate descent methods, a class of methods that update only a small number of coordinates of the decision variable in each iteration. Leveraging recent advances in the convergence analysis of these methods and structures of the equilibrium-capturing convex programs, we establish fast convergence rates of these methods.}, number={5}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Nan, Tianlong and Gao, Yuan and Kroer, Christian}, year={2023}, month={Jun.}, pages={5832-5840} }