[Proof Complexity] MIAO seminar Wed Nov 19 at 11:00 CET with Alexandros Hollender: Fisher markets with approximately optimal bundles and the need for a PCP theorem for PPAD

[Jakob Nordström]

Dear all,

With apologies for the short notice, on Wednesday November 19 at 11:00 CET (note the time!) we are excited to welcome Alexandros Hollender from the University of Oxford, who will present a seminar titled "Fisher markets with approximately optimal bundles and the need for a PCP theorem for PPAD". You find the abstract at the bottom of this message.

We will run this as a MIAO hybrid seminar at the University of Copenhagen. Local participants are warmly welcome to the new location of the Algorithms and Complexity Section at Vibenshuset, Lyngbyvej 2, while other participants are equally warmly welcome to join virtually at https://lu-se.zoom.us/j/61925271827 . Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar and post on the MIAO Research YouTube channel https://youtube.com/@MIAOresearch for people who would like to hear the talk but cannot attend.

More information about the MIAO seminar series can be found at https://jakobnordstrom.se/miao-seminars/ . If you do not wish to receive these announcements, or receive several copies of them, please send a message to jn at di.ku.dk.

Best regards,
Jakob Nordström

**********

Wednesday Nov 19 at 11:00 (note the time!) at the Algorithms and Complexity Section at the University of Copenhagen, Vibenshuset, Lyngbyvej 2, and on Zoom
Fisher markets with approximately optimal bundles and the need for a PCP theorem for PPAD
(Alexandros Hollender, University of Oxford)

We study the problem of computing (ε,δ)-approximate market equilibria in Fisher markets, meaning that every good should ε-approximately clear and every buyer should receive a (1-δ)-optimal bundle. While the problem is known to be PPAD-hard even for constant ε when δ = 0, there are no known lower bounds when δ > 0. We prove that the problem remains PPAD-hard for constant δ > 0, assuming the so-called PCP-for-PPAD conjecture. Furthermore, we show that the PCP-for-PPAD conjecture is in fact required to show hardness for constant δ: showing PPAD-hardness for (ε, δ)-approximate market equilibrium (even with ε = 0) in the natural class of markets considered by our hardness result would prove the conjecture.

Joint work with Argyrios Deligkas, John Fearnley, and Themistoklis Melissourgos.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +45 28 78 38 11 / +46 70 742 21 98
https://jakobnordstrom.se