Deligkas, Argyrios and Fearnley, John and Hollender, Alexandros and Melissourgos, Themistoklis (2024) Constant Inapproximability for Fisher Markets. In: Twenty-Fifth ACM Conference on Economics and Computation (EC'24), 2024-07-08 - 2024-07-11, Yale University, New Haven, CT, USA. (In Press)
Deligkas, Argyrios and Fearnley, John and Hollender, Alexandros and Melissourgos, Themistoklis (2024) Constant Inapproximability for Fisher Markets. In: Twenty-Fifth ACM Conference on Economics and Computation (EC'24), 2024-07-08 - 2024-07-11, Yale University, New Haven, CT, USA. (In Press)
Deligkas, Argyrios and Fearnley, John and Hollender, Alexandros and Melissourgos, Themistoklis (2024) Constant Inapproximability for Fisher Markets. In: Twenty-Fifth ACM Conference on Economics and Computation (EC'24), 2024-07-08 - 2024-07-11, Yale University, New Haven, CT, USA. (In Press)
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.
Item Type: | Conference or Workshop Item (Paper) |
---|---|
Additional Information: | Published proceedings: _not provided_ |
Divisions: | Faculty of Science and Health Faculty of Science and Health > Computer Science and Electronic Engineering, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 03 Oct 2024 12:41 |
Last Modified: | 03 Oct 2024 12:42 |
URI: | http://repository.essex.ac.uk/id/eprint/38498 |
Available files
Filename: preprint.pdf