Proportional Response Dynamics in Gross Substitutes Markets
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916775566770176 |
|---|---|
| author | Cheung, Yun Kuen Cole, Richard Tao, Yixin |
| author_facet | Cheung, Yun Kuen Cole, Richard Tao, Yixin |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_02852 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Proportional Response Dynamics in Gross Substitutes Markets Cheung, Yun Kuen Cole, Richard Tao, Yixin Computer Science and Game Theory Theoretical Economics 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. |
| title | Proportional Response Dynamics in Gross Substitutes Markets |
| topic | Computer Science and Game Theory Theoretical Economics |
| url | https://arxiv.org/abs/2506.02852 |