Computing Competitive Equilibrium for Chores: Linear Convergence and Lightweight Iteration
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917795625697280 |
|---|---|
| author | Chen, He Jiang, Chonghe So, Anthony Man-Cho |
| author_facet | Chen, He Jiang, Chonghe So, Anthony Man-Cho |
| contents | Competitive equilibrium (CE) for chores has recently attracted significant attention, with many algorithms proposed to approximately compute it. However, existing algorithms either lack iterate convergence guarantees to an exact CE or require solving high-dimensional linear or quadratic programming subproblems. This paper overcomes these issues by proposing a novel unconstrained difference-of-convex formulation, whose stationary points correspond precisely to the CE for chores. We show that the new formulation possesses the local error bound property and the Kurdyka-Łojasiewicz property with an exponent of $1/2$. Consequently, we present the first algorithm whose iterates provably converge linearly to an exact CE for chores. Furthermore, by exploiting the max structure within our formulation and applying smoothing techniques, we develop a subproblem-free algorithm that finds an approximate CE in polynomial time. Numerical experiments demonstrate that the proposed algorithms outperform the state-of-the-art method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_04036 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computing Competitive Equilibrium for Chores: Linear Convergence and Lightweight Iteration Chen, He Jiang, Chonghe So, Anthony Man-Cho Optimization and Control Competitive equilibrium (CE) for chores has recently attracted significant attention, with many algorithms proposed to approximately compute it. However, existing algorithms either lack iterate convergence guarantees to an exact CE or require solving high-dimensional linear or quadratic programming subproblems. This paper overcomes these issues by proposing a novel unconstrained difference-of-convex formulation, whose stationary points correspond precisely to the CE for chores. We show that the new formulation possesses the local error bound property and the Kurdyka-Łojasiewicz property with an exponent of $1/2$. Consequently, we present the first algorithm whose iterates provably converge linearly to an exact CE for chores. Furthermore, by exploiting the max structure within our formulation and applying smoothing techniques, we develop a subproblem-free algorithm that finds an approximate CE in polynomial time. Numerical experiments demonstrate that the proposed algorithms outperform the state-of-the-art method. |
| title | Computing Competitive Equilibrium for Chores: Linear Convergence and Lightweight Iteration |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2410.04036 |