Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD

4^th February 2026, 13:00 GH223
John Fearnley
University of Liverpool

Abstract

I will talk about some recent results that we have obtained on finding approximate market equilibria in Fisher markets. In particular, I will talk about the result that we obtained in our EC 2024 paper, where we showed that finding a market equilibrium in which the clearing constraint is approximately satisfied is PPAD hard even for constant approximations. I will also talk about our more recent work and ongoing work studying market equilibria with approximately optimal bundles, in which we show that the problem is related to the PCP-for-PPAD conjecture.



This is joint work with Argyrios Deligkas, Alexandros Hollender, and Themistoklis Melissourgos.