Algorithms and Computing Systems Series
2026-02-04 13:00 - 14:00 | GH223
John Fearnley: Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD

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.

https://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1323
