Conference item
Constant inapproximability for Fisher markets
- Abstract:
- 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 720.8KB, Terms of use)
-
- Publisher copy:
- 10.1145/3670865.3673533
Authors
+ Engineering and Physical Sciences Research Council
More from this funder
- Funder identifier:
- https://ror.org/0439y7842
- Funding agency for:
- Deligkas, A
- Grant:
- EP/X039862/1
- Programme:
- NAfANE: New Approaches for Approximate Nash Equilibria
+ Engineering and Physical Sciences Research Council
More from this funder
- Funder identifier:
- https://ror.org/0439y7842
- Funding agency for:
- Fearnley, J
- Grant:
- EP/W014750/1
- Programme:
- New Techniques for Resolving Boundary Problems in Total Search
- Publisher:
- Association for Computing Machinery
- Host title:
- EC '24: Proceedings of the 25th ACM Conference on Economics and Computation
- Pages:
- 13-39
- Publication date:
- 2024-12-17
- Acceptance date:
- 2024-05-18
- Event title:
- 25th ACM Conference on Economics and Computation (EC 2024)
- Event location:
- New Haven, CT, United States
- Event website:
- https://ec24.sigecom.org/
- Event start date:
- 2024-07-08
- Event end date:
- 2024-07-11
- DOI:
- EISBN:
- 9798400707049
- Language:
-
English
- Keywords:
- Pubs id:
-
2020860
- Local pid:
-
pubs:2020860
- Deposit date:
-
2024-08-09
Terms of use
- Copyright holder:
- Deligkas et al.
- Copyright date:
- 2024
- Rights statement:
- © 2024 Copyright held by the owner/author(s). This work is licensed under a Creative Commons Attribution International 4.0 License.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record