Constant Inapproximability for Fisher Market

  • Thu 7 Mar 24

    12:00 - 13:00

  • Colchester Campus

    4SW.6.28 (Seminar Room 4)

  • Event speaker

    Argyrios Deligkas

  • Event type

    Lectures, talks and seminars
    CCFEA Seminar Series

  • Event organiser

    Computer Science and Electronic Engineering, School of

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.

Based on joint work with John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos.