2025/06/03 by Cheung, Yun Kuen, Cole, Richard, Tao, Yixin · 2 citations
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Economics and business #Theoretical Economics (econ.TH)
paper · doi:10.48550/arxiv.2506.02852
Proportional response is a well-established distributed algorithm which has been shown to converge to competitive equilibria in both Fisher and Arrow-Debreu markets, for various sub-families of homogeneous utilities, including linear and constant elasticity of substitution utilities. We propose a natural generalization of proportional response for gross substitutes utilities, and prove that it converges to competitive equilibria in Fisher markets. This is the first convergence result of a proportional response style dynamics in Fisher markets for utilities beyond the homogeneous utilities covered by the Eisenberg-Gale convex program. We show an empirical convergence rate of O(1/T) for the prices. Furthermore, we show that the allocations of a lazy version of the generalized proportional response dynamics converge to competitive equilibria in Arrow-Debreu markets.