Constant Inapproximability for Fisher Markets
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909033393291264 |
|---|---|
| author | Deligkas, Argyrios Fearnley, John Hollender, Alexandros Melissourgos, Themistoklis |
| author_facet | Deligkas, Argyrios Fearnley, John Hollender, Alexandros Melissourgos, Themistoklis |
| contents | We study the problem of computing approximate market equilibria in Fisher markets with separable piecewise-linear concave (SPLC) utility functions. In this setting, the problem was only known to be PPAD-complete for inverse-polynomial approximations. We strengthen this result by showing PPAD-hardness for constant approximations. This means that the problem does not admit a polynomial time approximation scheme (PTAS) unless PPAD$=$P. In fact, we prove that computing any approximation better than $1/11$ is PPAD-complete. As a direct byproduct of our main result, we get the same inapproximability bound for Arrow-Debreu exchange markets with SPLC utility functions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_10802 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Constant Inapproximability for Fisher Markets Deligkas, Argyrios Fearnley, John Hollender, Alexandros Melissourgos, Themistoklis Computer Science and Game Theory Computational Complexity We study the problem of computing approximate market equilibria in Fisher markets with separable piecewise-linear concave (SPLC) utility functions. In this setting, the problem was only known to be PPAD-complete for inverse-polynomial approximations. We strengthen this result by showing PPAD-hardness for constant approximations. This means that the problem does not admit a polynomial time approximation scheme (PTAS) unless PPAD$=$P. In fact, we prove that computing any approximation better than $1/11$ is PPAD-complete. As a direct byproduct of our main result, we get the same inapproximability bound for Arrow-Debreu exchange markets with SPLC utility functions. |
| title | Constant Inapproximability for Fisher Markets |
| topic | Computer Science and Game Theory Computational Complexity |
| url | https://arxiv.org/abs/2605.10802 |