BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260922T101905Z
UID:Seminar-EcCo-1131@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20221207T110000
DTEND:20221207T120000
SUMMARY:Economics and Computation Series
DESCRIPTION:John Fearnley: Pure-Circuit: Tight Inapproximability within PPAD\n\nI will talk about a new technique for showing strong inapproximability results within PPAD based on a new problem called Pure-Circuit. In particular, I will talk about a new hardness result for epsilon approximate well-supported equilibria (WSNE) in polymatrix games which applies for all epsilon < 1/3 and is tight for two-action games, a new hardness result for finding epsilon-WSNEs in graphical games for all epsilon < 1, which is tight for all games, and a new hardness result for finding epsilon approximate Nash equilibria in graphical games for all epsilon < 1/2, which is tight for two-action games.\n\nThis is joint work with Argyrios Deligkas (Royal Holloway), Alexandros Hollender (Oxford & EPFL), and Themistoklis Melissourgos (Essex), and is presented in the following papers\n- Pure-Circuit: Strong Inapproximability in PPAD, FOCS 2022.\n- Tight Inapproximability for Graphical Games, AAAI 2023.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1131
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR