Accelerated Price Adjustment for Fisher Markets with Exact Recovery of Competitive Equilibrium
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918157153730560 |
|---|---|
| author | Chen, He Jiang, Chonghe So, Anthony Man-Cho |
| author_facet | Chen, He Jiang, Chonghe So, Anthony Man-Cho |
| contents | The canonical price-adjustment process, tâtonnement, typically fails to converge to the exact competitive equilibrium (CE) and requires a high iteration complexity of $\tilde{\mathcal{O}}(1/ε)$ to compute $ε$-CE prices in widely studied linear and quasi-linear Fisher markets. This paper proposes refined price-adjustment processes to overcome these limitations. By formulating the task of finding CE of a (quasi-)linear Fisher market as a strongly convex nonsmooth minimization problem, we develop a novel accelerated price-adjustment method (APM) that finds an $ε$-CE price in $\tilde{\mathcal{O}}(1/\sqrtε)$ lightweight iterations, which significantly improves upon the iteration complexities of tâtonnement methods. Furthermore, through our new formulation, we construct a recovery oracle that maps approximate CE prices to exact CE prices at a low computational cost. By coupling this recovery oracle with APM, we obtain an adaptive price-adjustment method whose iterates converge to CE prices in finite steps. To the best of our knowledge, this is the first convergence guarantee to exact CE for price-adjustment methods in linear and quasi-linear Fisher markets. Our developments pave the way for efficient lightweight computation of CE prices. We also present numerical results to demonstrate the fast convergence of the proposed methods and the efficient recovery of CE prices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_07759 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Accelerated Price Adjustment for Fisher Markets with Exact Recovery of Competitive Equilibrium Chen, He Jiang, Chonghe So, Anthony Man-Cho Optimization and Control The canonical price-adjustment process, tâtonnement, typically fails to converge to the exact competitive equilibrium (CE) and requires a high iteration complexity of $\tilde{\mathcal{O}}(1/ε)$ to compute $ε$-CE prices in widely studied linear and quasi-linear Fisher markets. This paper proposes refined price-adjustment processes to overcome these limitations. By formulating the task of finding CE of a (quasi-)linear Fisher market as a strongly convex nonsmooth minimization problem, we develop a novel accelerated price-adjustment method (APM) that finds an $ε$-CE price in $\tilde{\mathcal{O}}(1/\sqrtε)$ lightweight iterations, which significantly improves upon the iteration complexities of tâtonnement methods. Furthermore, through our new formulation, we construct a recovery oracle that maps approximate CE prices to exact CE prices at a low computational cost. By coupling this recovery oracle with APM, we obtain an adaptive price-adjustment method whose iterates converge to CE prices in finite steps. To the best of our knowledge, this is the first convergence guarantee to exact CE for price-adjustment methods in linear and quasi-linear Fisher markets. Our developments pave the way for efficient lightweight computation of CE prices. We also present numerical results to demonstrate the fast convergence of the proposed methods and the efficient recovery of CE prices. |
| title | Accelerated Price Adjustment for Fisher Markets with Exact Recovery of Competitive Equilibrium |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2510.07759 |